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.
Despite its success, PIMC has two critical flaws:
- Strategy Fusion: It assumes the player can choose different moves for different worlds at the same decision point, which is impossible in practice.
- 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.
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