language: en

Toward an Analysis of Forward Pruning

Stephen J. J. Smith
Computer Science Department University of Maryland
College Park, MD 20740
sjsmith@cs.umd.edu
Dana S. Nau
Institute for Advanced Computer Studies, Computer Science Department, and Institute for Systems Research University of Maryland
College Park, MD 20740
nau@cs.umd.edu June 30, 1993

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. 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. 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.

[Address correspondence to]

Dana S. Nau,
Computer Science Dept., University of Maryland,
College Park, MD 20742.

[This work supported in part by an AT&T Ph.D. scholarship to Stephen J. J. Smith, Maryland Industrial Part nerships (MIPS) grant 501.15, Great Game Products, and NSF grants IRI-8907890 and NSFD CDR-88003012.]