ALGORITMA ALPHA-BETA PRUNING DALAM CHESS ENGINE; ALPHA-BETA PRUNING ALGORITHM IN CHESS ENGINE

Werda Buana Putra, Lukman Heryawan

2014 | Skripsi | PROGRAM STUDI 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. Kata

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