Latar
Belakang
Perkembangan teknologi
dalam dunia komputer semakin hari semakin lebih maju, komputer yang dulunya
berfungsi sebagai alat hitung dan pengolah data, seiring perkembangan teknologi
modern komputer saat ini tidak hanya bertindak sebagai mesin yang hanya disuruh
namun mampu berfikir memberikan respon bagi pengguna. Kecerdasan buatan
dimanfaatkan dalam pembuatan game salah satunya adalah TIC-TAC-TOE, alasannya
adalah sebagai berikut :
a. Cukup mudah untuk
menentukan ukuran kemenangan atau kegagalan.
b.Memungkinkan untuk
dibandingkan dengan kemampuan manusia.
c.Pola peraturan permainan
TIC-TAC-TOE cukup dikenal dan mudah untuk dimainkan
Permainan
TIC-TAC-TOE
Permainan tic-tac-toe
merupakan permainan berjenis board-game berukuran 3x3 ataupun lebih. Pemain
harus mengisi sel-sel, sehingga karakter yang dimasukan pemain tersebut dapat
membentuk suatu garis lurus horizontal, vertikal, atau diagonal. Biasanya
karakter tersebut berupa tanda “X” dan “O” untuk membedakan antar pemain.
Permainan ini biasanya dimainkan ileh 2 orang, tetapi pada versi permainan
komputer, pemain lawan dapat digantikan oleh komputer. Hasil permaian dapat
menang, kalah, atau seri.
Algoritma
Minimax
Algoritma minimax
merupakan basis dari semua permainan berbasis AI. 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 sangat banyak sekali. Pada langkah pertama komputer akan
menganalisi seluruh pohon permainan, dan setiap langkahnya komputer akan memilih
langkah yang akan membuat lawan mendapatkan keuntungan minimum dan komputer itu
sendiri mendapatkan keuntungan maksimum. Pada permainan tic-tac-toe ini
digunakan nilai 1,0,-1 untuk mewakili hasil akhir permainan yaitu menang, seri,
kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana
dari pohon permainan yang akan dipilih. Garis besar algoritma minimax secara
umum:
“If ada langkah kemenangan
Then pilih langkah tersebut
Else if lawan mempunyai 2
spot terisi dalam satu garis dengan spot ketiga masih kosong Then tutup langkah
tersebut.
Else melangkah ke state
yang mempunyai kemungkinan menang tertinggi”.
Analisis
Pada permainan tic-tac-toe
menggunakan algoritma minimax, dimana AI akan menelusuri semua kemungkinan
langkah yang akan dilakukan oleh pemain. Sehingga AI akan selalu mengetahui
kemungkinan pemain untuk menang dan memblok semua langkah kemenangan pemain.
Dengan demikian permainan akan selalu seri apabila pemain cukup teliti dalam
menentukan langkah. Namun apabila pemain melakukan langkah yang salah, maka AI
akan langsung mengambil langkah yang mengarahkannya ke hasil akhir berupa
kemenangan atau seri.
Berikut adalah contoh
permainannya :
Saya memilih karakter"X", dan mendapat giliran pertama. Disini saya akan mengumpamakan "a" itu baris dan "b" itu kolom, jadi (a(baris),b(kolom)). Pertama saya memilih (a2,b2) dan komputer memilih (a2,b1).
Pada giliran berikutnya saya memilih (a1,b2) dan komputer memilih (a3,b2). komputer memilih (a3,b2) dikarenakan komputer mengetahui bahwa langkah kemenangan saya ada di (a3,b2).
Berikutnya saya memilih (a1,b1) dan disini saya memiliki 2 langkah kemenangan yaitu di (a1,b3) dan (a3,b3). komputer memilih (a3,b3) dan berarti langkah kemenangan saya ada di (a1,b3).
Karena disini saya memilih level kesulitan medium, maka tingkat ketelitian komputer masih rendah. Namun semakin tinggi level kesulitan yang kita mainkan makin sulit pula untuk kita memenangkan game ini.
Kesimpulan :
- Penerapan
algoritma minimax cukup bagus dan cocok untuk pengambilan keputusan oleh AI,
terutama dalam permainan non-player.
- Algoritma
minimax menggunakan konsep Dept First Search dalam pembentukan pohon solusi.
- Pohon
solusi dibentuk dari awal permainan sampai akhir permainan.
- Dengan
menggnakan algoritma minimax untuk AI dalam permainan tic-tac-toe sangat kecil
kemungkinan pemain untuk dapat menang
melawan AI tersebut.
Sumber :
- Khoirus Sholih,
2010.Jurnal Implementasi Teori Minimax pada Tic Tac Toe.Teknik Informatika.
Institut Teknologi Bandung.
- http://elib.unikom.ac.id/files/disk1/317/jbptunikompp-gdl-dickyherma-15803-6-jurnal.pdf
https://www.academia.edu/9991470/PAPER_IMPLEMENTASI_ALGORITMA_MINIMAX_PADA_PERMAINAN_TIC_TAC_TOE_5X5
0 komentar:
Posting Komentar