Shalihin, Maulana (2015) Penerapan Algoritma Minimax dengan Optimasi MTD(f) pada Permainan Dam-daman. Sarjana thesis, Universitas Brawijaya.
Abstract
Permainan dam-daman adalah permainan tradisional indonesia yang dimainkan oleh dua orang secara bergantian. Tujuan dari permainan ini adalah menghabiskan pion lawan. Dam-daman termasuk genre permainan turn based strategy. Algoritma yang dipakai dalam permainan berbasis turn based strategy adalah minimax. Namun, minimax memiliki permasalahan ketika kedalaman pencarian solusi tinggi, minimax akan berjalan sangat lambat. Karena setiap node dalam setiap kedalamannya akan ditelusuri satu persatu. Oleh karena itu, dibutuhkan algoritma optimasi yang bisa mempercepat performa dari minimax. MTD(f) menawarkan solusi dengan metode pencarian zero-window. MTD(f) memberikan batas dimana ketika pencarian berada di luar batas, maka pencarian akan dihentikan. Penelitian ini bertujuan mengimplementasikan dan menguji performa algoritma minimax dengan optimasi MTD(f) pada permainan dam-daman. Berdasarkan hasil pengujian, Algoritma Minimax MTD(f) memiliki performa yang handal. Kedalaman pencarian dan semakin tingginya papan permainan tidak berpengaruh negatif terhadap performa komputasi.
English Abstract
Dam-daman is traditional game from indonesia which played by two player alternately. The goal of this game is to spend enemy pieces. Dam-daman‟s games genre is turn based strategy. Generally, turn based strategy use minimax as it‟s Algorithm. But, minimax have some problem when implemented in higher recursive depth, minimax will run so slowly. Because minimax will visit every node has been generated one by one. So, it is need some optimation algorithm to boosting minimax. MTD(f) offers a solution with zero-window search method. MTD(f) give some low upperbound and lowerbound to AlphaBeta Method. Goal of the Research is to implement and testing the performance of minimax algorithm with MTD(f) in dam-daman game. Based on the test result, MTD(f) has good performance. It is good implemented in the deeper search and many nodes.
Item Type: | Thesis (Sarjana) |
---|---|
Identification Number: | SKR/FTIK/2015/40/051500788 |
Uncontrolled Keywords: | dam-daman, NPC, minimax, Alpha-Betawith memory, MTD(f) |
Subjects: | 000 Computer science, information and general works > 005 Computer programming, programs, data |
Divisions: | Fakultas Ilmu Komputer > Teknik Informatika |
Depositing User: | Budi Wahyono Wahyono |
Date Deposited: | 10 Feb 2015 08:40 |
Last Modified: | 28 Nov 2021 06:59 |
URI: | http://repository.ub.ac.id/id/eprint/146465 |
Preview |
Text
LENGKAP.pdf Download (2MB) | Preview |
Actions (login required)
![]() |
View Item |