ABSTRAKSI: Pingdoll merupakan permainan logika dengan menggunakan papan permainan yang berukuran minimal 5x5 sebagai media permainannya. Aturan mainnya adalah meyakinkan seorang pemain agar dapat mengisi sel-sel pada board sehingga karakter yang dimasukkan pemain dapat membentuk suatu pola 5 bidak yang terisi secara berdampingan secara horizontal, vertikal, ataupun diagonal.
Algoritma Minimax merupakan algoritma yang digunakan untuk menentukan pilihan dengan tujuan memperkecil kemungkinan kehilangan nilai maksimal. Sedangkan Alpha-Beta Pruning merupakan modifikasi dari algoritma Minimax, yang akan mengurangi jumlah node yang dievaluasi oleh pohon pencarian. Fungsi fitness dikembangkan berdasarkan implementasi dari algoritma Minimax dan Alpha-Beta Pruning dengan tujuan untuk memperoleh langkah terbaik dan memperoleh solusi yang terbaik bagi AI Player (menang atau minimal seri).
Alpha-Beta Pruning memberikan hasil yang lebih optimal dibandingkan dengan algoritma Minimax. Hasil yang optimal di sini adalah seperti tingkat kemenangan AI Player terhadap Human Player yang lebih baik, serta performansi sistem yang lebih baik dari segi eksekusi waktu solusi dan penggunaan memori. Pada analisis hasil untuk kecepatan waktu eksekusi game, Algoritma Alpha-Beta Pruning membutuhkan waktu sekitar 1 menit untuk menyelesaikan permasalahan pada game Pingdoll dan untuk kebutuhan memori algoritma Alpha-Beta Pruning sewaktu menjalankan permainan dari awal hingga selesai adalah jauh lebih kecil jika dibandingkan dengan algoritma Minimax dengan persentase sekitar 78.8%.
Kata Kunci : Pingdoll, Minimax, Alpha-Beta Pruning, Fungsi Fitness, AI Player, Human PlayerABSTRACT: Pingdoll is logic game were played in a game board within minimal space which in sized 5x5 to play it. The game rule is how to make sure a player can fill cells in board. Thus player can make any 5 pairing pattern in a certain possible positions that is horizontal, vertical and diagonal.
Minimax algorithm is a decision rule used in decision theory for minimizing the possible loss while maximizing the potential gain. On the other hand, Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated by the Minimax algorithm in its search tree. Fitness function will be built on the game based on the two algorithms, Minimax and Alpha-Beta Pruning in order to acquire the best solution for the next step on the AI Player (Win or draw).
Alpha-Beta Pruning algorithm obtained a more optimum result than Minimax did. Optimum result here is such as victory rate on AI Player which is better than Human Player versus itself, and system performance which again is better accordance to time execution and memory consumption when it is acquiring the best solution for AI Player. To the output analysis on the time execution, Alpha-Beta Pruning algorithm needs approximately 1 minute to accomplish job and gives best solution to the AI Player and through the memory needs on Alpha-Beta Pruning when it is running the game from the first start until finish is smaller than Minimax algorithm with estimation percentage 78.8%.
Keyword: Pingdoll, Minimax, Alpha-Beta Pruning, Fitness Function. AI Player, Human Player