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
