Improved Decision-Making in Game Trees: Recovering from Pathology

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.

Authors

• Arthur L. Delcher Simon Kasif

Keywords

No keywords are indexed for this paper.