Pengaruh Global Transposition Table dan Algoritma Pvs dan Negascout Pada Puzzle Games

Abstract

Nine Men’s Morris merupakan game puzzle berbentuk board game 2 pemain. Papan terdiri dari kotak dengan dua puluh empat persimpangan atau titik. Permainan Nine Men’s Morris bersifat fully observable yang artinya bahwa seluruh kondisi pada papan permainan dan bidak-bidak dapat dipersepsi dan dinilai dengan baik. Penelitian ini melihat pengaruh penggunaan algoritma-algoritma dalam performa game Nine Men’s Morris. Performa permainan dilihat dari kemenangan, panjang jumlah jalur, lama pencarian. Penggunaan Global Transposition Table (GTT) sebagai penyimpanan memiliki keunggulan – dimana penyimpanannya lebih banyak sehingga memberikan ruang penelusuran lebih besar. Kemampuan ini disebabkan karena sifat GTT yang paralel. Dengan GTT ini diharapkan mampu menemukan solusi lebih cepat. Global Transposition Table sendiri adalah kumpulan dari beberapa tabel transposisi di dalam sebuah tabel transposisi lebih besar. GTT dapat diibaratkan seperti folder yang memiliki banyak subfolder dengan setiap subfolder berisi tipe file yang sama, dan memiliki nama depan file yang sama. Maka dengan menggabungkan Algoritma pencaria dan penggunakan GTT dalam permaian Nine Man’s Morris ini diharapkan dapat mengetahui performa dari penggunaan Algoritma Negascout dan juga pengaruh tambahan dari penggunaan GTT dalam game puzzle Nine Men’s Morris.