Implementasi Algoritma Negascout untuk Menentukan Langkah Pemain Lawan Pada Permainan Nine Men's Morris

Nine men�s morris merupakan sebuah permainan papan dengan dua pemain dimana kondisi papan dapat dilihat oleh kedua pemain tersebut. Papan yang digunakan berupa 3 buah persegi berbeda ukuran dengan yang lebih kecil berada di dalam persegi yang besar. Titik tengah sisi sebuah persegi terhubung dengan titik tengah sisi dua persegi lain dengan sebuah garis. Setiap pemain memilik masing-masing 9 bidak, untuk mengalahkan lawan seorang pemain harus membentuk �mill� (atau disebut juga �morris�) yaitu garis lurus horizontal atau vertical dengan tiga bidak berwarna sama. Agar permainan ini dapat dimainkan oleh seorang pemain dibutuhkan sebuah kecerdasan buatan pada pemain lawan. Algoritma negascout merupakan algoritma perbaikan dari alpha beta pruning yang digunakan pada algoritma minimax dengan mempersempit ruang pencarian, dengan semakin sempitnya selisih nilai alpha dan beta, maka semakin besar kemungkinan terjadinya pemotongan pencarian. Sehingga akan mempercepat waktu berpikir AI dalam mengambil keputusan. Berdasarkan hasil pengujian yang dilakukan dapat disimpulkan bahwa algoritma negascout dapat diterapkan untuk menentukan langkah pemain lawan pada permainan nine men�s morris dalam mengambil keputusan.

Nine men's morris is a board game with two players in which the condition of the board can be seen by both players. Boards are used in the form of 3 square pieces of different sizes to be smaller in the large square. The midpoint of the side of a square connected to the midpoint of the two sides of another square with a line. Each player pick each 9 pawns, to defeat opponents a player must form a "mill" (pronounced "Morris") is a straight line horizontally or vertically with three same colored pawns. In order for this game can be played by a player takes an artificial intelligence on opposing players. Negascout algorithm is an algorithm improvement of alpha beta pruning algorithm is used to narrow the search space minimax with, with the limited increment of alpha and beta, the greater the likelihood of cutting search. So it will speed up the time to think of AI in making decisions. Based on the results of tests performed can be concluded that the algorithm can be applied to determine negascout opposing player steps on the game nine men's morris in making decisions.