threes ai

AI สำหรับเกม Threes! โดย Sirvo LLC คุณสามารถรับเกมได้จากที่นี่: http://asherv.com/threes/

การสร้าง AI นี้เป็นแรงบันดาลใจสำหรับ AI ในปี 2048 ของฉันในภายหลัง และแนวคิดบางส่วนจาก AI ปี 2048 ก็ถูกส่งกลับไปยัง AI นี้เช่นกัน

แม้ว่าฉันจะยังไม่ได้เปรียบเทียบประสิทธิภาพของ AI นี้อย่างเป็นทางการ แต่ฉันรู้ว่ามันประสบความสำเร็จในการบรรลุไทล์ 6144 หลายครั้ง ซึ่งเป็นไทล์ที่สูงที่สุดในเกม (ไทล์ที่สูงกว่านั้นเป็นไปได้แต่ไม่น่าเป็นไปได้ เนื่องจากเอฟเฟกต์สุ่มจำนวนมาก) คะแนนสูงสุด (ณ เวลาที่เขียน) คือ 775,524 คะแนน:

AI นี้เป็นการทดลองมากกว่า AI รุ่นน้องใหม่อย่าง 2048 AI เนื่องจากความซับซ้อนที่เพิ่มขึ้นของ Threes! และเนื่องจากยังไม่ได้รับเวลาในการพัฒนามากนัก นอกจากนี้ ทรีส! โดยทั่วไปแล้วจะเป็นเป้าหมายที่เคลื่อนไหวเล็กน้อย เนื่องจากอัลกอริธึมการสร้างไทล์แบบสุ่มมีการปรับแต่งเป็นครั้งคราว ซึ่งจำเป็นต้องมีการเปลี่ยนแปลงใน AI

อัลกอริทึม

อัลกอริทึมสำหรับ AI นี้มีรายละเอียดอยู่แล้วในคำตอบ StackOverflow ที่อธิบาย 2048 AI ของฉัน โดยพื้นฐานแล้ว จะใช้การค้นหาแบบ bruteforce ที่ปรับให้เหมาะสมที่สุดเหนือแผนผังเกม (การเคลื่อนไหวที่เป็นไปได้ทั้งหมด ค่าการวางไข่ของช่องสัญญาณ และค่าของช่องสัญญาณ) โดยใช้การปรับคาดหวังสูงสุดเพื่อรวมผลลัพธ์และค้นหาการเคลื่อนไหวที่ "ดีที่สุด" ที่เป็นไปได้

จริงๆ แล้ว Threes AI นี้มีความซับซ้อนมากกว่า AI ปี 2048 ในหลายๆ ด้าน โดยเฉพาะอย่างยิ่ง มันคำนึงถึง "สำรับ" ของไทล์ที่กำลังจะมาถึง (กระบวนการที่มีการจัดทำเอกสารไว้อย่างดีในการเลือกไทล์ที่เข้ามาแบบสุ่ม) และจัดการได้อย่างเหมาะสม ตำแหน่งวางไข่ที่เป็นไปได้ทั้งหมดขึ้นอยู่กับการเคลื่อนไหวที่เกิดขึ้น กล่าวโดยย่อ: Threes AI นี้อย่างถูกต้อง (ตามความรู้ที่ดีที่สุดของฉัน) จำลองทุกรายละเอียดของเกม Threes ซึ่งเป็นส่วนหนึ่งของกระบวนการเพิ่มประสิทธิภาพคาดหวังสูงสุด

อาคาร

วิธีที่ง่ายที่สุดในการทำให้ AI ทำงานคือการโคลนหนึ่งในสาขา prebuilt/ สาขาที่สอดคล้องกับระบบปฏิบัติการและโปรเซสเซอร์ของคุณ สาขาเหล่านี้มีไบนารีที่สร้างไว้ล่วงหน้าในไดเร็กทอรี bin/

โปรดทราบว่า Python "เริ่มต้น" บน Windows คือ 32 บิต ในขณะที่ Python "เริ่มต้น" บน OS X และ Linux คือ 64 บิต บิลด์ 32 บิตถูกแท็ก i386 ในขณะที่บิลด์ 64 บิตถูกแท็ก x86_64

หากคุณต้องการสร้างด้วยตนเองจากแหล่งที่มา (เช่น หากคุณกำลังทำการเปลี่ยนแปลง) ให้ทำตามคำแนะนำด้านล่าง

ยูนิกซ์/ลินุกซ์/OS X

ดำเนินการ

 ./configure
make

ในอาคารผู้โดยสาร คอมไพเลอร์ C++ ที่ค่อนข้างใหม่ควรสามารถสร้างเอาต์พุตได้

โปรดทราบว่าคุณไม่ได้ make install ; โปรแกรมนี้ตั้งใจให้รันจากไดเร็กทอรีนี้

หน้าต่าง

คุณมีตัวเลือกสองสามตัว ขึ้นอยู่กับสิ่งที่คุณติดตั้ง

• Pure Cygwin: ปฏิบัติตามคำแนะนำ Unix/Linux/OS X ด้านบน DLL ที่เป็นผลลัพธ์สามารถใช้ได้กับโปรแกรม Cygwin เท่านั้น ดังนั้นในการรันเวอร์ชันควบคุมเบราว์เซอร์ คุณต้องใช้ Cygwin Python (ไม่ใช่ python.org Python) สำหรับคำแนะนำทีละขั้นตอน ความอนุเคราะห์จาก Tamas Szell (@matukaa) โปรดดูเอกสารนี้

• Cygwin กับ MinGW: วิ่ง

    CXX=x86_64-w64-mingw32-g++ CXXFLAGS='-static-libstdc++ -static-libgcc -D_WINDLL -D_GNU_SOURCE=1' ./configure ; make
  

  ในเชลล์ MinGW หรือ Cygwin เพื่อสร้าง DLL ที่เป็นผลลัพธ์สามารถใช้กับโปรแกรมที่ไม่ใช่ Cygwin ได้

• Visual Studio: เปิดพรอมต์คำสั่ง Visual Studio cd ไปที่ไดเร็กทอรี threes-ai และเรียกใช้ make-msvc.bat

วิ่ง

ข้อกำหนดเบื้องต้นของ Python

คุณจะต้องมี Python 2.7, NumPy และ PIL เพื่อรันโปรแกรม Python

เรียกใช้เวอร์ชันบรรทัดคำสั่ง

เรียกใช้ bin/threes หากคุณต้องการเห็นการทำงานของ AI ด้วยตัวเอง

ผู้ช่วย Android

มี Threes เวอร์ชันบนเว็บบางเวอร์ชัน แต่ฉันต้องการให้ AI เล่นกับแอปจริง ดังนั้นฉันจึงสร้างโปรแกรม "ผู้ช่วย" สำหรับอุปกรณ์ Android ชื่อ android_assistant.py ซึ่งสื่อสารกับโทรศัพท์ผ่าน ADB และทำการเคลื่อนไหวโดยอัตโนมัติโดยสมบูรณ์ ต้องการเพียงสิทธิ์ USB ADB (การเข้าถึงของนักพัฒนามาตรฐาน) และไม่จำเป็นต้องทำการรูทหรือดัดแปลงอุปกรณ์หรือแอพอื่นใด ใช้ยูทิลิตี้ screencap มาตรฐานของ Android เพื่อรับสถานะเกม (มองเห็นได้) คำนวณการเคลื่อนไหวที่เหมาะสมที่สุด จากนั้นใช้ระบบย่อยเหตุการณ์อินพุต Linux เพื่อสร้างเหตุการณ์การปัด

หากต้องการใช้ android_assistant.py คุณจะต้องกำหนดค่าระบบย่อย OCR สำหรับอุปกรณ์ของคุณ คุณจะต้องบันทึกเหตุการณ์การปัดเพื่อเล่นซ้ำ ปัจจุบันมีการกำหนดค่าอุปกรณ์สองเครื่อง: LG Nexus 5 และ OnePlus One (ตรงกับโทรศัพท์ที่ฉันได้ทำการทดสอบ) แพทช์ยินดีที่จะเพิ่มโทรศัพท์เพิ่มเติม

หากต้องการกำหนดค่าระบบ OCR คุณควรเพิ่มรายการใน ocr/devices.py ที่สอดคล้องกับอุปกรณ์ของคุณ สามารถรับชื่อรุ่นได้เพียงแค่เรียกใช้ android_assistant.py ในขณะที่เชื่อมต่อกับอุปกรณ์ (ควรเกิดข้อผิดพลาดกับชื่อรุ่นที่คาดหวัง) โดยพื้นฐานแล้ว คุณจะต้องจับภาพหน้าจอของเกมและรับตำแหน่งของแผง "ช่องต่อที่จะมาถึง" รวมถึงตำแหน่งและระยะห่างของตารางช่องต่อ (ส่วนนี้อาจใช้ระบบอัตโนมัติและ/หรือลดความซับซ้อนมากกว่านี้!)

หากต้องการบันทึกเหตุการณ์ เพียงเรียกใช้ python -m android.inputemu --record up down left right และดำเนินการท่าทางที่เหมาะสมบนโทรศัพท์ของคุณเมื่อได้รับแจ้ง

ผู้ช่วยด้วยตนเอง

คู่มือผู้ช่วยคือ Threes อเนกประสงค์! ผู้ช่วยที่ทำงานร่วมกับการใช้งาน Threes!. คุณบอกกระดานและชุดไทล์ที่กำลังจะมาถึง จากนั้นผู้ช่วยจะคำนวณการเคลื่อนไหวที่ดีที่สุด

เรียกใช้ manual_assistant.py เพื่อเริ่มการทำงานของผู้ช่วยด้วยตนเอง

โปรดทราบว่าผู้ช่วยแบบแมนนวลคาดว่าจะเห็นการเคลื่อนไหวตามลำดับ หากคุณข้ามไปข้างหน้า (เคลื่อนไหวโดยไม่มีผู้ช่วย) ให้ออกจากผู้ช่วยโดยกด Ctrl+C แล้วเริ่มใหม่อีกครั้ง มิฉะนั้น คุณอาจได้รับข้อความแสดงข้อผิดพลาดเช่น "สถานการณ์ที่เป็นไปไม่ได้" หากคุณเข้าสู่บอร์ดที่ไม่ต่อเนื่องกับบอร์ดก่อนหน้า

เข้าบอร์ด

เมื่อเข้าสู่กระดานถัดไป คุณสามารถใช้ช่องว่าง บรรทัดใหม่ และ/หรือเครื่องหมายจุลภาคเพื่อแยกไทล์ได้ อ่านจากซ้ายไปขวา แล้วบนลงล่าง ป้อนศูนย์สำหรับช่องว่าง ข้อมูลตัวอย่าง:

• การใช้เครื่องหมายจุลภาคและบรรทัดใหม่:

    96,2,3,0
    2,1,1,0
    2,1,0,0
    0,0,2,0
  

• การใช้ลูกน้ำเพียงอย่างเดียว:

    96,2,3,0,2,1,1,0,2,1,0,0,0,0,2,0
  

• การใช้ช่องว่าง:

    96 2 3 0
    2 1 1 0
    2 1 0 0
    0 0 2 0
  

คุณยังสามารถป้อน "เดลต้า" จากบอร์ดก่อนหน้าได้ ระบุแถวหรือคอลัมน์ที่ไทล์ใหม่เกิดขึ้น และค่าของไทล์ที่เกิด (คุณสามารถละเว้นได้หากมีเพียงหนึ่งไทล์ใหม่ที่เป็นไปได้ในครั้งสุดท้าย เช่น ถ้าเป็นสีแดงหรือสีน้ำเงิน) ระบุการเคลื่อนไหวที่คุณทำด้วย หากไม่ใช่การเคลื่อนไหวที่แนะนำโดย AI

คอลัมน์และแถวจะมีหมายเลขกำกับจากซ้ายไปขวาและบนลงล่าง โดยคอลัมน์ที่ 1 คือคอลัมน์ด้านซ้าย และแถวที่ 1 คือแถวบนสุด

ตัวอย่างเช่นหากกระดานถูกปัดขึ้นและไปจาก

 96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0

ถึง

 96 3 3 0
2 1 1 0
2 0 2 0
0 3 0 0

จากนั้นคุณจะส่ง 2,3,up เป็นกระดาน (ในคอลัมน์ที่ 2 มี 3 วางไข่) หาก AI แนะนำให้เลื่อน up คุณสามารถละเว้นและส่ง 2,3 ได้ หากไทล์ที่กำลังจะมาถึงได้รับการคาดการณ์เป็น 3 คุณสามารถละเว้น 3 และส่งเพียง 2 ได้

การเข้าสู่สันดอนจะช่วยประหยัดเวลาได้มาก ในกรณีส่วนใหญ่ คุณจะต้องป้อนเพียงตัวเลขเดียวเท่านั้น (คอลัมน์/แถวที่เปลี่ยนแปลง)

เข้ากระเบื้อง

เมื่อเข้าสู่ไทล์ที่กำลังจะมาถึง ให้ใช้รูปแบบใดรูปแบบหนึ่งต่อไปนี้:

• สี: blue (1), red (2) หรือ white (3+)
• กลุ่มตัวเลข: 1 , 2 , 3 , 3+ , 6+ หรือเช่น 24,48,96 , 24 48 96
  • 3+ หมายความว่าอาจเป็น 3 หรือสูงกว่า ใช้สิ่งนี้กับ Threes ที่เก่ากว่า! ที่ไม่แสดงเครื่องหมาย "บวก" บนไทล์โบนัส
  • 6+ หมายความว่าเป็นไทล์โบนัสใดๆ ใช้สิ่งนี้หากไทล์ที่กำลังจะมาถึงคือ "+"
  • 24,48,96 หมายความว่าเป็นหนึ่งในสามนั้น ใช้สิ่งนี้กับ Threes รุ่นใหม่! ที่แสดงตัวเลือกที่ชัดเจนสำหรับค่าไทล์โบนัส