Board Game & Algoritma Min Max
Silvia
June 23, 2018
0 Comments
Nama : Silvia Wahyuningtias
Npm : 56415572
Kelas : 3IA21
Mata Kuliah : Pengantar Teknologi Game
Nama Dosen : Syefani Rahma Deski
Board game adalah bagian dari tabletop game yang
didalamnya terdapat peraturan cara bermain yang dilengkapi dengan beberapa
komponen seperti token, pion atau bidak yang dapat digerakkan diatas sebuah
“papan” khusus. Contohnya seperti yang sudah umum diketahui, yaitu Catur.
Sebuah permainan bagaimana mengatur strategi untuk “menangkap” pion Raja milik
lawan. Seperti kriteria board game yang sudah disebutkan, Catur terdiri dari
banyak pion (Raja, Ratu, Mentri, Kuda, dll) dan bisa digerakkan di atas
papan-khusus dengan motif kotak-kotak. Manikmaya akan membahas tentang sejarah board
game di lain kesempatan.
Algoritma minimax merupakan basis dari semua permainan
berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah
sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia sekalipun.
Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada sampai
akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon
permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource
yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut
berhubung kombinasi kemungkinan untuk sebuah permainan catur pada setiap
geraknya sangat banyak sekali. Keuntungan yang didapat dengan menggunakan
algoritma minimax yaitu algoritma minimax mampu menganalisis segala kemungkinan
posisi permainan untuk menghasilkan keputusan yang terbaik karena algoritma
minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat
lawan mengalami kerugian minimum. Semua strategi lawan akan dihitung dengan
algoritma yang sama dan seterusnya. Ini berarti, pada langkah pertama komputer
akan menganalisis seluruh pohon permainan. Dan untuk setiap langkahnya,
komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan
minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan
maksimum. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang
merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah
tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heurisitic untuk
mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang
akan terjadi jika langkah tersebut dipilih. Biasanya pada permainan tic tac toe
ini digunakan nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang,
seri, dan kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan
simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan
dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun
permainan ke hasil akhir yang menguntungkan bagi komputer.
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.
Sumber :
