Algoritma Penyelesaian Game 2048

Bismillaah…

Mumpung masih hangat. Ada satu mobile game yang nampaknya sekarang sedang rame-ramenya dimainkan di jagat perangkat bergerak. Namanya 2048. Game ini ber-genre puzzle game dengan model tile berbentuk kotak dan berukuran 4×4. Secara tampilan mirip dengan game-game puzzle serupa (8-Puzzle, 15-Puzzle, dan sejenisnya), hanya saja berbeda dari sisi gameplay-nya.

Idenya sederhana, game ini mempunyai tile kotak yang bisa dalam kondisi kosong ataupun bernilai. Kotak-kotak bernilai tersebut dapat digerakkan (atas, kiri, kanan, bawah) dan dapat menempati kotak yang masih kosong. Misinya adalah pengguna ditantang untuk menggabungkan nilai-nilai tersebut hingga mencapai angka 2048. Aturannya, hanya kotak yang bernilai sama besar yang boleh digabung menjadi satu kotak. Sedangkan interaksi pengguna cukup dengan melakukan swipe ke arah atas, kanan, kiri, atau bawah sesuai pergerakan kotak bernilai yang diinginkan. Permainan berakhir (game over) jika kotak sudah penuh angka dan sudah tidak dapat digerakkan ke mana-mana. Penasaran? Langsung menuju TKP-nya saja.

Nah, sekarang saya hanya akan sedikit membahas algoritma penyelesaian game ini dengan cara saya. Bukan bermaksud agar Anda kecanduan memainkan game ini. Tapi siapa tahu ada yang tertarik untuk membuat implementasi algoritma penyelesaiannya. Seperti halnya yang sudah pernah saya bahas di blog ini terkait penyelesaian 8-puzzle problem [bagian 1], [bagian 2], dan [bagian 3].

Domain persoalan

Jumlah kotak	16
Interaksi	kanan | atas | kiri | bawah
Batasan nilai	2n, dengan n ≥ 1, dan n bilangan bulat positif

Aturan permainan

Misi permainan adalah menggabungkan kotak-kotak menjadi nilai yang lebih besar hanya dengan menggeser bidang permainan ke arah atas, bawah, kanan, atau kiri.

Yang boleh digabung hanyalah kotak-kotak yang bernilai sama dan berada pada posisi yang bersisian.

Contoh pada gambar di atas, posisi awal gambar pertama (sebelah kiri), lalu saya geser ke arah kiri, maka posisinya akan menjadi gambar kedua (sebelah kanan). Jika terdapat tiga kotak bersisian yang bernilai sama, maka yang digabung adalah dua pasang yang pertama. Contohnya ada pada gambar di bawah. Jika posisi pertama saya geser ke arah bawah, maka kedua angka 4 yang berada di kiri bawah akan tergabung menjadi 8.

Pada setiap pergeseran, akan dibangkitkan satu kotak bernilai 2 atau 4 (kemungkinan lebih banyak nilai 2 yang keluar) dengan posisi acak di tempat yang masih kosong.

Goal

1. Mencapai nilai 2048.

2. Menggabungkan nilai sebesar-besarnya untuk memperoleh skor setinggi-tingginya.

Pendekatan “cara saya”

Dari beberapa kali percobaan, ternyata ada kecenderungan bahwa game 2048 ini dapat diselesaikan dengan model stack. Maksudnya, kita akan semakin sulit menggabungkan kotak yang bernilai besar, karena nilai baru yang muncul secara acak hanyalah di kisaran 2 atau 4. Jadi, sebisa mungkin kotak-kotak tersebut disusun berdasar nilainya. Nilai yang paling besar berada pada posisi paling dalam pada urutan stack.

Berikut langkah-langkah yang dapat dijadikan acuan untuk menyusun stack: 1. Tentukan satu sisi yang akan dijadikan point of gravity dari stack. Biasanya saya memilih sisi bawah. Perlu diingat, sekali sisi ini dipilih, maka tidak boleh sekalipun melakukan pergeseran dengan arah yang berlawanan. Misal: yang dipilih adalah sisi bawah, maka pergeseran ke arah atas hukumnya dilarang. 2. Ketika satu sisi point of gravity terpilih, maka otomatis akan terbentuk layer tumpukan stack dari yang paling dalam hingga paling atas (ada 4 layer). Jadikan layer ini sebagai aturan prioritas pemilihan arah pergeseran. Karena berbentuk stack, maka prioritas paling tinggi adalah penggabungan nilai ke arah layer paling bawah. Misal: jika dihadapkan pada opsi seperti gambar di bawah kiri, maka saya akan memilih untuk menggabungkan kedua angka 8 yang ada di kolom 4 dari kiri sebelah bawah, daripada kedua angka 8 di baris 2 dari bawah sebelah kanan.

3. Aturan prioritas juga diterapkan untuk masing-masing layer. Prioritas paling tinggi adalah bagian pinggir pojok. Karena bagian pinggir akan lebih kecil kemungkinannya untuk bersisian dengan angka baru hasil proses acak. Sederhananya, begitu mendapat angka terbesar, taruh di bagian pinggir atau pojok.

4. Hindari kasus “terkunci“, yaitu kasus dimana sudah tidak ada lagi kotak-kotak yang dapat digeser ke arah selain arah larangan yang dijelaskan pada poin 1. Kalau nilai-nilainya masih belum terlalu besar seperti contoh di bawah, masih mungkin bisa diatasi dengan mengejar ketertinggalan nilai untuk nilai baru yang pasti akan muncul di bagian bawah posisi stack. Tapi kalau sudah terlalu besar, maka akan meninggalkan satu kotak yang tidak berguna di bagian bawah stack. Untuk menghindari kasus ini, dapat dilakukan dengan menambah fungsi pengecualian prioritas untuk kondisi seperti ini.

Yaa, cara saya ini belum tentu merupakan cara yang paling efektif. Mungkin cara Anda bisa lebih manjur untuk menyelesaikan persoalan game 2048 ini. Tapi setidaknya dari penerapan cara saya di atas, sampai saat tulisan ini dibuat, game 2048 yang saya mainkan belum menemui kasus game over.

Barangkali ada yang tertarik untuk mengimplementasikan algoritmanya ke salah satu platform atau bahasa pemrograman tertentu? 😀

Semoga bermanfaat dan CMIIW ya…

Btw, ternyata banyak diprotes karena menggunakan versi yang ada undo-nya. Gapapa lah. Lha wong cara saya ini juga belum tentu manjur kok. Ampun gans, saya mah apa atuh.

Kalau sempet ntar dianjutin lagi… 😛