BAB 6 - BOARD GAME dan ALGORITMA MINIMAX
PENGERTIAN BOARD GAME
Board
game adalah permainan yang dimainkan oleh dua orang atau lebih, berupa papan
permainan yang telah di desain sedemikian rupa sesuai jenis permainan, board
game bisa menggunakan koin, dadu, pion, kartu atau semacamnya yang digunakan
dengan cara tertentu, sesuai dengan peraturan tiap-tiap jenis board game.
Contohnya adalah game canddyland, chess, monopoly, scrabble, dan lain
sebgainya.
ALGORITMA MINIMAX
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.
Table
Transposition and Memory
Algoritma
dapat menggunakan tabel transposisi untuk menghindari melakukan pekerjaan ekstra
dalam mencari posisi board yang sama beberapa kali.
- Memori kerja posisi board sudah dikenal
- Menggunakan fungsi hash khusus desiderata: sebarkan posisi-posisi yang mirip seluas mungkin melalui kisaran nilai hash nilai hash yang banyak berubah saat berpindah dari papan bergerak mengalami perubahan yang sangat sedikit.
- Kunci zobrist adalah sekumpulan bit acak dari fixed-length pola yang tersimpan untuk setiap kemungkinan keadaan dari setiap lokasi yang mungkin ada pada board. Contoh: Catur memiliki 64 kotak, dan masing-masing persegi bisa kosong atau ada 1 dari 6 potongan berbeda di atasnya, masing-masing dua warna mungkin.Zobrist kunci harus seperti berikut : 64 2 (6 + 1) = 832 bit-string yang berbeda.
- Kunci Zobrist perlu diinisialisasi dengan bit-string acak dengan ukuran yang sesuai.
- Untuk setiap kotak yang tidak kosong, tombol Zobrist adalah mendongak dan XORed dengan jumlah hash yang berjalan.
- Zobrist Key dapat diperbarui secara bertahan
- Tabel hash menyimpan nilai yang terkait dengan posisi board • Gerakan terbaik dari posisi masing-masing board.
- Kedalaman digunakan untuk menghitung nilai
- Nilai yang akurat, atau kita dapat juga menyimpan nilai "fail-soft" yang dihasilkan darisebuah cabang yang dipangkas
- Nilai akurat atau nilai gagal-rendah (alpha pruned), atau nilai gagal-tinggi (beta pruned)
Source:
voice-teacher.blogspot.com ›
Pengayaan
http://abdulagisni.blogspot.com/2017/11/
8 Casino Stays | MapyRO
BalasHapusLooking 충청북도 출장마사지 for Casino Stays in Stays? 평택 출장안마 Compare reviews, see 목포 출장샵 photos and albums from 8 Casino Stays, 경주 출장샵 with or without the need for a hotel in Stays. 정읍 출장안마