Improved Decision-Making in Game Trees: Recovering from Pathology

Problem Solving

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 10

Problem Solving: Search and Expert Systems

In this paper we address the problem of making correct decisions in the context of game-playing. Specifically, we address the problem of reducing or eliminating pathology in game trees. However, the framework used in the paper applies to decision making that depends on evaluating complex Boolean expressions. The main contribution of this paper is in casting general evaluation of game trees as belief propagation in causal trees. This allows us to draw several theoretically and practically interesting corollaries. In the Bayesian framework we typically do not want to ignore any evidence, even if it may be inaccurate. Therefore, we evaluate the game tree on several levels rather than just the deepest one. Choosing the correct move in a game can be implemented in a straightforward fashion by an efficient linear-time algorithm adapted from the procedure for belief propagation in causal trees. We propose a probabilistically sound heuristic that allows us to reduce the effects of pathology significantly.