MODIFIKASI ALGORITMA MINIMAX DENGAN ALPHA BETA PRUNING PADA PROTOTYPE PERMAINAN BERTIPE TURN BASED

• Main Author: Perdiansyah, Arief (Author)
• Format: Book
• Published: 2017-08-23.
• Subjects: Thesis; NonPeerReviewed
• Online Access: Link Metadata

Summary

Algoritma Minimax merupakan salah satu algoritma yang sering diterapkan pada permainan bertipe giliran atau biasa disebut turn based game. Namun permasalahan muncul saat algoritma Minimax digunakan pada permainan yang kompleks. Penggunaan algoritma Minimax pada permainan yang kompleks akan membuat waktu pencarian solusi menjadi lebih lama. Oleh karena itu, Alpha Beta pruning menjadi salah satu solusi untuk mengurangi waktu penelusuran pada pencarian solusi. Untuk melihat perbedaan waktu pencarian solusi antara algoritma Minimax dengan algoritma Minimax Aplha Beta pruning maka dibuatlah sebuah prototype permainan bertipe turn based. Hasil pengujian dengan menggunakan prototype permainan yang dibuat diketahui bahwa Alpha Beta pruning mampu memangkas waktu penelusuran sebanyak 90 persen lebih cepat daripada algoritma Minimax tanpa pruning. Hal ini terjadi karena simpul-simpul yang bukan merupakan solusi tidak perlu ditelusuri. Adapun salah satu cara untuk memangkas simpul lebih banyak pada algoritma Minimax Alpha Beta pruning diperlukan pembuatan tree yang baik, sehingga pada saat proses pencarian dengan algoritma Minimax Alpha Beta pruning bisa lebih cepat dengan melakukan pruning pada bagian-bagian tree yang sudah disusun atau disortir, Kata Kunci: permainan, turn based game, prototype, tree, Minimax, Alpha Beta pruning.  Minimax algorithm is one algorithm that is often applied in turn-type game or commonly called turn based game. But the problem arises when the Minimax algorithm is used in complex games. The use of Minimax algorithms in complex games will make the solution search time longer. Therefore, Alpha Beta pruning becomes one of the solutions to reduce search time on solution search. To see the difference of the time searching solution between Minimax algorithm with Minimax algorithm Aplha Beta pruning a turn based game prototype is made. The test results using the game prototype made a finding that Alpha Beta pruning able to cut search time as much as 90 percent faster than the Minimax algorithm without pruning. This happens because nodes that are not a solution are already pruned by Alpha Beta pruning method. As for one way to cut more nodes on the algorithm Minimax Alpha Beta pruning process required good tree creation, so the Minimax Alpha Beta pruning algorithm can be faster by pruning the parts of the tree that has been prepared or sorted. Keywords: games, turn based game, prototype, tree, Minimax, Alpha Beta pruning

Item Description

http://repository.upi.edu/31127/1/S_KOM_1301416_Title.pdf
http://repository.upi.edu/31127/2/S_KOM_1301416_Abstract.pdf
http://repository.upi.edu/31127/3/S_KOM_1301416_Table_of_content.pdf
http://repository.upi.edu/31127/4/S_KOM_1301416_Chapter1.pdf
http://repository.upi.edu/31127/5/S_KOM_1301416_Chapter2.pdf
http://repository.upi.edu/31127/6/S_KOM_1301416_Chapter3.pdf
http://repository.upi.edu/31127/7/S_KOM_1301416_Chapter4.pdf
http://repository.upi.edu/31127/8/S_KOM_1301416_Chapter5.pdf
http://repository.upi.edu/31127/9/S_KOM_1301416_Bibliography.pdf
http://repository.upi.edu/31127/10/S_KOM_1301416_Appendix.pdf