Set-Based Retrograde Analysis: Precomputing the Solution to 28-card Bridge Double Dummy Deals

Isaac Stone, Nathan R. Sturtevant, Jonathan SchaefferIJCAI 2025 · DOI

Abstract

Retrograde analysis has traditionally struggled with the astronomical state spaces of Bridge endgames. This paper presents Setrograde Analysis, a novel approach that groups game outcomes into generalized sets rather than evaluating individual positions. By replacing specific low-rank cards with generic placeholders, the algorithm successfully precomputed solutions for all 7-trick (28-card) Bridge deals. This represents a state space of $10^{30}$ positions, compressed into a 1.4 TiB database—the largest endgame database in gaming history.

Introduction

Retrograde analysis is a cornerstone of game AI, enabling perfect play in endgames by working backward from terminal states. While highly effective for games like Checkers and Chess, Bridge presents a unique "state-space explosion." Even with only 7 tricks remaining, the number of possible deals reaches $10^{30}$. Traditional state-based retrograde analysis would require hundreds of petabytes of storage, rendering the problem unsolvable for decades. Because of this challenge, virtually no progress had been made in Bridge endgame databases for over 25 years.

Methodology: From States to Sets

The core innovation of this work is the transition from individual game states to consistent sets. The authors propose Setrograde Analysis, which leverages the fact that in many Bridge endgames, the specific ranks of low cards do not influence the final trick-win outcome.

Generalization and Rank Reduction

Instead of solving for a specific hand (e.g., North holding $\spadesuit$9, $\spadesuit$8, and $\spadesuit$7), the algorithm identifies a "set" of deals where these cards are treated as generic placeholders ($x$). If all deals within this set yield the same game value, they can be stored as a single entry. This generalization allows a single solution to cover thousands or millions of individual deals.

Figure 1: The generalization process, where specific low-rank cards are replaced by generic 'xx' placeholders to form a consistent set.

Set-Space Reduction and Parallelization

The algorithm iteratively solves "independent states"—positions not yet covered by the database—and attempts to generalize them into the largest possible consistent sets. This approach achieved a 5-order-of-magnitude reduction in the number of required database entries. To handle the remaining computational load, the problem was partitioned by deal "shape" (suit distribution) and distributed across high-performance computing clusters, totaling approximately 140 CPU years of computation. This represents a 3-order-of-magnitude reduction in computing resources compared to traditional state-based methods.

Results and Impact

The resulting 28-card Bridge Double Dummy (DD) database is a landmark in computational game theory.

  • Storage Efficiency: Through generalization and symmetry reduction, the $10^{30}$ states were compressed into just 1.4 TiB. On average, each byte of storage represents over 100,000 individual game states.
  • Solver Performance: Integrating the database into existing Double Dummy solvers, such as Partition Search, reduced the search tree size by 90% for 7-trick problems.
  • Validation: The database was verified against standard solvers using 500 million sampled positions, confirming an error rate of less than 0.0000005% with 99% confidence.

Conclusion and Future Work

Setrograde Analysis demonstrates that even "unsolvable" state spaces can be tamed through intelligent generalization. While the 28-card database is a massive milestone, the ultimate challenge remains the full 52-card Bridge deck. The authors suggest that with current technology and further refinements to set-ordering and generalization logic, a complete Bridge tablebase may finally be within reach. This methodology also holds promise for other games with high information density and equivalent low-value states, such as Skat or Chinese Checkers.

Summary updated

BibTeX
@inproceedings{stone2025set,
  author = {Isaac Stone and Nathan R. Sturtevant and Jonathan Schaeffer},
  title = {{Set-Based Retrograde Analysis: Precomputing the Solution to 28-card Bridge Double Dummy Deals}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/995},
}
Figure