Implementasi Algoritma Minimax Untuk Menentukan Langkah NPC Dalam Mengambil Keputusan Pada Permainan Domino

Domino merupakan sebuah permainan yang menggunakan balok-balok dimana pada kedua sisi memiliki nilai berupa tanda lubang berwarna hitam yang menyatakan nilainya dari 0 sampai dengan 6. Berdasarkan penelitian yang dilakukan sebelumya oleh Hary Fernando dari Institut Teknologi Bandung dengan menerapkan algoritma brute force dan greedy. Pada persoalan kasusnya algoritma brute force pada permainan domino pemain hanya perlu meletakkan kartu domino dimana saja asalkan sesuai, sehingga dapat dikeluarkan tapi tidak peduli urutan atau hal-hal lain. Sedangkan penerapan algoritma greedy, jika kita telah mengeluarkan kartu dengan nilai terbesar yang kita miliki, hal tersebut belum menjamin bahwa kartu-kartu selanjutnya yang dikeluarkan akan mudah / cepat habis. Permainan yang dibangun berjudul domino, Algoritma yang digunakan menggunakan algoritma Minimax dengan metode pencarian Divide and Conquer. Data masukan yang dibutuhkan yaitu kartu dan waktu, struktur yang digunakan berupa array, metode analisis pembangunan perangkat lunak berorientasi objek menggunakan UML, dimana tahap-tahap perancangannya dimulai dari usecase diagram, activity diagram, class diagram dan sequence diagram.Berdasarkan hasil pengujian yang dilakukan dapat disimpulkan bahwa algoritma Minimax dengan metode pencarian divide and conquer dapat diterapkan untuk menentukan langkah NPC (Non Player Character) dalam mengambil keputusan. Algoritma Minimax adalah solusi untuk mencari langkah yang tepat dalam penentuan langkah, sehingga memperkecil peluang untuk kalah.

Domino is a game which has blocks on it where the two side have values in forms of black holes which state their values from 0 to 6. According to the previous research by Hary Fernando from Bandung Institute of Technology by applying brute force and greedy algorithm. In the case of brute force algorithm in the game of Domino, the players only need to put down the domino cards anywhere they like as long as they match, hence they can be put down not according to the count or other variables. While in greedy algorithm, if the players have put down their highest-value card, it does not give the players guarantee that the next cards will be easily put down.The game in the making called Domino which is using minimax algorthm with Devide and Conquer searching method. The data which required are cards and time, structur which is used is Array, analysis methode in software-building based on objects is using UML where the steps of making it started from usecase diagram, acxtivity diagram, class diagram or sequence diagram.Based on result of the test it can be concluded that minimax algorithm with divide and conquer method can be applied to determine the steps of NPC (Non Playing Character) in making decision. Minimax algorithm is the solution to find the right steps while making steps hence minimize the chance of losing the game.