On Optimal Game Tree Propagation for Imperfect Players

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Search and Expert Systems

We consider the approach to game playing where one looks ahead in a game tree, evaluates heuristically the probability of winning at the leaves, and then propagates this evaluation up the tree. We show that minimax does not make optimal use of information contained in the leaf evaluations, and in fact misvalues the position associated with all nodes. This occurs because when actually playing a position down the game tree, a player would be able to search beyond the boundaries of the original search, and so has access to additional information. The remark that such extra information will exist, allows better use of the information contained in the leaf evaluations even though we do not have access to the extra information itself. Our analysis implies that, while minimax is approximately correct near the top of the game tree, near the bottom a formula closer to the probability product formula is better. We propose a simple model of how deep search yields extra information about the chances of winning in a position. Within the context of this model, we write down the formula for propagating information up the tree which is correct at all levels. We generalize our results to the case when the outcomes at the leaves are correlated and also to games like chess where there are three possible outcomes: Win, Lose, and Draw. Experiments demonstrate our formula’s superiority to minimax and probability product in the game of Kalah.