Algoritma pada permainan Othello
GAME OTHELLO
AI
dalam game ini memiliki kecepatan dalam taktik bermain sehingga mengharuskan
pemain untuk berfikir lebih cepat untuk menyusun strategi terbaik agar dapat
mendapatkan skor yang maksimal. Kecerdasan buatan merupakan kecerdasan yang
ditujukan oleh suatu entitas buatan, yang diciptakan dan diterapkan kedalam
sebuah mesin (computer) sehingga dapat melakukan perbuatan seperti manusia.
Dalam permainan ini, pemain diharuskan berfikir agar setiap langkahnya
memperoleh hasil solusi optimum. Kecerdasan pada computer mengarah pada
perhitungan atau komputasi, mereka tidak menggunakan intuisi yang menggunakan
perasaan. Namun, dalam hal komputasi, mereka lebih baik dibandingkan manusia.
Sama seperti manusia ketika computer diberikan papan reversy, mereka akan
melakukan perhitungan simulasi permainan untuk valid moves yang tersedia. 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.
