In game-tree search, a point value is customarily used to measure position evaluation. If the uncertainty about the value is to be reflected in the evaluation, which is described with probabilistic distribution or probabilities, the search process must back up distributions from leaf nodes to the root. It is shown that even though the merit value of a node is described by probabilities, α-β bounded windows can still be used to cut off some subtrees from search when a space-efficient depth-first traversal is applied to the game tree. Several variations of probability-based α-β game tree pruning are presented. We also show that probability-based α-β pruning can be viewed as a generalization of the standard α-β game tree search algorithm and that it inherits some good properties from its point-value version.
['Liwu Li', 'T. A. Marsland']
Probability-based game tree pruning