Proceedings

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

Isaac Stone, Nathan R. Sturtevant, Jonathan Schaeffer

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8948-8955.

https://doi.org/10.24963/ijcai.2025/995

Keywords

  • Multidisciplinary Topics and Applications: MTA: Databases
  • Search: S: Game playing
  • Multidisciplinary Topics and Applications: MTA: Game playing

Abstract

Among the most popular games played worldwide, Bridge stands out for having had little AI progress for over 25 years. Ginsberg's Partition Search algorithm (1996) was a breakthrough for double-dummy Bridge play, allowing a program to reason about sets of states rather than individual states. Partition Search supports the current state of the art for both bidding and cardplay. In the time since, virtually no progress has been made in Bridge bidding. Inspired by Ginsberg's idea, this paper presents Setrograde Analysis, a new set-based algorithm for perfectly solving Bridge hands. Using this approach, we have solved all 7-trick (28-card) hands — 10^30 states, which can be reduced to 10^17 unique states using preexisting techniques. This was done by considering five orders of magnitude fewer sets than the traditional state-based Retrograde Analysis algorithm. This work suggests that the entire 13-trick (52-card) state space can be solved with modern technology using this new approach.

The 7-trick computation represents the largest endgame database to date in any game.

Isaac Stone, Nathan R. Sturtevant, and Jonathan Schaeffer. 2025. Set-Based Retrograde Analysis: Precomputing the Solution to 28-card Bridge Double Dummy Deals. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8948–8955. https://doi.org/10.24963/ijcai.2025/995
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards