The α μ Search Algorithm for the Game of Bridge

Tristan Cazenave, Véronique Ventos

Abstract

Computer Bridge has long relied on Perfect Information Monte Carlo (PIMC) sampling, which suffers from fundamental theoretical flaws like strategy fusion and non-locality. This paper introduces $\alpha\mu$, a novel anytime heuristic search algorithm that represents game states as Pareto fronts of outcome vectors across multiple possible worlds. By accounting for the interdependence of strategies across different card distributions, $\alpha\mu$ overcomes PIMC's limitations and demonstrates superior performance in competitive Bridge scenarios.

Introduction: The Limitations of PIMC

In imperfect information games like Bridge, players must make decisions without knowing the exact distribution of cards. The traditional state-of-the-art approach is Perfect Information Monte Carlo (PIMC). As shown in the figure below, PIMC samples several possible "worlds" (card distributions consistent with the bidding), solves each as a perfect information game using a Double Dummy Solver (DDS), and averages the results to select a move.

Algorithm 1 (PIMC) and a sample hand illustrating the non-locality problem where averaging independent world outcomes leads to sub-optimal strategies.

Despite its success, PIMC has two critical flaws:

  1. Strategy Fusion: It assumes the player can choose different moves for different worlds at the same decision point, which is impossible in practice.
  2. Non-locality: It makes local decisions based on averages that may not be globally optimal across all possible distributions.

The αμ Search Algorithm

To address these issues, the authors propose $\alpha\mu$, which generalizes PIMC by treating game states as vectors of outcomes $[o_1, o_2, ..., o_n]$ across $n$ possible worlds. Instead of a single scalar value, each node in the search tree returns a Pareto front of these vectors.

The αμ search tree represents states as vectors of outcomes across multiple worlds, enabling multi-dimensional pruning and accounting for strategy interdependence.

In this framework:

  • Max Nodes (Declarer): The algorithm takes the union of Pareto fronts from all available moves and prunes dominated vectors. A vector is dominated if another vector performs at least as well in every world.
  • Min Nodes (Defenders): The algorithm assumes defenders have perfect information (a pessimistic heuristic) and computes the minimum outcome across worlds for combinations of moves.

The algorithm is an "anytime" search because it uses a parameter $M$ to control search depth. At $M=0$, it uses DDS; at $M=1$, it behaves similarly to PIMC; and at $M > 1$, it begins to account for information gain and complex dependencies.

Optimizations and Performance

Searching Pareto fronts is computationally expensive. The authors implemented several optimizations to make the algorithm viable for real-time play:

  • Transposition Tables: Storing previous search results to avoid redundant calculations.
  • Early and Root Cuts: Pruning branches where the current Pareto front is already dominated by a parent node's front.

These optimizations reduced the average move time from over 18 seconds to just 1.2 seconds for a depth $M=3$ search.

Results and Conclusion

Evaluation on 500 Bridge deals showed that $\alpha\mu$ ($M=3$) significantly outperforms PIMC ($M=1$), achieving a 63.2% win rate compared to 62.4% for the baseline. While the numerical gap is modest, it represents a meaningful improvement over a highly optimized baseline. More importantly, $\alpha\mu$ correctly handles "Discovery Play" and other advanced strategies that PIMC fundamentally cannot model. Future work includes optimizing for overtricks and refining the defender model to account for their uncertainty.

Summary updated

Abstract

αμ is an anytime heuristic search algorithm for incomplete information games that assumes perfect information for the opponents. αμ addresses the strategy fusion and non-locality problems encountered by Perfect Information Monte Carlo sampling. In this paper αμ is applied to the game of Bridge.
BibTeX
@inproceedings{cazenave2019search,
  author = {Tristan Cazenave and Véronique Ventos},
  title = {{The α μ Search Algorithm for the Game of Bridge}},
  booktitle = {Base},
  year = {2019},
  doi = {10.48550/arxiv.1911.07960},
}
Figure