Toward an Analysis of Forward Pruning

Abstract

Several early game-playing computer programs used forward pruning (i.e., the practice of deliberately ignoring nodes that are believed unlikely to affect a game tree's minimax value), but this technique did not seem to result in good decision-making. The poor performance of forward pruning presents a major puzzle for AI research on game playing, because some version of forward pruning seems to be "what people do", and the best chess-playing programs still do not play as well as the best humans.<P>As a step toward deeper understanding of how forward pruning affects quality of play, in this paper we set up a model of forward pruning on two abstract classes of binary game trees, and we use this model to investigate how forward pruning affects the accuracy of the minimax values returned. The primary result of our study is that forward pruning does better when there is a high correlation among the minimax values of sibling nodes in a game tree.<P>This result suggests that forward pruning may possibly be a useful decision-making technique in certain kinds of games. In particular, we believe that bridge may be such a game.