IMPLEMENTASI ALGORITMA GREEDY DAN MINIMAX DENGAN OPTIMASI ALPHA BETA PRUNING DALAM GAME HALMA

• Main Author: Kholish, Muhammad Nur (Author)
• Format: Book
• Published: 2017-05-31.
• Subjects: Thesis; NonPeerReviewed
• Online Access: Link Metadata
• Notes: http://repository.upi.edu/29153/1/S_KOM_1002478_Title.pdf; http://repository.upi.edu/29153/2/S_KOM_1002478_Abstract.pdf; http://repository.upi.edu/29153/3/S_KOM_1002478_Table_of_Content.pdf; http://repository.upi.edu/29153/4/S_KOM_1002478_Chapter1.pdf; http://repository.upi.edu/29153/5/S_KOM_1002478_Chapter2.pdf; http://repository.upi.edu/29153/6/S_KOM_1002478_Chapter3.pdf; http://repository.upi.edu/29153/7/S_KOM_1002478_Chapter4.pdf; http://repository.upi.edu/29153/8/S_KOM_1002478_Chapter5.pdf; http://repository.upi.edu/29153/9/S_KOM_1002478_Bibliography.pdf; http://repository.upi.edu/29153/10/S_KOM_1002478_Appendix.pdf
• Keywords: L Education (General); QA76 Computer software

Seiring dengan perkembangan zaman dan teknologi yang semakin maju, game juga semakin maju dan berkembang. Pada sebuah game, biasanya terdapat implementasi dari algoritma kecerdasan buatan untuk mendukung gameplay game tersebut. Pada penelitian ini algoritma greedy dan minimax dengan alpha beta pruning dijadikan sebagai kecerdasan buatan untuk non-player character (NPC) dalam game halma. Algoritma greedy digunakan untuk mencari nilai perpindahan paling jauh pada setiap bidak dan algoritma minimax dengan alpha beta pruning digunakan untuk mengantisipasi pergerakan lawan dan mencari bidak yang paling optimal untuk digerakkan. Dari hasil pengujian perbandingan antara algoritma greedy saja dengan algoritma gabungan disimpulkan bahwa algoritma gabungan lebih baik dalam pemilihan langkah terbaik dalam game halma dengan presentase kemenangan untuk algoritma gabungan adalah 100% dalam pengujian dua pemain, 83.3% dalam pengujian tiga pemain, dan 78.6% dalam pengujian empat pemain. Dari hasil kuesioner yang diberikan kepada responden bahwa dengan adanya penerapan kecerdasan buatan pada NPC, secara keseluruhan game halma lebih menarik untuk dimainkan.----------Along with the development of the era and the more advanced technology, the game is also more advanced and growing. In a game, there is usually an implementation of artificial intelligence algorithm to support the game's gameplay. In this study the greedy and minimax algorithms with alpha beta pruning serve as artificial intelligence for non-player character (NPC) in game halma. The greedy algorithm is used to find the most distant displacement value on each piece and the minimax algorithm with alpha beta pruning is used to anticipate the movement of the opponent and find the most optimized piece to move. From the result of comparison test between greedy algorithm with combined algorithm it is concluded that the combined algorithm is better in choosing the best step in game of halma with 100% winning percentage for the combined algorithm in two player test, 83.3% in three player test, and 78.6% in four player test. From the results of questionnaires given to the respondents that with the application of artificial intelligence on the NPC, overall game is more interesting halma to play.