Note: [1] This is a revised version of the paper delivered under the same title on June 28, 1996, at the 8th Conference on Advances in Computer Chess, Maastricht, The Netherlands. It will also be published in the Proceedings of that Conference.
Note: [*] University of Alberta, Department of Computing Science, Edmonton, Alberta T6G 2H1, Canada. E-mails: yngvi@cs.ualberta.ca, tony@cs.ualberta.ca, jonathan@cs.ualberta.ca, andreas@cs.ualberta.ca.
Abstract: A new domain-independent pruning method is described that guarantees returning a correct game value. Even though αβ-based chess programs are already searching close to the minimal tree, there is still scope for improvement. Our idea hinges on the recognition that the game tree has two types of node those where cut-offs occur, and those that must be fully explored. In the latter case one of the moves is best and yields the subtree value, thus for the remaining alternatives it is enough to show their inferiority. This otters an opportunity for pruning, while introducing some potential for uncertainty in the search process. There are two cases of interest. One considers the immediate alternatives to the Principal Variation itself, here a new safe cut-off is presented. The other is a proposal for an unsafe generalization, one which offers substantial search reduction but with the potential for control of the error probability. Experiments with the new pruning method show some savings in the search.
DOI: 10.3233/ICG-1997-20104
Journal: ICGA Journal, vol. 20, no. 1, pp. 29-37, 1997
