Improved Decision-Making in Game Trees: Recovering from Pathology

Arthur L. Delcher, Simon KasifAAAI 1992

Abstract

Searching deeper in a game tree is traditionally expected to improve move quality. However, in "noisy" environments, deeper search can paradoxically lead to worse performance—a phenomenon known as pathology. This paper investigates this issue and proposes a solution by treating game trees as Bayesian networks. By employing belief propagation or a simpler majority-vote heuristic, the proposed methods aggregate evidence across multiple search depths to mitigate pathology and enhance decision robustness.

Introduction: The Problem of Game Tree Pathology

In classical AI game-playing, minimax search is the standard paradigm: an agent looks ahead several moves, evaluates the resulting board states at the "leaves," and propagates these values back to the root. The intuitive assumption is that deeper look-ahead always yields better results.

However, research has identified a counter-intuitive phenomenon called pathology. In certain game tree structures, searching deeper actually increases the probability of making a mistake. This occurs because errors in the evaluation function can accumulate and amplify as they are backed up through MIN and MAX levels, eventually outweighing the benefits of deeper look-ahead. This paper seeks to address this by transitioning from the "all-or-nothing" logic of minimax to a probabilistic framework.

Methodology: Probabilistic Evidence Aggregation

The authors propose two primary methods to combat pathology by moving away from relying solely on the frontier nodes.

1. Bayesian Decision Procedure

The game tree is recast as a causal tree (a type of Bayesian Network), where each node is a random variable representing a WIN or LOSS state. Instead of just taking the value from the deepest level, the system uses belief propagation. This allows for the incorporation of "evidence" (evaluations) from every node in the tree.

Causal tree representation for Bayesian belief propagation.

By calculating the actual probability of a win for each possible move, the agent makes a statistically optimal choice based on all available data.

2. Majority Vote Heuristic

Since full Bayesian propagation is computationally expensive and incompatible with standard Alpha-Beta pruning, the authors also propose a "Majority Vote" heuristic. This involves performing multiple searches to different depths (e.g., depths 4 through 8) and having each depth "vote" on the best move. The final move is chosen by a majority or weighted majority.

Experimental Setup

The methods were evaluated using the Board-Splitting Game, a synthetic benchmark designed to exhibit pathological behavior. The researchers used both plausible heuristics and intentionally "noisy" evaluation functions (flipping correct values with an error probability $p_e$) to simulate real-world uncertainty.

Key Results and Insights

The experimental results demonstrate that pathology is not an inherent property of searching deeper, but rather a flaw in how minimax propagates values under noise.

Comparison of error rates between standard minimax, majority evaluation, and Bayesian evaluation.

As shown in the figure above, while standard minimax error rates (at level 8 vs level 4) exhibit pathology as the evaluation function error increases, both the Bayesian and Majority Vote methods show consistently lower error rates. In trials of 10,000 games, the Bayesian approach significantly outperformed any single-level evaluation.

Key insights include:

  • Minimax is "Greedy" with Evidence: Standard minimax discards all intermediate information, making it fragile if the frontier is noisy.
  • Robustness to Noise: The Bayesian method is particularly effective as evaluation function error increases, whereas standard minimax degrades rapidly.
  • Heuristics are Effective: The simple Majority Vote heuristic captures much of the benefit of the full Bayesian approach while being easier to implement.

Limitations and Future Work

Despite its effectiveness, the Bayesian procedure requires evaluating every node in the tree, which is impractical for games with high branching factors like Go because it prevents Alpha-Beta pruning. Furthermore, the model assumes known prior and conditional probabilities, which are often difficult to estimate in complex games. Future research will focus on developing "probabilistic pruning" strategies to achieve Bayesian benefits without exhaustive tree traversal.

Summary updated

BibTeX
@inproceedings{delcher1992improved,
  author = {Arthur L. Delcher and Simon Kasif},
  title = {{Improved Decision-Making in Game Trees: Recovering from Pathology}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure