Penerapan Algoritma Negamax Untuk Menghasilkan Langkah Yang Optimal Pada Permainan Dam Daman

Permainan dam daman merupakan permainan tradisional, permainan ini dimainkan oleh dua pemain. Permainan ini dimainkan di papan atau karton yang telah digambar. Dalam permainan ini terdapat 16 bidak untuk setiap pemain. Tujuan permainan ini adalah untuk menghabiskan bidak lawan dengan aturan yang telah disepakati bersama sebagai akhir permainannya. Pada permainan dam daman ini terdapat banyak langkah. Satu bidak bisa mempunyai lebih dari dua kemungkinan langkah yang bisa diambil. Dari beberapa langkah tersebut ada yang menguntungkan, ada juga yang merugikan pemain. Jika pemain mengambil langkah bidak secara acak, maka kemungkinan kalah akan lebih besar. Untuk mencari langkah pergerakan bidak yang menguntungkan digunakan algoritma Depth-First Search. Salah satu algoritma DFS adalah algoritma negamax. Algoritma ini menggunakan dua buah fungsi, satu fungsi untuk memaksimalkan dan satu untuk meminimalkan kedua fungsi tersebut digabung menjadi satu fungsi yang dapat menegasikan dan terbalik setiap kali pemanggilannya. Dan untuk mempersempit pencarian digunakan algoritma alpha beta prunning. Tujuan dari penelitian ini adalah untuk mengetahui banyaknya kemungkinan langkah yang bisa diambil dan tingkat kemenangan dengan menggunakan algoritma negamax. Banyaknya kemungkinan langkah yang bisa diambil berdasarkan hasil pencarian algoritma negamax adalah sebanyak 10 langkah kemungkinan. Sedangkan tingkat kemenangan komputer masih rendah, yaitu hanya 40%. Algoritma negamax yang diterapkan pada permainan dam daman belum optimal.

Game of dam daman is a game of traditional, this game is played by two players. The game is played on a board or cardboard that has been drawn. In this game there are 16 pawns for each other. The purpose of the game is to spend pawns opponent with the rules that have been agreed upon as the end of the game. In game of dam daman there are mant steps, one pawn can have more than two possible steps that could be taken. From some of the steps there is a profitable, there is also a disadvantage to the player. If the player takes a pawn move randomly, then the possibility of losing will be bigger. To search for a profitable move movement pawn used algorithms Depth-First Search. One of the DFS algorithm is an algorithm negamax. This algorithm uses two functions, one function to maximize and one to minimize both functions are combined into a single function that can be negated and reversed each time calling. And to narrow the search algorithm, alpha beta prunning. The purpose of this research was to determine the number of possible steps that can be taken and the level of victory by using algorithm negamax. The number of possible steps that can be taken based on the results of the search algorithm negamax is as many as 10 steps possibility. As for winning rate computer is still low at only 40%. Negamax algorithm is applied to the game of dam daman not optimal.