A Search Procedure for Perfect Information Games of Chance: Its Formulation and Analysis

Bruce W. BallardAAAI 1982

TL;DR

This paper introduces a novel algorithm, "Star-Minimax," for efficiently searching game trees that include chance events (like dice rolls or card draws). It significantly reduces the computational search space compared to standard minimax algorithms, offering a substantial speedup for games like backgammon or craps.

What Problem Does This Paper Address?

Many games, especially those involving dice or cards, introduce an element of chance. Traditional game-playing AI often uses minimax search, which works well for games with perfect information and no chance. However, incorporating chance events into these search trees requires a modified approach. The challenge is to develop a search algorithm that can efficiently explore these "chance nodes" while still leveraging the powerful pruning techniques (like alpha-beta pruning) that make minimax effective for deterministic games. Without such an algorithm, the search space for games with chance can become prohibitively large, even for relatively simple games.

Methods

The core innovation is the Star-Minimax algorithm, which extends the standard minimax search to handle "probability nodes" (denoted by '*'). These nodes represent chance events where multiple outcomes can occur with specific probabilities.

The algorithm's key features include:

  • Probability Node Value Calculation: The value of a probability node is defined as the weighted average of its successor nodes' values. The paper simplifies this by assuming all successor outcomes are equally likely.
  • Extended Alpha-Beta Pruning: The algorithm adapts alpha-beta pruning to probability nodes. It derives new, tighter bounds (alpha and beta values) for the children of a probability node based on the current bounds of the parent node and the probabilities of the outcomes. This allows for more effective cutoffs.
  • "Star1" and "Star2" Procedures: Two specific procedures are detailed. Star1 handles probability nodes where all children are also probability nodes. Star2 is an "improved" version that can further reduce search by "probing" a single child of each successor node before committing to a full search, especially useful when successor nodes are of the same type.

Datasets

Not discussed in the paper. The authors generated synthetic game trees for evaluation.

Key Insights and Ideas

  • Chance doesn't have to mean exponential blow-up: The paper demonstrates that with a clever algorithm, the computational cost of searching games with chance can be managed, offering significant savings over naive approaches.
  • Probability nodes can be pruned too: The core insight is that just as minimax prunes branches based on guaranteed outcomes, Star-Minimax can prune branches based on the expected outcomes at probability nodes.
  • Tighter bounds are key: By carefully calculating and propagating alpha and beta bounds through probability nodes, the algorithm achieves more aggressive pruning.
  • "Probing" can be a powerful heuristic: The Star2 algorithm's success in cutting off branches by examining just one child of a successor node highlights the effectiveness of preliminary exploration.

Key Results

  • Empirical Speedup: For depth 3 trees, the Star1 algorithm achieved a search reduction of more than 50 percent.
  • Best-Case Complexity: Closed-form analysis shows a best-case complexity of O(N^2) for Star1 on certain tree structures, a significant improvement over the O(N^3) of a naive search.
  • Average-Case Savings: Empirical tests showed average-case savings of about 21 percent for Star1.
  • Star2 Improvements: The Star2 algorithm further reduced search, with cutoffs occurring during the probing phase. For branching factors greater than 20, Star2 explored fewer than half the leaves examined by Star1.
  • Table 1: Shows best-case leaf exploration percentages for Star1 and Star2, with Star1 achieving savings of over 60% and Star2 achieving savings up to 95% for larger branching factors.
  • Table 2: Demonstrates average-case leaf exploration for Star1, showing savings consistently above 78% for larger branching factors.
  • Table 3: Details average-case cutoffs for Star2, highlighting that a significant portion of cutoffs occur during the probing phase.

Limitations and Future Work

  • Equal Probability Assumption: The presented algorithm assumes all outcomes of a probability node are equally likely. The authors note that the algorithm can be extended to handle more general probability distributions.
  • Synthetic Trees: The evaluation was performed on synthetic "*-complete N-ary trees" rather than real-world game data.
  • Future Work: The authors suggest that their Star-Minimax procedures can be integrated into existing game-playing programs by incorporating standard optimizations like static evaluation functions, transposition tables, and forward pruning, adapting them to the specific features of a particular game.

Summary updated

BibTeX
@inproceedings{ballard1982search,
  author = {Bruce W. Ballard},
  title = {{A Search Procedure for Perfect Information Games of Chance: Its Formulation and Analysis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1982},
}
Figure