Pertanyaan Apa algoritma optimal untuk game 2048?


Saya baru saja menemukan permainan 2048. Anda menggabungkan ubin serupa dengan memindahkannya ke salah satu dari empat arah untuk membuat ubin "lebih besar". Setelah setiap langkah, ubin baru muncul di posisi kosong acak dengan nilai baik 2 atau 4. Permainan berakhir ketika semua kotak diisi dan tidak ada gerakan yang bisa menggabungkan ubin, atau Anda membuat ubin dengan nilai 2048.

Satu, saya harus mengikuti strategi yang jelas untuk mencapai tujuan. Jadi, saya berpikir untuk menulis sebuah program untuk itu.

Algoritme saya saat ini:

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Apa yang saya lakukan adalah kapan saja, saya akan mencoba menggabungkan ubin dengan nilai-nilai 2 dan 4, itulah yang saya coba miliki 2 dan 4 ubin, seminimal mungkin. Jika saya mencobanya dengan cara ini, semua ubin lain secara otomatis digabungkan dan strategi tampak bagus.

Tapi, ketika saya benar-benar menggunakan algoritma ini, saya hanya mendapatkan sekitar 4000 poin sebelum game berakhir. AFAIK poin maksimum sedikit lebih dari 20.000 poin yang jauh lebih besar dari skor saya saat ini. Apakah ada algoritme yang lebih baik daripada yang di atas?


1753
2018-03-12 05:37


asal


Jawaban:


Saya mengembangkan penggunaan 2048 AI expectimax optimasi, bukan pencarian minimax yang digunakan oleh algoritma @ ovolve. AI hanya melakukan maksimalisasi atas semua gerakan yang mungkin, diikuti oleh ekspektasi atas semua petak genteng yang mungkin (dibobot oleh probabilitas ubin, yaitu 10% untuk 4 dan 90% untuk 2). Sejauh yang saya ketahui, tidak mungkin untuk memangkas optimisasi expectimax (kecuali untuk menghapus cabang yang sangat tidak mungkin), dan algoritma yang digunakan adalah pencarian kekuatan kasar yang dioptimalkan secara hati-hati.

Kinerja

AI dalam konfigurasi defaultnya (kedalaman pencarian maks 8) membutuhkan waktu dari 10ms hingga 200ms untuk melakukan pemindahan, tergantung pada kompleksitas posisi board. Dalam pengujian, AI mencapai tingkat pergerakan rata-rata 5-10 gerakan per detik selama keseluruhan permainan. Jika kedalaman pencarian dibatasi hingga 6 gerakan, AI dapat dengan mudah mengeksekusi 20+ gerakan per detik, yang menghasilkan beberapa menonton menarik.

Untuk menilai kinerja skor AI, saya menjalankan AI 100 kali (terhubung ke game browser melalui remote control). Untuk setiap petak, berikut adalah proporsi gim di mana petak itu dicapai setidaknya satu kali:

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

Skor minimum atas semua run adalah 124024; skor maksimum yang dicapai adalah 794076. Skor median adalah 387222. AI tidak pernah gagal untuk mendapatkan ubin 2048 (sehingga tidak pernah kehilangan permainan bahkan sekali dalam 100 pertandingan); pada kenyataannya, itu mencapai 8192 ubin setidaknya sekali dalam setiap run!

Inilah tangkapan layar lari terbaik:

32768 tile, score 794076

Game ini mengambil 27830 bergerak lebih dari 96 menit, atau rata-rata 4,8 gerakan per detik.

Pelaksanaan

Pendekatan saya mengkodekan seluruh papan (16 entri) sebagai bilangan bulat 64-bit tunggal (di mana ubin adalah nybbles, yaitu 4-bit chunks). Pada mesin 64-bit, ini memungkinkan seluruh papan untuk diedarkan dalam satu mesin register.

Operasi pengalihan bit digunakan untuk mengekstrak baris dan kolom individual. Satu baris atau kolom adalah kuantitas 16-bit, sehingga tabel ukuran 65536 dapat menyandikan transformasi yang beroperasi pada satu baris atau kolom. Misalnya, langkah diimplementasikan sebagai 4 pencarian ke dalam "tabel efek pindah" yang telah diprediksi yang menggambarkan bagaimana setiap gerakan mempengaruhi satu baris atau kolom (misalnya, tabel "pindah ke kanan" berisi entri "1122 -> 0023" yang menjelaskan bagaimana baris [2,2,4,4] menjadi baris [0,0,4,8] ketika dipindahkan ke kanan).

Scoring juga dilakukan menggunakan pencarian tabel. Tabel berisi skor heuristik yang dihitung pada semua baris / kolom yang mungkin, dan skor yang dihasilkan untuk sebuah papan hanyalah jumlah dari nilai tabel di setiap baris dan kolom.

Representasi papan ini, bersama dengan pendekatan tabel lookup untuk gerakan dan scoring, memungkinkan AI untuk mencari sejumlah besar negara game dalam waktu singkat (lebih dari 10.000.000 negara permainan per detik pada satu inti laptop saya pertengahan 2011).

Pencarian expectimax itu sendiri dikodekan sebagai pencarian rekursif yang bergantian antara langkah-langkah "harapan" (menguji semua lokasi dan nilai bertunas genteng yang mungkin, dan membobot skor optimal mereka dengan probabilitas setiap kemungkinan), dan langkah "memaksimalkan" (menguji semua kemungkinan langkah) dan memilih satu dengan nilai terbaik). Pencarian pohon berakhir ketika melihat posisi yang sebelumnya dilihat (menggunakan tabel transposisi), saat mencapai batas kedalaman yang ditentukan sebelumnya, atau ketika mencapai keadaan papan yang sangat tidak mungkin (misalnya, dicapai dengan mendapatkan ubin 6 "4" berturut-turut dari posisi awal). Kedalaman pencarian tipikal adalah 4-8 gerakan.

Heuristik

Beberapa heuristik digunakan untuk mengarahkan algoritma optimasi menuju posisi yang menguntungkan. Pilihan heuristik yang tepat memiliki efek besar pada kinerja algoritma. Berbagai heuristik ditimbang dan digabungkan ke dalam skor posisi, yang menentukan seberapa "baik" posisi papan yang diberikan. Pencarian optimasi kemudian akan bertujuan untuk memaksimalkan skor rata-rata dari semua posisi dewan yang mungkin. Skor yang sebenarnya, seperti yang ditunjukkan oleh permainan, adalah tidak digunakan untuk menghitung skor papan, karena terlalu berat untuk ubin penggabungan (ketika penundaan penggabungan dapat menghasilkan manfaat besar).

Awalnya, saya menggunakan dua heuristik yang sangat sederhana, memberikan "bonus" untuk kotak terbuka dan memiliki nilai besar di tepinya. Heuristik ini dilakukan dengan cukup baik, sering mencapai 16384 tetapi tidak pernah mencapai 32768.

Petr Morávek (@xificurk) mengambil AI saya dan menambahkan dua heuristik baru. Heuristik pertama adalah penalti karena memiliki baris dan kolom non-monotonik yang meningkat ketika peringkat meningkat, memastikan bahwa deretan non-monotonik dalam jumlah kecil tidak akan sangat memengaruhi skor, tetapi baris non-monotonik dalam jumlah besar akan sangat merugikan skor. Heuristik kedua menghitung jumlah gabungan potensial (nilai yang sama) di samping ruang terbuka. Kedua heuristik ini berfungsi untuk mendorong algoritme ke arah papan monotonik (yang lebih mudah digabungkan), dan menuju posisi papan dengan banyak gabungan (mendorongnya untuk menyelaraskan gabungan jika mungkin untuk efek yang lebih besar).

Selanjutnya, Petr juga mengoptimalkan bobot heuristik menggunakan strategi "meta-optimasi" (menggunakan algoritme yang disebut CMA-ES), di mana bobot itu sendiri disesuaikan untuk mendapatkan skor rata-rata tertinggi.

Efek dari perubahan ini sangat signifikan. Algoritma pergi dari mencapai ubin 16384 sekitar 13% dari waktu untuk mencapai lebih dari 90% dari waktu, dan algoritma mulai mencapai 32768 lebih dari 1/3 dari waktu (sedangkan heuristik lama tidak pernah menghasilkan ubin 32768) .

Saya percaya masih ada ruang untuk perbaikan pada heuristik. Algoritma ini pasti belum "optimal", tetapi saya merasa sepertinya sudah cukup dekat.


Bahwa AI mencapai 32.768 ubin di lebih dari sepertiga dari game-nya adalah tonggak besar; Saya akan terkejut mendengar jika ada pemain manusia telah mencapai 32.768 pada game resmi (yaitu tanpa menggunakan alat seperti savestates atau undo). Saya pikir ubin 65536 berada dalam jangkauan!

Anda dapat mencoba AI untuk diri sendiri. Kode ini tersedia di https://github.com/nneonneo/2048-ai.


1130
2018-03-19 07:22



Saya adalah penulis program AI yang telah disebutkan orang lain di utas ini. Anda dapat melihat AI masuk tindakan atau baca sumber.

Saat ini, program ini mencapai sekitar 90% tingkat kemenangan yang berjalan di javascript di browser di laptop saya yang diberikan sekitar 100 milidetik waktu berpikir per gerakan, jadi sementara tidak sempurna (belum!) Kinerjanya cukup baik.

Karena permainan adalah ruang status diskrit, informasi sempurna, permainan berbasis giliran seperti catur dan catur, saya menggunakan metode yang sama yang telah terbukti bekerja pada game-game tersebut, yaitu minimax  pencarian dengan pemangkasan alpha-beta. Karena sudah ada banyak info tentang algoritma itu di luar sana, saya hanya akan berbicara tentang dua heuristik utama yang saya gunakan di fungsi evaluasi statis dan yang meresmikan banyak intuisi yang diungkapkan orang lain di sini.

Monotonisitas

Heuristik ini mencoba untuk memastikan bahwa nilai-nilai ubin semuanya meningkat atau menurun sepanjang arah kiri / kanan dan atas / bawah. Heuristik ini saja menangkap intuisi yang banyak orang lain telah sebutkan, bahwa ubin berharga lebih tinggi harus dikelompokkan di sudut. Ini biasanya akan mencegah ubin yang lebih kecil yang berharga untuk menjadi yatim piatu dan akan membuat papan tetap teratur, dengan ubin yang lebih kecil mengalir masuk dan mengisi ke dalam ubin yang lebih besar.

Ini adalah screenshot dari grid monoton sempurna. Saya memperoleh ini dengan menjalankan algoritma dengan fungsi eval yang ditetapkan untuk mengabaikan heuristik lainnya dan hanya mempertimbangkan monotonisitas.

A perfectly monotonic 2048 board

Kelancaran

Heuristik di atas sendiri cenderung menciptakan struktur di mana ubin yang berdekatan mengalami penurunan nilai, tetapi tentu saja untuk menggabungkan, ubin yang berdekatan perlu menjadi nilai yang sama. Oleh karena itu, kehalusan heuristik hanya mengukur perbedaan nilai antara ubin yang berdekatan, mencoba untuk meminimalkan jumlah ini.

Seorang komentator di Hacker News memberi formalisasi yang menarik ide ini dalam hal teori grafik.

Berikut adalah screenshot dari grid yang sangat halus, milik garpu parodi yang sangat bagus ini.

A perfectly smooth 2048 board

Ubin Gratis

Dan akhirnya, ada penalti karena memiliki terlalu sedikit ubin gratis, karena opsi dapat cepat habis ketika papan permainan terlalu sempit.

Dan itu dia! Mencari melalui ruang permainan sambil mengoptimalkan kriteria ini menghasilkan kinerja yang sangat baik. Salah satu keuntungan menggunakan pendekatan umum seperti ini daripada strategi bergerak yang dikodekan secara eksplisit adalah bahwa algoritma tersebut sering dapat menemukan solusi yang menarik dan tidak terduga. Jika Anda melihatnya berjalan, ia akan sering membuat gerakan mengejutkan namun efektif, seperti tiba-tiba menukar dinding atau sudut mana yang dibangunnya.

Edit:

Berikut ini demonstrasi kekuatan pendekatan ini. Saya membuka nilai ubin (jadi terus berjalan setelah mencapai 2048) dan inilah hasil terbaik setelah delapan percobaan.

4096

Ya, itu adalah 4096 bersama 2048. =) Itu berarti mencapai ubin 2048 yang sulit dipahami tiga kali di papan yang sama.


1224
2018-03-13 20:04



EDIT: Ini adalah algoritma naif, pemodelan proses pemikiran sadar manusia, dan mendapat hasil yang sangat lemah dibandingkan dengan AI yang mencari semua kemungkinan karena hanya terlihat satu ubin di depan. Itu disampaikan pada awal waktu tanggapan.

Saya telah menyempurnakan algoritme dan mengalahkan game! Ini mungkin gagal karena nasib buruk yang sederhana mendekati akhir (Anda dipaksa untuk bergerak ke bawah, yang seharusnya tidak pernah Anda lakukan, dan ubin muncul di tempat tertinggi Anda seharusnya. Hanya mencoba untuk menjaga baris teratas terisi, jadi pindah ke kiri tidak mematahkan pola), tetapi pada dasarnya Anda akhirnya memiliki bagian tetap dan bagian ponsel untuk dimainkan. Ini adalah tujuan Anda:

Ready to finish

Ini adalah model yang saya pilih secara default.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

Sudut yang dipilih adalah sewenang-wenang, Anda pada dasarnya tidak pernah menekan satu kunci (gerakan terlarang), dan jika Anda melakukannya, Anda menekan sebaliknya lagi dan mencoba memperbaikinya. Untuk ubin masa depan, model selalu mengharapkan ubin acak berikutnya menjadi 2 dan muncul di sisi berlawanan dengan model saat ini (sementara baris pertama tidak lengkap, di sudut kanan bawah, setelah baris pertama selesai, di kiri bawah sudut).

Ini dia algoritma. Sekitar 80% menang (sepertinya selalu mungkin untuk menang dengan teknik AI yang lebih "profesional", saya tidak yakin tentang hal ini.)

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Beberapa petunjuk tentang langkah-langkah yang hilang. Sini: model change

Model telah berubah karena keberuntungan menjadi lebih dekat dengan model yang diharapkan. Model AI yang coba dicapai adalah

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

Dan rantai menuju ke sana telah menjadi:

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

Itu O mewakili ruang terlarang ...

Jadi itu akan menekan kanan, lalu ke kanan lagi, lalu (kanan atau atas tergantung di mana 4 telah dibuat) kemudian akan melanjutkan untuk menyelesaikan rantai sampai mendapat:

Chain completed

Jadi sekarang model dan rantai kembali ke:

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

Penunjuk kedua, itu memiliki nasib buruk dan tempat utamanya telah diambil. Sangat mungkin itu akan gagal, tetapi masih bisa mencapainya:

Enter image description here

Di sini model dan rantai adalah:

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Ketika berhasil mencapai 128, ia memperoleh seluruh baris diperoleh lagi:

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

119
2018-03-12 16:05



Saya menjadi tertarik dengan ide AI untuk game ini tidak ada kecerdasan yang dikodekan (Tidak ada heuristik, fungsi scoring, dll). AI seharusnya "tahu" hanya aturan main, dan "Cari tahu" permainan game. Hal ini berbeda dengan kebanyakan AI (seperti yang ada di thread ini) di mana permainan bermain pada dasarnya adalah kekuatan kasar yang dikendalikan oleh fungsi penilaian yang mewakili pemahaman manusia tentang permainan.

Algoritma AI

Saya menemukan algoritme permainan sederhana namun sangat bagus: Untuk menentukan langkah selanjutnya untuk papan yang diberikan, AI memainkan game ini menggunakan memori bergerak acak sampai pertandingan selesai. Ini dilakukan beberapa kali sambil melacak skor pertandingan akhir. Kemudian skor akhir rata-rata per langkah awal dihitung. Langkah awal dengan skor akhir rata-rata tertinggi dipilih sebagai langkah selanjutnya.

Dengan hanya 100 berjalan (yaitu dalam permainan memori) per gerakan, AI mencapai 2048 genteng 80% dari waktu dan 4096 genteng 50% dari waktu. Menggunakan 10000 run mendapatkan 2048 tile 100%, 70% untuk 4096 tile, dan sekitar 1% untuk ubin 8192.

Melihatnya dalam aksi

Skor terbaik yang dicapai ditampilkan di sini:

best score

Sebuah fakta menarik tentang algoritma ini adalah bahwa sementara permainan acak-bermain tidak mengherankan cukup buruk, memilih yang terbaik (atau paling buruk) bergerak mengarah ke permainan yang sangat bagus: Permainan AI yang khas dapat mencapai 70000 poin dan 3000 langkah terakhir, namun permainan putar acak in-memory dari posisi tertentu menghasilkan rata-rata 340 poin tambahan dalam sekitar 40 gerakan ekstra sebelum meninggal. (Anda dapat melihat ini sendiri dengan menjalankan AI dan membuka konsol debug.)

Grafik ini menggambarkan hal ini: Garis biru menunjukkan skor papan setelah setiap langkah. Garis merah menunjukkan algoritma terbaik Skor game akhir acak-lari dari posisi itu. Intinya, nilai-nilai merah "menarik" nilai-nilai biru ke atas ke arah mereka, karena mereka adalah tebakan terbaik algoritma. Sangat menarik untuk melihat garis merah hanya sedikit di atas garis biru di setiap titik, namun garis biru terus meningkat semakin banyak.

scoring graph

Saya merasa cukup mengejutkan bahwa algoritma tidak perlu benar-benar memperkirakan permainan yang bagus untuk memilih gerakan yang menghasilkannya.

Pencarian kemudian saya menemukan algoritma ini dapat diklasifikasikan sebagai Pencarian Pohon Monte Carlo Murni algoritma.

Implementasi dan Tautan

Pertama saya membuat versi JavaScript yang bisa terlihat beraksi di sini. Versi ini dapat menjalankan 100 berjalan dalam waktu yang layak. Buka konsol untuk info tambahan. (sumber)

Kemudian, untuk bermain-main lagi, saya menggunakan @nneonneo infrastruktur yang sangat dioptimalkan dan menerapkan versi saya di C ++. Versi ini memungkinkan hingga 100000 berjalan per langkah dan bahkan 1000000 jika Anda memiliki kesabaran. Instruksi bangunan disediakan. Ini berjalan di konsol dan juga memiliki remote control untuk memainkan versi web. (sumber)

Hasil

Anehnya, meningkatkan jumlah berjalan tidak secara drastis meningkatkan permainan game. Sepertinya ada batasan untuk strategi ini di sekitar 80000 poin dengan 4096 ubin dan semua yang lebih kecil, sangat dekat dengan pencapaian ubin 8192. Meningkatkan jumlah berjalan dari 100 hingga 100000 meningkatkan peluang untuk mencapai batas skor ini (dari 5% hingga 40%) tetapi tidak menerobosnya.

Menjalankan 10000 berjalan dengan peningkatan sementara ke 10.00000 posisi kritis dekat berhasil menembus penghalang ini kurang dari 1% dari waktu mencapai skor maksimum 129892 dan ubin 8192.

Perbaikan

Setelah menerapkan algoritme ini, saya mencoba banyak peningkatan termasuk menggunakan skor min atau maks, atau kombinasi dari min, max, dan avg. Saya juga mencoba menggunakan kedalaman: Alih-alih mencoba K berjalan per gerakan, saya mencoba K bergerak per gerakan daftar dari panjang yang diberikan ("atas, atas, kiri" misalnya) dan memilih langkah pertama dari daftar langkah penilaian terbaik.

Kemudian saya menerapkan pohon penilaian yang memperhitungkan probabilitas bersyarat untuk bisa bermain bergerak setelah daftar gerakan yang diberikan.

Namun, tidak satu pun dari ide-ide ini menunjukkan keuntungan nyata atas ide pertama yang sederhana. Saya meninggalkan kode untuk ide-ide ini yang dikomentari dalam kode C ++.

Saya menambahkan mekanisme "Penelusuran Mendalam" yang meningkatkan jumlah larik sementara menjadi 10.00000 saat salah satu lintasan berhasil secara tidak sengaja mencapai petak tertinggi berikutnya. Ini menawarkan peningkatan waktu.

Saya akan tertarik untuk mendengar jika ada yang memiliki ide perbaikan lain yang mempertahankan kemandirian domain AI.

2048 Varian dan Klon

Hanya untuk bersenang-senang, saya juga menerapkan AI sebagai bookmarklet, mengaitkan ke kontrol permainan. Ini memungkinkan AI untuk bekerja dengan gim orisinal dan banyak variannya.

Hal ini dimungkinkan karena sifat bebas-domain dari AI. Beberapa varian cukup berbeda, seperti klon Heksagonal.


114
2018-05-25 09:25



Saya menyalin di sini isi dari posting di blog saya


Solusi yang saya usulkan sangat sederhana dan mudah diterapkan. Meskipun, telah mencapai skor 131040. Beberapa tolok ukur kinerja algoritma disajikan.

Score

Algoritma

Algoritma penilaian heuristik

Asumsi di mana algoritma saya didasarkan agak sederhana: jika Anda ingin mencapai skor yang lebih tinggi, dewan harus disimpan serapi mungkin. Secara khusus, pengaturan optimal diberikan oleh urutan penurunan linear dan monoton dari nilai ubin. Intuisi ini akan memberi Anda juga batas atas untuk nilai ubin: s dimana n adalah jumlah ubin di papan tulis.

(Ada kemungkinan untuk mencapai ubin 131072 jika 4-ubin dibuat secara acak bukannya 2-ubin bila diperlukan)

Dua cara yang mungkin untuk mengatur papan ditunjukkan dalam gambar berikut:

enter image description here

Untuk menegakkan pentahbisan ubin dalam urutan menurun monotonik, skor yang dihitung sebagai jumlah dari nilai-nilai yang dilinearisasi di papan dikalikan dengan nilai-nilai dari urutan geometrik dengan rasio umum r <1.

s

s

Beberapa jalur linear dapat dievaluasi sekaligus, skor akhir akan menjadi skor maksimum dari setiap jalur.

Aturan keputusan

Aturan keputusan yang diterapkan tidak cukup cerdas, kode di Python disajikan di sini:

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Implementasi minmax atau Expectiminimax pasti akan meningkatkan algoritma. Tentunya lebih aturan keputusan yang canggih akan memperlambat algoritma dan akan membutuhkan waktu untuk diimplementasikan. Saya akan mencoba implementasi minimax dalam waktu dekat. (tetap disini)

Benchmark

  • T1 - 121 tes - 8 jalur berbeda - r = 0,125
  • T2 - 122 tes - 8 jalur berbeda - r = 0,25
  • T3 - 132 tes - 8 jalur berbeda - r = 0,5
  • T4 - 211 tes - 2 jalur berbeda - r = 0,125
  • T5 - 274 tes - 2 jalur berbeda - r = 0,25
  • T6 - 211 tes - 2 jalur berbeda - r = 0,5

enter image description here enter image description here enter image description here enter image description here

Dalam kasus T2, empat tes dalam sepuluh menghasilkan ubin 4096 dengan skor rata-rata s 42000

Kode

Kode dapat ditemukan di GiHub pada tautan berikut: https://github.com/Nicola17/term2048-AI Itu didasarkan pada term2048 dan itu ditulis dengan Python. Saya akan menerapkan versi yang lebih efisien dalam C ++ sesegera mungkin.


88
2018-03-26 22:13



Upaya saya menggunakan expectimax seperti solusi lain di atas, tetapi tanpa bitboards. Solusi Nneonneo dapat memeriksa 10 juta gerakan yang kira-kira kedalaman 4 dengan 6 ubin tersisa dan 4 gerakan mungkin (2 * 6 * 4)4. Dalam kasus saya, kedalaman ini terlalu lama untuk dijelajahi, saya menyesuaikan kedalaman pencarian expectimax sesuai dengan jumlah ubin gratis yang tersisa:

depth = free > 7 ? 1 : (free > 4 ? 2 : 3)

Skor papan dihitung dengan penjumlahan penjumlahan kuadrat dari jumlah ubin bebas dan produk titik dari grid 2D dengan ini:

[[10,8,7,6.5],
 [.5,.7,1,3],
 [-.5,-1.5,-1.8,-2],
 [-3.8,-3.7,-3.5,-3]]

yang memaksa untuk menata ubin secara menurun dalam semacam ular dari ubin kiri atas.

Kode di bawah atau jsbin:

  
var n = 4,
	M = new MatrixTransform(n);

var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles

var snake= [[10,8,7,6.5],
            [.5,.7,1,3],
            [-.5,-1.5,-1.8,-2],
            [-3.8,-3.7,-3.5,-3]]
snake=snake.map(function(a){return a.map(Math.exp)})

initialize(ai)

function run(ai) {
	var p;
	while ((p = predict(ai)) != null) {
		move(p, ai);
	}
	//console.log(ai.grid , maxValue(ai.grid))
	ai.maxValue = maxValue(ai.grid)
	console.log(ai)
}

function initialize(ai) {
	ai.grid = [];
	for (var i = 0; i < n; i++) {
		ai.grid[i] = []
		for (var j = 0; j < n; j++) {
			ai.grid[i][j] = 0;
		}
	}
	rand(ai.grid)
	rand(ai.grid)
	ai.steps = 0;
}

function move(p, ai) { //0:up, 1:right, 2:down, 3:left
	var newgrid = mv(p, ai.grid);
	if (!equal(newgrid, ai.grid)) {
		//console.log(stats(newgrid, ai.grid))
		ai.grid = newgrid;
		try {
			rand(ai.grid)
			ai.steps++;
		} catch (e) {
			console.log('no room', e)
		}
	}
}

function predict(ai) {
	var free = freeCells(ai.grid);
	ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3);
	var root = {path: [],prob: 1,grid: ai.grid,children: []};
	var x = expandMove(root, ai)
	//console.log("number of leaves", x)
	//console.log("number of leaves2", countLeaves(root))
	if (!root.children.length) return null
	var values = root.children.map(expectimax);
	var mx = max(values);
	return root.children[mx[1]].path[0]

}

function countLeaves(node) {
	var x = 0;
	if (!node.children.length) return 1;
	for (var n of node.children)
		x += countLeaves(n);
	return x;
}

function expectimax(node) {
	if (!node.children.length) {
		return node.score
	} else {
		var values = node.children.map(expectimax);
		if (node.prob) { //we are at a max node
			return Math.max.apply(null, values)
		} else { // we are at a random node
			var avg = 0;
			for (var i = 0; i < values.length; i++)
				avg += node.children[i].prob * values[i]
			return avg / (values.length / 2)
		}
	}
}

function expandRandom(node, ai) {
	var x = 0;
	for (var i = 0; i < node.grid.length; i++)
		for (var j = 0; j < node.grid.length; j++)
			if (!node.grid[i][j]) {
				var grid2 = M.copy(node.grid),
					grid4 = M.copy(node.grid);
				grid2[i][j] = 2;
				grid4[i][j] = 4;
				var child2 = {grid: grid2,prob: .9,path: node.path,children: []};
				var child4 = {grid: grid4,prob: .1,path: node.path,children: []}
				node.children.push(child2)
				node.children.push(child4)
				x += expandMove(child2, ai)
				x += expandMove(child4, ai)
			}
	return x;
}

function expandMove(node, ai) { // node={grid,path,score}
	var isLeaf = true,
		x = 0;
	if (node.path.length < ai.depth) {
		for (var move of[0, 1, 2, 3]) {
			var grid = mv(move, node.grid);
			if (!equal(grid, node.grid)) {
				isLeaf = false;
				var child = {grid: grid,path: node.path.concat([move]),children: []}
				node.children.push(child)
				x += expandRandom(child, ai)
			}
		}
	}
	if (isLeaf) node.score = dot(ai.weights, stats(node.grid))
	return isLeaf ? 1 : x;
}



var cells = []
var table = document.querySelector("table");
for (var i = 0; i < n; i++) {
	var tr = document.createElement("tr");
	cells[i] = [];
	for (var j = 0; j < n; j++) {
		cells[i][j] = document.createElement("td");
		tr.appendChild(cells[i][j])
	}
	table.appendChild(tr);
}

function updateUI(ai) {
	cells.forEach(function(a, i) {
		a.forEach(function(el, j) {
			el.innerHTML = ai.grid[i][j] || ''
		})
	});
}
updateUI(ai)

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai)
		updateUI(ai)
		requestAnimationFrame(runAI)
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
	}
}


hint.onclick = function() {
	hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)]
}
document.addEventListener("keydown", function(event) {
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai)
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai)
}


function stats(grid, previousGrid) {

	var free = freeCells(grid);

	var c = dot2(grid, snake);

	return [c, free * free];
}

function dist2(a, b) { //squared 2D distance
	return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2)
}

function dot(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		r += a[i] * b[i];
	return r
}

function dot2(a, b) {
	var r = 0;
	for (var i = 0; i < a.length; i++)
		for (var j = 0; j < a[0].length; j++)
			r += a[i][j] * b[i][j]
	return r;
}

function product(a) {
	return a.reduce(function(v, x) {
		return v * x
	}, 1)
}

function maxValue(grid) {
	return Math.max.apply(null, grid.map(function(a) {
		return Math.max.apply(null, a)
	}));
}

function freeCells(grid) {
	return grid.reduce(function(v, a) {
		return v + a.reduce(function(t, x) {
			return t + (x == 0)
		}, 0)
	}, 0)
}

function max(arr) { // return [value, index] of the max
	var m = [-Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] > m[0]) m = [arr[i], i];
	}
	return m
}

function min(arr) { // return [value, index] of the min
	var m = [Infinity, null];
	for (var i = 0; i < arr.length; i++) {
		if (arr[i] < m[0]) m = [arr[i], i];
	}
	return m
}

function maxScore(nodes) {
	var min = {
		score: -Infinity,
		path: []
	};
	for (var node of nodes) {
		if (node.score > min.score) min = node;
	}
	return min;
}


function mv(k, grid) {
	var tgrid = M.itransform(k, grid);
	for (var i = 0; i < tgrid.length; i++) {
		var a = tgrid[i];
		for (var j = 0, jj = 0; j < a.length; j++)
			if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j]
		for (; jj < a.length; jj++)
			a[jj] = 0;
	}
	return M.transform(k, tgrid);
}

function rand(grid) {
	var r = Math.floor(Math.random() * freeCells(grid)),
		_r = 0;
	for (var i = 0; i < grid.length; i++) {
		for (var j = 0; j < grid.length; j++) {
			if (!grid[i][j]) {
				if (_r == r) {
					grid[i][j] = Math.random() < .9 ? 2 : 4
				}
				_r++;
			}
		}
	}
}

function equal(grid1, grid2) {
	for (var i = 0; i < grid1.length; i++)
		for (var j = 0; j < grid1.length; j++)
			if (grid1[i][j] != grid2[i][j]) return false;
	return true;
}

function conv44valid(a, b) {
	var r = 0;
	for (var i = 0; i < 4; i++)
		for (var j = 0; j < 4; j++)
			r += a[i][j] * b[3 - i][3 - j]
	return r
}

function MatrixTransform(n) {
	var g = [],
		ig = [];
	for (var i = 0; i < n; i++) {
		g[i] = [];
		ig[i] = [];
		for (var j = 0; j < n; j++) {
			g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left]
			ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations
		}
	}
	this.transform = function(k, grid) {
		return this.transformer(k, grid, g)
	}
	this.itransform = function(k, grid) { // inverse transform
		return this.transformer(k, grid, ig)
	}
	this.transformer = function(k, grid, mat) {
		var newgrid = [];
		for (var i = 0; i < grid.length; i++) {
			newgrid[i] = [];
			for (var j = 0; j < grid.length; j++)
				newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]];
		}
		return newgrid;
	}
	this.copy = function(grid) {
		return this.transform(3, grid)
	}
}
body {
	text-align: center
}
table, th, td {
    border: 1px solid black;
    margin: 5px auto;
}
td {
    width: 35px;
    height: 35px;
    text-align: center;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



Saya pikir saya menemukan sebuah algoritma yang bekerja cukup baik, karena saya sering mencapai nilai lebih dari 10.000, pribadi terbaik saya adalah sekitar 16000. Solusi saya tidak bertujuan menyimpan angka terbesar di sudut, tetapi untuk tetap di baris atas.

Silakan lihat kode di bawah ini:

while( !game_over ) {
    move_direction=up;
    if( !move_is_possible(up) ) {
        if( move_is_possible(right) && move_is_possible(left) ){
            if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) 
                move_direction = left;
            else
                move_direction = right;
        } else if ( move_is_possible(left) ){
            move_direction = left;
        } else if ( move_is_possible(right) ){
            move_direction = right;
        } else {
            move_direction = down;
        }
    }
    do_move(move_direction);
}

25
2018-03-12 18:57



Saya adalah pengarang dari 2048 pengendali yang mendapat nilai lebih baik daripada program lain yang disebutkan di utas ini. Implementasi pengontrol yang efisien tersedia di github. Di repo terpisah ada juga kode yang digunakan untuk melatih fungsi evaluasi negara pengendali. Metode pelatihan dijelaskan dalam kertas.

Pengontrol menggunakan pencarian expectimax dengan fungsi evaluasi negara yang dipelajari dari awal (tanpa keahlian 2048 manusia) oleh varian belajar perbedaan temporal (teknik pembelajaran penguatan). Fungsi nilai-negara menggunakan jaringan n-tuple, yang pada dasarnya merupakan fungsi linear tertimbang dari pola yang diamati di papan tulis. Itu melibatkan lebih dari 1 miliar bobot, secara keseluruhan.

Kinerja

Dengan 1 gerakan / s: 609104 (Rata-rata 100 pertandingan)

Dengan 10 gerakan / s: 589355 (300 game rata-rata)

Pada 3-lapis (sekitar 1500 gerakan / detik): 511759 (1000 game rata-rata)

Statistik ubin untuk 10 gerakan / s adalah sebagai berikut:

2048: 100%
4096: 100%
8192: 100%
16384: 97%
32768: 64%
32768,16384,8192,4096: 10%

(Baris terakhir berarti memiliki ubin yang diberikan pada saat yang sama di papan).

Untuk 3-lapis:

2048: 100%
4096: 100%
8192: 100%
16384: 96%
32768: 54%
32768,16384,8192,4096: 8%

Namun, saya tidak pernah melihat itu mendapatkan ubin 65536.


25
2017-12-21 10:49



Sudah ada implementasi AI untuk game ini: sini. Kutipan dari README:

Algoritma ini adalah kedalaman kedalaman mendalam pencarian alpha-beta pertama. Fungsi evaluasi mencoba untuk menjaga baris dan kolom monotonik (baik semua menurun atau meningkat) sambil meminimalkan jumlah ubin di grid.

Ada juga diskusi tentang ycombinator tentang algoritma ini yang mungkin berguna bagi Anda.


21
2018-03-13 09:16