AI untuk game Bertiga! oleh Sirvo LLC. Anda bisa mendapatkan gamenya dari sini: http://asherv.com/threes/
Membangun AI ini adalah inspirasi bagi AI 2048 saya nanti, dan beberapa ide dari AI 2048 telah di-backport ke AI ini juga.
Meskipun saya belum secara resmi mengukur kinerja AI ini, saya tahu bahwa AI ini telah berhasil mencapai ubin 6144 beberapa kali, yang merupakan ubin tertinggi yang tersedia dalam game. (Ubin yang lebih tinggi dimungkinkan tetapi tidak mungkin, karena efek acak yang berat). Skor tertinggi (pada saat penulisan) adalah 775.524 poin:
AI ini jauh lebih eksperimental dibandingkan saudaranya yang lebih baru, AI 2048, karena kompleksitas Threes yang semakin meningkat! dan karena belum menerima banyak waktu pengembangan. Selanjutnya, Bertiga! secara umum merupakan target yang bergerak karena algoritme pembuatan ubin acak terkadang diubah, sehingga memerlukan perubahan pada AI.
Algoritme untuk AI ini pada dasarnya sudah dirinci dalam jawaban StackOverflow yang menjelaskan AI 2048 saya. Intinya, ini mengimplementasikan pencarian bruteforce yang sangat optimal pada pohon permainan (semua kemungkinan gerakan, nilai ubin yang muncul, dan nilai ubin), menggunakan optimasi ekspektasi untuk menggabungkan hasil dan menemukan gerakan "terbaik".
Threes AI ini sebenarnya lebih canggih daripada AI 2048 dalam beberapa hal: terutama, AI ini bertanggung jawab atas "dek" ubin yang akan datang (proses yang terdokumentasi dengan baik dalam memilih ubin masuk secara acak), dan menangani dengan baik semua kemungkinan lokasi pemijahan ubin berdasarkan gerakan yang dilakukan. Singkatnya: Threes AI ini dengan benar (sejauh pengetahuan saya) mengemulasi setiap detail game Threes sebagai bagian dari proses optimasi ekspektasi.
Cara termudah untuk menjalankan AI adalah dengan mengkloning salah satu cabang prebuilt/ yang sesuai dengan OS dan prosesor Anda. Cabang-cabang ini memiliki biner yang sudah dibuat sebelumnya di direktori bin/ .
Perhatikan bahwa Python "default" di Windows adalah 32-bit, sedangkan Python "default" di OS X dan Linux adalah 64-bit. Versi 32-bit diberi tag i386 sedangkan versi 64-bit diberi tag x86_64 .
Jika Anda ingin membuatnya sendiri dari sumbernya (misalnya jika Anda membuat perubahan), ikuti petunjuk di bawah.
Menjalankan
./configure
make
di sebuah terminal. Kompiler C++ yang relatif baru harus dapat membuat output.
Perhatikan bahwa Anda tidak melakukan make install ; program ini dimaksudkan untuk dijalankan dari direktori ini.
Anda memiliki beberapa pilihan, tergantung pada apa yang telah Anda instal.
Cygwin Murni: ikuti instruksi Unix/Linux/OS X di atas. DLL yang dihasilkan hanya dapat digunakan dengan program Cygwin, jadi untuk menjalankan versi kontrol browser, Anda harus menggunakan Cygwin Python (bukan python.org Python). Untuk petunjuk langkah demi langkah, atas izin Tamas Szell (@matukaa), lihat dokumen ini.
Cygwin dengan MinGW: lari
CXX=x86_64-w64-mingw32-g++ CXXFLAGS='-static-libstdc++ -static-libgcc -D_WINDLL -D_GNU_SOURCE=1' ./configure ; make
dalam shell MinGW atau Cygwin untuk dibuat. DLL yang dihasilkan dapat digunakan dengan program non-Cygwin.
Visual Studio: buka prompt perintah Visual Studio, cd ke direktori threes-ai, dan jalankan make-msvc.bat .
Anda memerlukan Python 2.7, NumPy dan PIL untuk menjalankan program Python.
Jalankan bin/threes jika Anda ingin melihat AI beraksi sendiri.
Ada beberapa versi Threes berbasis web, tetapi saya ingin membuat AI bermain melawan aplikasi sebenarnya. Jadi, saya membuat program "asisten" untuk perangkat Android, bernama android_assistant.py , yang berkomunikasi dengan telepon melalui ADB dan melakukan perpindahan sepenuhnya secara otomatis. Ini hanya memerlukan izin USB ADB (akses pengembang standar), dan tidak memerlukan rooting atau modifikasi lain pada perangkat atau aplikasi. Ia menggunakan utilitas screencap Android standar untuk mendapatkan status permainan (yang terlihat), menghitung gerakan optimal, kemudian menggunakan subsistem peristiwa masukan Linux untuk menghasilkan peristiwa gesek.
Untuk menggunakan android_assistant.py , Anda perlu mengonfigurasi subsistem OCR untuk perangkat Anda. Anda juga harus merekam acara gesek untuk diputar ulang. Saat ini, dua perangkat dikonfigurasi: LG Nexus 5 dan OnePlus One (sesuai dengan ponsel yang saya uji). Patch dipersilakan untuk menambahkan lebih banyak ponsel.
Untuk mengkonfigurasi sistem OCR, Anda harus menambahkan entri di ocr/devices.py yang sesuai dengan perangkat Anda. Nama model dapat diperoleh hanya dengan menjalankan android_assistant.py saat terhubung ke perangkat (harus terjadi kesalahan dengan nama model yang diharapkan). Pada dasarnya, Anda perlu mengambil tangkapan layar permainan dan mendapatkan posisi panel "ubin yang akan datang", serta posisi dan jarak kisi ubin. (Bagian ini mungkin memerlukan lebih banyak otomatisasi dan/atau penyederhanaan!)
Untuk merekam peristiwa, cukup jalankan python -m android.inputemu --record up down left right dan jalankan gerakan yang sesuai di ponsel Anda saat diminta.
Asisten manual adalah Threes untuk keperluan umum! asisten yang bekerja dengan implementasi Threes!. Anda memberi tahu papan dan kumpulan ubin yang akan datang, dan asisten menghitung langkah terbaik.
Jalankan manual_assistant.py untuk memulai asisten manual.
Perhatikan bahwa asisten manual mengharapkan untuk melihat gerakan berurutan. Jika Anda melompat ke depan (melakukan gerakan tanpa asisten), keluar dari asisten dengan menekan Ctrl+C dan mulai lagi. Jika tidak, Anda mungkin menerima pesan kesalahan seperti "situasi yang tidak mungkin" jika Anda memasuki papan yang tidak berurutan dengan papan sebelumnya.
Saat memasuki papan berikutnya, Anda dapat menggunakan spasi, baris baru, dan/atau koma untuk memisahkan ubin. Baca dari kiri ke kanan, lalu atas ke bawah. Masukkan angka nol untuk ruang kosong. Contoh masukan:
Menggunakan koma dan baris baru:
96,2,3,0
2,1,1,0
2,1,0,0
0,0,2,0
Menggunakan koma saja:
96,2,3,0,2,1,1,0,2,1,0,0,0,0,2,0
Menggunakan spasi:
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
Anda juga dapat memasukkan "delta" dari papan sebelumnya. Tentukan baris atau kolom tempat ubin baru muncul, dan nilai ubin yang muncul (Anda dapat menghilangkan ini jika hanya ada satu kemungkinan ubin baru yang terakhir dipindahkan, misalnya jika warnanya merah atau biru). Tentukan juga gerakan yang Anda lakukan jika itu bukan gerakan yang disarankan oleh AI.
Kolom dan baris diberi nomor dari kiri ke kanan dan dari atas ke bawah: kolom 1 adalah kolom kiri dan baris 1 adalah baris atas.
Contohnya, jika papan digesek ke atas, dan berpindah dari
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
ke
96 3 3 0
2 1 1 0
2 0 2 0
0 3 0 0
lalu Anda akan mengirim 2,3,up sebagai papan (di kolom ke-2, muncul angka 3). Jika AI merekomendasikan langkah up maka Anda dapat menghilangkannya dan mengirimkan 2,3 . Jika ubin yang akan datang diperkirakan 3, Anda dapat menghilangkan 3 dan mengirimkan 2 saja.
Dengan memasuki delta, Anda akan menghemat banyak waktu. Dalam kebanyakan kasus, Anda hanya perlu memasukkan satu nomor (kolom/baris yang diubah).
Saat memasukkan ubin yang akan datang, gunakan salah satu format berikut:
blue (1), red (2) atau white (3+)1 , 2 , 3 , 3+ , 6+ , atau misalnya 24,48,96 , 24 48 963+ berarti bisa jadi 3 atau lebih tinggi; gunakan ini dengan Threes yang lebih tua! yang tidak menunjukkan tanda "plus" pada ubin bonus6+ berarti ubin bonus apa pun; gunakan ini jika ubin berikutnya adalah "+"24,48,96 artinya salah satu dari ketiganya; gunakan ini dengan Threes yang lebih baru! yang menunjukkan kepada Anda opsi eksplisit untuk nilai ubin bonus.
