Searching with Uncertainty Cut-Offs1
Yngvi Björnsson, T.A. Marsland, Jonathan Schaeffer, Andreas Junghanns · ICGA Journal · 1997
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.