Apa algoritma optimal untuk game 2048?

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

Pertama, saya harus mengikuti strategi yang jelas untuk mencapai tujuan. Jadi, saya berpikir untuk menulis 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 pada titik mana pun, saya akan mencoba untuk menggabungkan petak dengan nilai-nilai 2dan 4, yaitu, saya mencoba untuk memiliki 2dan 4petak, seminimal mungkin. Jika saya mencobanya dengan cara ini, semua ubin lainnya secara otomatis akan digabung dan strateginya tampak bagus.

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

Saya mengembangkan AI 2048 menggunakan expectimax optimasi, bukan Minimax pencarian yang digunakan oleh algoritma @ ovolve ini. AI hanya melakukan pemaksimalan atas semua gerakan yang mungkin, diikuti oleh ekspektasi atas semua kemungkinan ubin (ditimbang dengan probabilitas ubin, yaitu 10% untuk 4 dan 90% untuk 2). Sejauh yang saya ketahui, tidak mungkin untuk memangkas optimisasi ekspektasi (kecuali untuk menghapus cabang yang sangat tidak mungkin), dan algoritma yang digunakan adalah pencarian brute force yang dioptimalkan dengan hati-hati.

Performa

AI dalam konfigurasi default-nya (kedalaman pencarian maksimum 8) memakan waktu mulai dari 10 ms hingga 200 ms untuk menjalankan gerakan, tergantung pada kompleksitas posisi board. Dalam pengujian, AI mencapai tingkat gerakan rata-rata 5-10 bergerak per detik selama seluruh permainan. Jika kedalaman pencarian terbatas pada 6 gerakan, AI dapat dengan mudah mengeksekusi 20+ gerakan per detik, yang membuat beberapa tontonan menarik .

Untuk menilai kinerja skor AI, saya menjalankan AI 100 kali (terhubung ke game browser melalui remote control). Untuk setiap ubin, berikut adalah proporsi permainan yang ubinnya dicapai setidaknya satu kali:

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

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

Berikut screenshot tangkapan terbaik:

Game ini mengambil 27.830 gerakan selama 96 menit, atau rata-rata 4,8 bergerak per detik.

Penerapan

Pendekatan saya mengkodekan seluruh papan (16 entri) sebagai integer 64-bit tunggal (di mana ubin adalah nybbles, yaitu potongan 4-bit). Pada mesin 64-bit, ini memungkinkan seluruh papan untuk dilewatkan dalam register mesin tunggal.

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

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

Representasi dewan ini, bersama dengan pendekatan pencarian tabel untuk pergerakan dan penilaian, memungkinkan AI untuk mencari sejumlah besar status gim dalam waktu singkat (lebih dari 10.000.000 status gim per detik pada satu inti laptop pertengahan 2011 saya).

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

Heuristik

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

Awalnya, saya menggunakan dua heuristik yang sangat sederhana, memberikan "bonus" untuk kotak terbuka dan karena memiliki nilai besar di tepi. Heuristik ini berkinerja cukup baik, seringkali 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 baris non-monotonik dalam jumlah kecil tidak akan sangat mempengaruhi skor, tetapi baris non-monotonik dalam jumlah besar merusak skor secara substansial. Heuristik kedua menghitung jumlah gabungan potensial (nilai yang sama berbatasan) di samping ruang terbuka. Dua heuristik ini berfungsi untuk mendorong algoritma ke arah papan monoton (yang lebih mudah untuk digabung), dan ke arah posisi papan dengan banyak penggabungan (mendorongnya untuk menyelaraskan gabungan jika memungkinkan untuk efek yang lebih besar).

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

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

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

Bahwa AI mencapai 32768 ubin di lebih dari sepertiga dari gimnya adalah tonggak besar; Saya akan terkejut mendengar jika ada pemain manusia yang mencapai 32.768 pada permainan resmi (yaitu tanpa menggunakan alat seperti savestate atau undo). Saya pikir ubin 65536 berada dalam jangkauan!

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

Saya penulis program AI yang orang lain sebutkan di utas ini. Anda dapat melihat AI beraksi atau membaca sumbernya .

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

Karena gim ini adalah ruang keadaan diskrit, informasi sempurna, gim berbasis giliran seperti catur dan catur, saya menggunakan metode yang sama yang telah terbukti berhasil pada gim-gim tersebut, yaitu pencarian minimax 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 dalam fungsi evaluasi statis dan yang memformalkan banyak intuisi yang diungkapkan orang lain di sini.

Monotonisitas

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

Berikut adalah tangkapan layar dari kotak monoton sempurna. Saya memperoleh ini dengan menjalankan algoritma dengan fungsi eval diatur untuk mengabaikan heuristik lain dan hanya mempertimbangkan monotonisitas.

Kelancaran

Heuristik di atas saja cenderung membuat struktur di mana ubin yang berdekatan mengalami penurunan nilainya, tetapi tentu saja untuk bergabung, ubin yang berdekatan harus memiliki nilai yang sama. Oleh karena itu, kehalusan heuristik hanya mengukur perbedaan nilai antara ubin tetangga, mencoba untuk meminimalkan jumlah ini.

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

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

Ubin gratis

Dan akhirnya, ada penalti karena terlalu sedikit ubin gratis, karena opsi dapat dengan cepat habis ketika papan permainan menjadi 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 langkah yang dikodekan secara eksplisit adalah bahwa algoritme sering dapat menemukan solusi yang menarik dan tidak terduga. Jika Anda menontonnya berjalan, itu akan sering membuat gerakan mengejutkan tapi efektif, seperti tiba-tiba beralih dinding atau sudut mana ia membangun melawan.

Edit:

Berikut ini demonstrasi kekuatan dari pendekatan ini. Saya membuka nilai genteng (jadi terus setelah mencapai 2048) dan di sini adalah hasil terbaik setelah delapan percobaan.

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

Saya menjadi tertarik pada ide AI untuk game ini yang tidak mengandung kecerdasan hard-code (yaitu tidak ada heuristik, fungsi penilaian dll). AI harus "tahu" hanya aturan mainnya, dan "mencari tahu" permainannya. Ini berbeda dengan kebanyakan AI (seperti yang ada di utas ini) di mana permainan pada dasarnya adalah kekuatan kasar yang dikendalikan oleh fungsi penilaian yang mewakili pemahaman manusia tentang permainan.

Algoritma AI

Saya menemukan algoritma bermain sederhana namun mengejutkan baik: Untuk menentukan langkah selanjutnya untuk papan yang diberikan, AI memainkan permainan dalam memori menggunakan gerakan acak sampai permainan 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 berikutnya.

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

Lihat itu dalam aksi

Skor terbaik yang dicapai ditunjukkan di sini:

Fakta menarik tentang algoritme ini adalah bahwa meskipun permainan acak tidak terlalu buruk, memilih langkah terbaik (atau paling tidak buruk) mengarah ke permainan yang sangat baik: Permainan AI tipikal dapat mencapai 70000 poin dan 3000 langkah terakhir, namun permainan memori acak di dalam memori dari posisi mana pun menghasilkan rata-rata 340 poin tambahan dalam sekitar 40 gerakan ekstra sebelum mati. (Anda dapat melihatnya sendiri dengan menjalankan AI dan membuka konsol debug.)

Grafik ini menggambarkan poin ini: Garis biru menunjukkan skor papan setelah setiap gerakan. Garis merah menunjukkan skor akhir permainan run-run algoritma terbaik dari posisi itu. Pada dasarnya, nilai merah adalah "menarik" 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.

Saya merasa cukup mengejutkan bahwa algoritma tidak perlu benar-benar melihat permainan yang baik untuk memilih langkah yang menghasilkannya.

Pencarian kemudian saya menemukan algoritma ini mungkin diklasifikasikan sebagai algoritma Pencarian Murni Monte Carlo Tree .

Implementasi dan Tautan

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

Kemudian, untuk bermain-main lagi, saya menggunakan infrastruktur @nneonneo yang sangat optimal dan mengimplementasikan versi saya di C ++. Versi ini memungkinkan hingga 100000 berjalan per gerakan 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 lari tidak secara drastis meningkatkan permainan. Tampaknya ada batas untuk strategi ini di sekitar 80000 poin dengan 4.096 petak dan semua yang lebih kecil, sangat dekat dengan pencapaian 8192 petak. Meningkatkan jumlah run dari 100 ke 100000 meningkatkan peluang untuk mencapai batas skor ini (dari 5% menjadi 40%) tetapi tidak menerobosnya.

Berlari 10.000 lari dengan kenaikan sementara menjadi 10.00000 di dekat posisi kritis yang berhasil menembus penghalang ini kurang dari 1% dari waktu mencapai skor maksimum 129892 dan 8192 ubin.

Perbaikan

Setelah menerapkan algoritma ini, saya mencoba banyak perbaikan termasuk menggunakan skor min atau max, atau kombinasi dari min, max, dan rata-rata. Saya juga mencoba menggunakan kedalaman: Alih-alih mencoba menjalankan K per langkah, saya mencoba gerakan K per daftar panjang tertentu ("atas, atas, kiri" misalnya) dan memilih langkah pertama dari daftar bergerak skor terbaik.

Kemudian saya menerapkan pohon penilaian yang memperhitungkan probabilitas kondisional untuk dapat memainkan gerakan setelah daftar langkah yang diberikan.

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

Saya memang menambahkan mekanisme "Pencarian Dalam" yang meningkatkan jumlah run sementara untuk 1000000 ketika salah satu berjalan berhasil secara tidak sengaja mencapai ubin tertinggi berikutnya. Ini menawarkan peningkatan waktu.

Saya akan tertarik untuk mendengar jika ada yang punya ide perbaikan lain yang menjaga independensi domain AI.

2048 Varian dan Klon

Hanya untuk bersenang-senang, saya juga menerapkan AI sebagai bookmarklet , mengaitkannya ke kontrol gim. Ini memungkinkan AI untuk bekerja dengan gim asli dan banyak variasinya .

Hal ini dimungkinkan karena sifat AI yang independen domain. Beberapa varian cukup berbeda, seperti klon Hexagonal.

EDIT: Ini adalah algoritma naif, memodelkan proses pemikiran manusia sadar, dan mendapatkan hasil yang sangat lemah dibandingkan dengan AI yang mencari semua kemungkinan karena hanya terlihat satu ubin di depan. Itu disampaikan di awal timeline respons.

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

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 sewenang-wenang, Anda pada dasarnya tidak pernah menekan satu tombol (langkah terlarang), dan jika Anda melakukannya, Anda menekan sebaliknya lagi dan mencoba memperbaikinya. Untuk ubin berikutnya, model selalu mengharapkan ubin acak berikutnya menjadi 2 dan muncul di sisi yang 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 memungkinkan 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 telah berubah karena keberuntungan karena lebih dekat dengan model yang diharapkan. Model AI sedang berusaha untuk mencapai

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

Dan rantai untuk sampai ke sana telah menjadi:

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

The Omewakili ruang dilarang ...

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:

Jadi sekarang model dan rantai kembali ke:

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

Pointer kedua, itu memiliki nasib buruk dan tempat utamanya telah diambil. Kemungkinan itu akan gagal, tetapi masih bisa mencapainya:

Di sini model dan rantainya 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 yang diperoleh lagi:

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

Saya menyalin konten posting di blog saya di sini

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

Algoritma

Algoritma penilaian heuristik

Asumsi yang menjadi dasar algoritme saya agak sederhana: jika Anda ingin mencapai skor yang lebih tinggi, dewan harus dijaga 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: mana n adalah jumlah ubin di papan tulis.

(Ada kemungkinan untuk mencapai ubin 131072 jika 4-ubin dihasilkan secara acak, bukan 2-ubin bila diperlukan)

Dua kemungkinan cara mengatur papan ditunjukkan pada gambar berikut:

Untuk menegakkan penahbisan ubin dalam urutan menurun monoton, skor si dihitung sebagai jumlah dari nilai-nilai linierisasi di papan dikalikan dengan nilai-nilai urutan geometri dengan rasio umum r <1.

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

Aturan keputusan

Aturan keputusan yang diterapkan tidak cukup pintar, kode dalam 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 algoritme. Jelas aturan keputusan yang lebih canggih akan memperlambat algoritme dan akan membutuhkan waktu untuk diimplementasikan. Saya akan mencoba implementasi minimax dalam waktu dekat. (tetap disini)

Tolok ukur

• T1 - 121 tes - 8 jalur yang 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

Dalam kasus T2, empat tes dalam sepuluh menghasilkan 4.096 ubin dengan skor rata-rata 42.000

Kode

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

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

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

Skor papan dihitung dengan jumlah kuadrat tertimbang dari jumlah ubin gratis 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 mengatur ubin turun dalam semacam ular dari ubin kiri atas.

kode di bawah atau di github :

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);
updateHint(predict(ai));

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


function updateHint(dir) {
	hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(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 {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}

<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

Saya penulis 2048 controller yang mendapat skor lebih baik daripada program lain yang disebutkan di utas ini. Implementasi kontroler yang efisien tersedia di github . Dalam repo terpisah ada juga kode yang digunakan untuk melatih fungsi evaluasi keadaan pengontrol. Metode pelatihan dijelaskan dalam makalah ini .

Pengontrol menggunakan pencarian ekspektasi dengan fungsi evaluasi keadaan yang dipelajari dari awal (tanpa keahlian manusia 2048) oleh varian pembelajaran perbedaan temporal (teknik pembelajaran penguatan). Fungsi state-value menggunakan jaringan n-tuple , yang pada dasarnya adalah fungsi linear dari pola yang diamati di papan tulis. Ini melibatkan lebih dari 1 miliar bobot , secara total.

Performa

Dengan 1 gerakan / gerakan: 609104 (rata-rata 100 game)

Pada 10 gerakan / s: 589355 (rata-rata 300 pertandingan)

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

Statistik ubin untuk 10 gerakan 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 tulis).

Untuk 3-lapis:

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

Namun, saya belum pernah melihatnya memperoleh ubin 65536.

Saya pikir saya menemukan sebuah algoritma yang bekerja dengan sangat baik, karena saya sering mencapai skor lebih dari 10.000, yang terbaik untuk pribadi saya adalah sekitar 16000. Solusi saya tidak bertujuan untuk menjaga 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);
}

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

Algoritma ini memperdalam pencarian iteratif mendalam iteratif pertama. Fungsi evaluasi mencoba untuk menjaga baris dan kolom monoton (baik semua menurun atau meningkat) sambil meminimalkan jumlah ubin di kisi.

Ada juga diskusi tentang Peretas Berita tentang algoritma ini yang mungkin bermanfaat bagi Anda.

Algoritma

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Evaluasi

Evaluation =
    128 (Constant)
    + (Number of Spaces x 128)
    + Sum of faces adjacent to a space { (1/face) x 4096 }
    + Sum of other faces { log(face) x 4 }
    + (Number of possible next moves x 256)
    + (Number of aligned values x 2)

Rincian Evaluasi

128 (Constant)

Ini adalah konstanta, digunakan sebagai garis dasar dan untuk kegunaan lain seperti pengujian.

+ (Number of Spaces x 128)

Semakin banyak ruang membuat keadaan lebih fleksibel, kita kalikan dengan 128 (yang merupakan median) karena kisi yang diisi dengan 128 wajah adalah keadaan optimal yang tidak mungkin.

+ Sum of faces adjacent to a space { (1/face) x 4096 }

Di sini kita mengevaluasi wajah yang memiliki kemungkinan untuk bergabung, dengan mengevaluasinya mundur, ubin 2 menjadi nilai 2048, sedangkan ubin 2048 dievaluasi 2.

+ Sum of other faces { log(face) x 4 }

Di sini kita masih perlu memeriksa nilai-nilai yang ditumpuk, tetapi dengan cara yang lebih rendah yang tidak mengganggu parameter fleksibilitas, jadi kita memiliki jumlah {x dalam [4,44]}.

+ (Number of possible next moves x 256)

Suatu negara lebih fleksibel jika memiliki lebih banyak kebebasan dari kemungkinan transisi.

+ (Number of aligned values x 2)

Ini adalah pemeriksaan yang disederhanakan dari kemungkinan memiliki penggabungan dalam kondisi itu, tanpa membuat pandangan ke depan.

Catatan: Konstanta dapat di-tweak ..

Ini bukan jawaban langsung untuk pertanyaan OP, ini lebih merupakan barang (percobaan) yang saya coba sejauh ini untuk menyelesaikan masalah yang sama dan memperoleh beberapa hasil dan memiliki beberapa pengamatan yang ingin saya bagikan, saya ingin tahu apakah kita dapat memiliki beberapa wawasan lebih lanjut dari ini.

Saya baru saja mencoba implementasi minimax saya dengan pemangkasan alpha-beta dengan cut-tree depth cutoff pada 3 dan 5. Saya mencoba untuk memecahkan masalah yang sama untuk grid 4x4 sebagai tugas proyek untuk kursus edX ColumbiaX: CSMM.101x Artificial Intelligence ( AI) .

Saya menerapkan kombinasi cembung (mencoba bobot heuristik berbeda) dari beberapa fungsi evaluasi heuristik, terutama dari intuisi dan dari yang dibahas di atas:

1. Monotonisitas
2. Ruang kosong tersedia

Dalam kasus saya, pemutar komputer benar-benar acak, tetapi saya masih mengasumsikan pengaturan permusuhan dan menerapkan agen pemain AI sebagai pemain maks.

Saya memiliki kotak 4x4 untuk bermain game.

Pengamatan:

Jika saya menetapkan terlalu banyak bobot pada fungsi heuristik pertama atau fungsi heuristik kedua, kedua kasus skor yang didapat pemain AI rendah. Saya bermain dengan banyak kemungkinan tugas berat untuk fungsi heuristik dan mengambil kombinasi cembung, tetapi sangat jarang pemain AI mampu mencetak 2048. Sebagian besar waktu itu berhenti pada 1024 atau 512.

Saya juga mencoba sudut heuristik, tetapi untuk beberapa alasan itu membuat hasilnya lebih buruk, ada intuisi mengapa?

Juga, saya mencoba untuk meningkatkan cut-off kedalaman pencarian dari 3 menjadi 5 (saya tidak bisa meningkatkannya lagi karena mencari bahwa ruang melebihi waktu yang diizinkan bahkan dengan pemangkasan) dan menambahkan satu lagi heuristik yang melihat nilai-nilai ubin yang berdekatan dan memberikan lebih banyak poin jika mereka bisa-gabung, tapi tetap saja saya tidak bisa mendapatkan 2048.

Saya pikir akan lebih baik menggunakan Expectimax daripada minimax, tetapi saya masih ingin menyelesaikan masalah ini dengan minimax saja dan mendapatkan skor tinggi seperti 2048 atau 4096. Saya tidak yakin apakah saya kehilangan sesuatu.

Animasi di bawah ini menunjukkan beberapa langkah terakhir dari permainan yang dimainkan oleh agen AI dengan pemutar komputer:

Setiap wawasan akan sangat membantu, terima kasih sebelumnya. (Ini adalah tautan posting blog saya untuk artikel: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve -2048-game-with-computer / dan video youtube: https://www.youtube.com/watch?v=VnVFilfZ0r4 )

Animasi berikut ini menunjukkan beberapa langkah terakhir dari permainan yang dimainkan di mana agen pemain AI bisa mendapatkan skor 2048, kali ini menambahkan heuristik nilai absolut juga:

Angka-angka berikut menunjukkan pohon permainan dieksplorasi oleh agen AI pemain dengan menganggap komputer sebagai musuh hanya untuk satu langkah:

Saya menulis sebuah pemecah 2048 di Haskell, terutama karena saya sedang belajar bahasa ini sekarang.

Implementasi saya terhadap game sedikit berbeda dari game sebenarnya, karena ubin baru selalu '2' (daripada 90% 2 dan 10% 4). Dan ubin baru itu tidak acak, tetapi selalu yang pertama tersedia dari kiri atas. Varian ini juga dikenal sebagai Det 2048 .

Sebagai akibatnya, pemecah ini bersifat deterministik.

Saya menggunakan algoritma lengkap yang mendukung ubin kosong. Kerjanya cukup cepat untuk kedalaman 1-4, tetapi pada kedalaman 5 itu menjadi agak lambat sekitar 1 detik per gerakan.

Di bawah ini adalah kode yang mengimplementasikan algoritma penyelesaian. Grid direpresentasikan sebagai array Integer 16-panjang. Dan penilaian dilakukan hanya dengan menghitung jumlah kotak kosong.

bestMove :: Int -> [Int] -> Int
bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x <- [0..3], takeTurn x grid /= [] ]

gridValue :: Int -> [Int] -> Int
gridValue _ [] = -1
gridValue 0 grid = length $ filter (==0) grid  -- <= SCORING
gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ]

Saya pikir ini cukup berhasil karena kesederhanaannya. Hasil yang dicapai ketika memulai dengan kisi kosong dan penyelesaian di kedalaman 5 adalah:

Move 4006
[2,64,16,4]
[16,4096,128,512]
[2048,64,1024,16]
[2,4,16,2]

Game Over

Kode sumber dapat ditemukan di sini: https://github.com/popovitsj/2048-haskell

Algoritma ini tidak optimal untuk memenangkan permainan, tetapi cukup optimal dalam hal kinerja dan jumlah kode yang dibutuhkan:

  if(can move neither right, up or down)
    direction = left
  else
  {
    do
    {
      direction = random from (right, down, up)
    }
    while(can not move in "direction")
  }

Banyak jawaban lain menggunakan AI dengan pencarian yang mahal secara komputasi tentang kemungkinan masa depan, heuristik, pembelajaran, dan sebagainya. Ini mengesankan dan mungkin cara yang benar untuk maju, tetapi saya ingin berkontribusi ide lain.

Modelkan jenis strategi yang digunakan pemain bagus dalam permainan.

Sebagai contoh:

13 14 15 16
12 11 10  9
 5  6  7  8
 4  3  2  1

Baca kotak dalam urutan yang ditunjukkan di atas sampai nilai kotak berikutnya lebih besar dari yang saat ini. Ini menyajikan masalah mencoba menggabungkan ubin lain dengan nilai yang sama ke dalam kotak ini.

Untuk mengatasi masalah ini, ada 2 cara untuk bergerak yang tidak tertinggal atau bertambah buruk dan memeriksa kedua kemungkinan dapat segera mengungkapkan lebih banyak masalah, ini membentuk daftar ketergantungan, setiap masalah yang membutuhkan masalah lain untuk diselesaikan terlebih dahulu. Saya pikir saya memiliki rantai ini atau dalam beberapa kasus pohon ketergantungan secara internal ketika memutuskan langkah selanjutnya, terutama ketika macet.

Ubin perlu bergabung dengan tetangga tetapi terlalu kecil: Gabungkan tetangga lain dengan yang ini.

Ubin yang lebih besar di jalan: Meningkatkan nilai ubin sekitarnya yang lebih kecil.

dll ...

Seluruh pendekatan kemungkinan akan lebih rumit dari ini, tetapi tidak jauh lebih rumit. Bisa jadi ini mekanis dalam merasakan kekurangan skor, bobot, neuron dan pencarian kemungkinan yang mendalam. Pohon kemungkinan secara kasar bahkan perlu cukup besar untuk membutuhkan percabangan sama sekali.