Agar dapat lebih leluasa dalam memakan pion lawan maka sedapat
mungkin seorang pemain harus menciptakan pion raja di pihaknya.Hal ini dapat terjadi
bila pion pemain mencapai ujung papan pada daerah lawan.Dengan menjadi raja, maka
pion bisa bergerak maju-mundur baik dalam melangkah maupun dalam memakan pion
musuh sedangkan pion biasa hanya dapat berjalan maju saja.
Baik pion raja
maupun pion biasa melakukan langkahnya dengan arah diagonal.
Algoritma
Minimax
Program permainan Checkers kami ini adalah implementasi dari algoritma
Minimax. Pada algoritma ini komputer akan membuat sebuah game tree yang berisi
kemungkinan-kemungkinan langkah yang bisa terjadi baik yang dilakukan oleh komputer
sendiri maupun oleh manusia. Kemudian dengan menggunakan suatu fungsi evaluasi
keadaan papan, maka komputer akan memilih suatu jalan yang terbaik dari semua
jalan yang terburuk yang mungkin terjadi (dengan anggapan bahwa lawan selalu berusaha
membuat keadaan komputer menjadi buruk dan lawan tidak pernah lengah). Algoritma
Minimax ini bersifat recursive sehingga game tree yang dihasilkan akan ditelusuri
secara Depth First Search (DFS). Karena menggunakan metode DFS ini maka komputer
bisa melakukan suatu cara optimasi pencarian langkah yaitu dengan menggunakan
Alpha-Beta Prunning.
Dengan Alpha-Beta Prunning maka komputer akan dapat
memangkas node-node tree yang tidak mungkin untuk dipilih/digunakan. Dengan demikian
maka game tree yang dihasilkan akan menjadi lebih ringkas sehingga jumlah ply
(level) dari game tree dapat diperbanyak. Jumlah ply yang lebih banyak akan membuat
komputer menjadi semakin cerdas karena dapat 'melihat' lebih jauh ke depan.
Fungsi Static Board Evaluator
Fungsi evaluasi yang digunakan oleh algoritma
Minimax untuk menilai kebaikan suatu state/kondisi disebut dengan fungsi Static
Board Evaluator (SBE). Fungsi SBE yang digunakan dalam program kami adalah
sebagai berikut:
- Setiap pion Checkers biasa di pihak kita (dalam
hal ini komputer) bernilai 100. Bila pion tersebut semakin dekat ke daerah musuh
akan bernilai semakin besar. Nilainya (100) akan dikalikan dengan kuadrat posisi
baris pion tersebut. Hal yang sebaliknya berlaku untuk pihak musuh (nilai pion
-100 dan dikalikan kuadrat posisi baris).
- Setiap pion raja yang berada
di pihak sendiri bernilai bernilai 200, akan tetapi bila raja berada di tepi papan
akan nilainya akan dikurangi 10 baik untuk tepi baris maupun tepi kolom. Hal sebaliknya
berlaku untuk pion raja pihak musuh.
- Nilai akhir papan akan ditambahkan
dengan suatu faktor random sehingga diharapkan pergerakan komputer tidak selalu
sama untuk setiap permainan.
