Risk management in game-tree pruning
In the half century since minimax was first suggested as a strategy for adversary game search, various search algorithms have been developed. The standard approach has been to use improvements to the AlphaBeta (??) algorithm. Some of the more powerful improvements examine continuations beyond the nominal search depth if they are of special interest, while others terminate the search early. The latter case is referred to as forward pruning. In this paper we discuss some important aspects of forward pruning, especially regarding risk-management, and propose ways of making risk-assessment. Finally, we introduce two new pruning methods based on some of the principles discussed here, and present experimental results from application of the methods in an established chess program.
forward pruning game-tree search computer chess