Properties of forward pruning in game-tree search

Abstract

Forward pruning, or selectively searching a subset of moves, is now commonly used in game-playing programs to reduce the number of nodes searched with manageable risk. Forward pruning techniques should consider how pruning errors in a game-tree search propagate to the root to minimize the risk of making errors. In this paper, we explore forward pruning using theoretical analyses and Monte Carlo simulations and report on two findings. Firstly, we find that pruning errors propagate differently depending on the player to move, and show that pruning errors on the opponent's moves are potentially more serious than pruning errors on the player's own moves. This suggests that pruning on the player's own move can be performed more aggressively compared to pruning on the opponent's move. Secondly, we examine the ability of the minimax search to filter away pruning errors and give bounds on the rate of error propagation to the root. We find that if the rate of pruning error is kept constant, the growth of errors with the depth of the tree dominates the filtering effect, therefore suggesting that pruning should be done more aggressively near the root and less aggressively near the leaves. Copyright © 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.