ALGORITMA ALPHA-BETA PRUNING DALAM CHESS ENGINE

WERDA BUANA PUTRA, Lukman Heryawan S.T., M.T.

2015 | Skripsi | S1 ILMU KOMPUTER

Kapasitas sebuah software catur ditentukan oleh teknik pencarian yang dilakukan chess engine dan didukung oleh hardware yang digunakan. Minimax adalah sebuah algoritma pencarian yang dipakai sebagai konsep permainan zero sum(catur, go). Jika konsep algoritma Minimax diterapkan dalam permainan catur tanpa dimodifikasi, akan memberikan beban yang besar pada hardware komputer canggih sekalipun. Algoritma Alpha-Beta Pruning, sebagai pengembangan dari algoritma Minimax, merupakan suatu solusi untuk mengurangi beban hardware. Idenya adalah mengurangi jumlah node yang akan dievaluasi oleh algoritma Minimax dengan membuang suatu cabang di dalam sebuah search tree jika node child tidak dapat memberikan nilai yang dicari oleh node parent. Chess engine yang dibangun kali ini menggunakan algoritma Alpha-Beta Pruning dan diberi nama Harmonia. Dalam masa penelitian, Harmonia akan dipertandingkan dengan beberapa chess engine lain yang memiliki ukuran lebih besar (175 KB) dan menggunakan lebih banyak resource komputer. Hasil yang diperoleh dari penelitian membuktikan Harmonia yang menggunakan algoritma Alpha-Beta Pruning dapat mengimbangi permainan melawan engine catur yang memiliki ukuran dan menggunakan sumber daya yang lebih besar.

A chess engine's capability is determined by the search technique it used, supported by the hardware. Minimax is an algorithm used as foundation in zero-sum game(chess, go). Should Minimax concept applied in chess, unmodified, they will give a massive burden on hardware, even the sophisticated one. Algorithm Alpha-Beta Pruning, as the advancement of Minimax algorithm, is a solution to reduce the burden on hardware. The idea is to reduce the number of nodes that will be evaluated by the Minimax algorithm by removing a branch in a tree search should the child node can't provide the value sought by the parent node. Chess engines we built use the Alpha-Beta Pruning algorithm and named Harmonia. In the study period, Harmonia would be competed with several other chess engines with larger size (175 KB) and uses more computer resources in execution. Results obtained at the end of the study proved that Harmonia which built using Alpha-Beta Pruning algorithm can withstand the might of another chess engines that greater in term of the size and use of resources.

Kata Kunci : Alpha-Beta Pruning, child, Minimax, node, parent