Algoritma minimax merupakan algoritma yang diterapkan
dalam game yang
melibatkan dua pemain yang saling bergantian, seperti
tic-tac-toe, chess, go, othello dan
game
yang menggunakan strategi atau logika lainnya (Wijaya, 2010). Persamaan antara semua game
tersebut yaitu semua merupakan game logika dan game
dengan informasi yang lengkap. Ini berarti bahwa game
merupakan sekumpulan aturan main dan
dasar pemikiran yang logis. Adanya aturan main dan dasar pemikiran yang logis
tersebut, maka nantinya setiap
pemain dapat mengetahui semua
langkah yang mungkin dari pemain lawannya,
sehingga pemain bisa tetap “memantau” kondisi
permainan sewaktu game sedang berlangsung (Akbar, 2011).
Algoritma
minimax merupakan salah satu algoritma yang sering
digunakan untuk game kecerdasan buatan yang menggunakan teknik depth
first search (DFS) dalam pencariannya pada
pohon dengan kedalaman terbatas (Kusumadewi, 2003).
Algoritma minimax digunakan untuk memilih langkah terbaik,
dimana kedua pemain akan saling berusaha untuk
memenangkan permainan. Selain itu, algoritma minimax ini bekerja secara
rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum.
Algoritma minimax
mendeskripsikan kondisi apabila terdapat pemain yang
mengalami keuntungan, pemain lain akan mengalami kerugian senilai dengan
keuntungan yang diperoleh lawan dan sebaliknya.
Algoritma
minimax akan melakukan
pengecekan pada seluruh kemungkinan yang ada, sehingga akan menghasilkan pohon
permainan yang berisi semua kemungkinan permainan tersebut (Jannah, 2010). Dengan pohon permainan ini setiap pemain
mengetahui langkah-langkah yang mungkin diberikan pada situasi permainan saat
ini. Sehingga untuk setiap langkah dan semua langkah selanjutnya dapat
diketahui. Dalam repersentasi pohon pada algoritma minimax, terdapat dua
jenis simpul, yaitu simpul
min dan simpul max.
Max akan memilih langkah dengan nilai tertinggi dan min akan memilih langkah
dengan nilai terendah (Kusumadewi, 2003). Dalam penentuan keputusan max/min tersebut dibutuhkan
suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh
jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi
heuristik.
Fungsi heuristik yang
digunakan algoritma ini adalah fungsi heuristik statis (Kusumadewi, 2003). Fungsi
heuristik digunakan untuk mengevaluasi nilai sebagai nilai yang
merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut
dipilih. Dari nilai-nilai
heuristik inilah komputer akan menentukan simpul
mana dari pohon permainan yang akan dipilih, tentunya simpul
yang akan dipilih
tersebut adalah simpul dengan nilai
heuristik yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer (Akbar, 2007). Untuk proses dan
cara kerja algoritma yang lebih jelasnya lagi, dapat dilihat pada Gambar 2.10 yang merepresentasikan
cara kerja algoritma Minimax.
Gambar 2.10 Contoh Representasi
Cara Kerja pada Algoritma Minimax
Gambar 2.10 menunjukkan proses
pencarian dimulai dari jalur paling kiri terlebih dahulu, sehingga DFS akan
menelusuri simpul paling kiri bawah hingga paling kanan. DFS
akan menelusuri simpul paling kiri bawah
yaitu 5. Nilai 5 disimpan sebagai nilai maksimum sementara karena berada di level max, kemudian DFS melakukan backtrack dan menelusuri simpul yang bertetangga dengan simpul 5 yaitu simpul 2. Karena nilai 5
lebih besar dari nilai 2, maka nilai 2 tidak disimpan. Lalu DFS akan melakukan backtrack ke level min sehingga nilai 5
yang diperoleh akan disimpan sebagai nilai minimum sementara. Untuk simpul 1 dan 3, nilai 3
yang akan disimpan karena merupakan nilai maksimum di level max. Saat mencapai level min, sudah ada nilai
minimum sementara yaitu 5, namun karena nilai 3 lebih kecil daripada nilai 5,
maka nilai 5 akan digantikan dengan nilai 3. Nilai 3 akan disimpan sebagai nilai
maksimum sementara di level paling atas karena merupakan level max. Lalu penelusuran jalur kanan akan
dilakukan dengan cara yang sama seperti penelusuran jalur kiri sehingga
diperoleh nilai 6. Karena nilai maksimum sementara pada level paling atas adalah
nilai 3, maka nilai 3 akan digantikan dengan nilai 6 karena nilai 6 lebih besar
daripada nilai 3. Dengan demikian, jalur yang akan dipilih menggunakan
algoritma minimax
adalah jalur sebelah kanan, karena level atas
merupakan level max sehingga didapat nilai 6 sedangkan jika memilih jalur kiri, hanya akan didapat nilai 3.
terimakasih atas info nya. ini sangat membantu
BalasHapuscara penyelesaian masalah pada algoritma minimax seperti apa? Lebih ke hitung2an kah?
BalasHapus