Analisa Game dan Algoritma pada Game

GAME OTHELLO

 

Permainan Othello dimainkan oleh dua orang pemain. Permainan ini dimainkan di atas papan arena permainan persegi yang terdiri dari kotak-kotak kecil, berukuran 8x8 kotak. Masing-masing pemain memiliki pin dengan warna yang berbeda, satu pemain berwarna hitam dan yang lainnya berwarna putih. Dalam game tersebut, tiap pemain berusaha untuk mengganti warna pin lawan menjadi warna pin miliknya dengan menjepit atau memblok pin – pin musuh baik itu secara vertikal, diagonal, maupun horizontal.

Dalam permainan ini, pemain diharuskan berfikir agar setiap langkahnya memperoleh hasil solusi optimum. Disinilah daya perhitungan yang besar sangat diperlukan. Pada dasarnya ketika diberikan sebuah susunan posisi papan tertentu, komputer menghitung nilai posisi tersebut menggunakan fitur-fitur yang dijelaskan pada artikel Strategi bermain reversy, seperti jumlah pin, penguasaan sudut/x-quare/c-square, jumlah pin stabil, mobility, jumlah pin tepi, parity, dan pola sisi/sudut.

● Algoritma Minimax

Dalam permainan ini, perhitungan setiap langkahnya menggunakan algoritma standar dibidang kecerdasan buatan yang sudah dikembangkan sejak lama yaitu Game Theory yaitu yang disebut dengan Algoritma Minimax. Sesuai dengan namanya, algoritma ini bergerak meminimalisasi kekalahan dan memaksimalkan kesempatan untuk menang. 

Pada kedalaman 1 dan kedalaman ganjil lainnya, posisi papan akan menentukan nilai untuk pemain yang akan melangkah saat ini. Sehingga di kedalaman ganjil ini algoritma minimax memilih langkah bernilai maksimal sebagai langkah terbaik. Namun sebaliknya, dikedalaman kedua dan kedalaman genap lainnya, posisi papan akan menentukan nilai untuk pemain lawan yang akan main berikutnya, sehingga dikedalaman genap ini algoritma minimax ini mencari langkah paling minimal untuk langkah terbaik. 

	B memilih B1	B memilih B2	B memilih B3
A memilih A1	+3	−2	+2
A memilih A2	−1	0	+4
A memilih A3	−4	−3	+1

             Ketika A memilih langkah A1 dilanjutkan dengan B memilih langkah B1, posisi papan yang terbentuk bernilai +3. Demikian pula untuk A1 → B2 nilainya -2, A1 → B3 nilainya +2 dst. Sekarang mari kita coba aplikasikan algoritma minimax untuk menghitung langkah terbaik bagi pemain A.

             Terhadap langkah A1 (kedalaman 1) misalnya valid moves pemain B adalah B1, B2 dan B3 (kedalaman 2), dan langkah terbaik menurut algoritma minimax didapat dengan mencari langkah bernilai minimal (karena di kedalaman 2), yaitu B2 (bernilai -2). Demikian pula terhadap langkah A2 yang terbaik bagi B adalah B1 (bernilai -1), dan terhadap A3 adalah B1 juga (bernilai -4). Selanjutnya, nilai untuk langkah pemain A (kedalaman 1) adalah nilai yang 'dikembalikan' dari pemain B di kedalaman 2, yaitu A1 adalah -2, A2 adalah -1, dan A3 adalah -4. Kemudian untuk kedalaman 1 ini algoritma minimax mencari nilai maksimal sebagai langkah terbaik, yaitu A2 (bernilai-1).

             Untuk kedalaman lebih dari dua, cara 'berpikir' algoritma minimax dapat digambarkan sebagai pohon permainan (game tree) seperti pada gambar di atas. Di lokasi paling dalam (disebut lokasi node daun atau leaf node), dalam hal ini kedalaman 4, dilakukanlah perhitungan nilai posisi papan yang selanjutnya 'dikembalikan' ke node pada kedalaman di atasnya terus hingga sampai lokasi paling atas (di sebut akar atau root). Panah merah menunjukkan nilai yang dikembalikan dari langkah terbaik pilihan algoritma minimax ke kedalaman di atasnya. Demikianlah, kita dapat melihat algoritma minimax bergantian memilih langkah dengan nilai minimal dan maksimal sebagai langkah terbaik sesuai dengan kedalamannya. Dengan algoritma ini komputer dapat 'berpikir' sampai kedalaman tertentu untuk menentukan langkah terbaik untuk memenangkan permainan.

             Namun dalam penerapannya, algoritma minimax kini sudah jarang digunakan. Karena algoritma minimax memperhitungkan setiap valid moves yang ada sehingga akan memakan waktu yang lebih lama, kini terdapat algoritma yang dapat berfikir lebih cepat yang di kembangkan dari algoritma minimax yaitu algoritma AlphaBeta, Nagascout dll.

Sumber : http://hotsprot.blogspot.com/2012/05/algoritma-pada-permainan-othello.html