Kecerdasan buatan pada permainan catur berbasis komputer :: Sebuah implementasi metode pencarian Alpha Beta Cutoff

SANO, Albert V. Dian, Drs. Retantyo Wardoyo, M.Sc.,Ph.D

2006 | Tesis | S2 Ilmu Komputer

Pada dasarnya sebuah program catur dalam penelitian ini terdiri dari tiga hal pokok, yaitu adanya suatu fungsi yang menghasilkan langkah, fungsi yang memberikan evaluasi berdasarkan skor pada tiap-tiap buah catur, dan adanya fungsi pencarian yang bertugas mencari skor langkah terbaik. Inti dari proses berpikir komputer adalah adanya fungsi pencarian untuk menemukan langkah terbaik. Metode pencarian yang diimplementasikan pada penelitian ini adalah metode pencarian alpha beta cutoff. Metode ini merupakan bentuk optimasi dari metode pencarian minimax. Pada pencarian minimax semua node akan dibandingkan untuk mendapatkan nilai terbaik. Sementara pada pencarian alpha beta cutoff tidak semua node dibandingkan. Node-node yang tidak memberi manfaat pada proses pencarian akan dipangkas dan proses pencarian tidak perlu diteruskan. Dengan adanya pemangkasan node-node yang tidak berguna tersebut diharapkan akan mempersingkat waktu proses pencarian. Pengujian pada penelitian ini berupa serangkaian percobaan pertandingan antara manusia melawan komputer. Hasil penelitian menunjukkan bahwa komputer mampu berpikir dan menunjukkan kecerdasan dengan baik, meskipun masih sangat terbuka untuk mendapatkan optimasi lebih lanjut.

A chess program basically consists of three main parts, that is, a move generator to generate all legal moves, an evaluation function to evaluate each move, and a search function to select the best move. The core of thinking process is the search function. The search method implemented in this research is alpha beta cutoff. This method is derived from minimax search method to get more optimized. In minimax, all nodes will be searched and compared one by one to get the best value. Meanwhile in alpha beta cutoff, it is not necessary to do those. This method only searches nodes which make contribution to the previous value and cuts off nodes which are not useful. It means that alpha beta will not search and compare all nodes. The new node will be better than the previous one and replace the old value with the new one. In this sense, alpha beta will take less search time. Examinations on this research are by doing a series of matches between human and computer. The results show that the computer has ability to think well and performs a good artificial intelligence though it is very open to be modified and more optimized.

Kata Kunci : Teknologi Informasi,Perancangan Sistem,Kecerdasan Buatan, move generator function, evaluation function, search function, minimax, alpha beta cutoff