Artificial Intelligence on Computer Based Chess Game: An Implementation of Alpha-Beta-Cutoff Search Method

Abstract

Abstract

A chess program usually 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 search function is the core of thinking process. The goal of this research is to implement the alpha beta cutoff as a search method. This method is derived from minimax search method and is more optimal than the minimax search method.

In minimax, all nodes is searched and compared one by one to get the best value. On the other hand, the alpha beta cut of methd only searches nodes which make contribution to the previous value and cuts off nodes which are not useful. It means that the alpha beta method 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. This will make the alpha beta method requires smaller search time.

The proposed method is tested by doing a series of matches between humans and a computer. The results show that the computer has ability to think well and performs a good artcial intelligence though it is very open to be modified and more optimized.

Keywords: move generator function, evaluation function, search function, minimax, alpha beta cutoff