Use of the alpha-beta pruning algorithm instead of the simple minimax search reduces by a large factor the number of bottom positions which must be examined in the search. An analytical expression for the expected number of bottom positions examined in a game tree using alpha-beta pruning is derived, subject to the assumptions that the branching factor N and the depth D of the tree are arbitrary but fixed, and the bottom positions are a random permutation of N unique values. A simple approximation to the growth rate of the expected number of bottom positions examined is suggested, based on a Monte Carlo simulation for large values of N and D. The behavior of the model is compared with the behavior of the alpha-beta algorithm in a chess playing program and the effects of correlation and non-unique bottom position values in real game trees are examined. The probabilistic model used in our study is presented in the next section and we derive an analytical expression for the expected number of bottom positions evaluated in the search of a game tree using alpha-beta pruning.
Gillogly, J. J.
Gillogly, J. J.
A chess program has been developed which plays good chess (for a program) using a very simple structure. It is based on a brute force search of the move tree with no forward pruning, using material as the only terminal evaluation function, and using a limited positional analysis at the top level for a tiebreak between moves which are materially equal. Because of the transparent structure, this program is proposed as a technological benchmark for chess programs which will continue to improve as computer technology increases.