Set-Based Retrograde Analysis: Precomputing the Solution to 24-card Bridge Double Dummy Deals
This work addresses the computational challenge of solving complex card games like Bridge for researchers and AI game developers, representing an incremental improvement in retrograde analysis techniques.
The paper tackled the problem of solving Bridge double dummy card-play deals with 24 cards remaining by introducing setrograde analysis, which operates on sets of states with the same game value, resulting in a factor of 10^3 fewer search operations and a database with 10^4 fewer entries compared to standard retrograde algorithms.
Retrograde analysis is used in game-playing programs to solve states at the end of a game, working backwards toward the start of the game. The algorithm iterates through and computes the perfect-play value for as many states as resources allow. We introduce setrograde analysis which achieves the same results by operating on sets of states that have the same game value. The algorithm is demonstrated by computing exact solutions for Bridge double dummy card-play. For deals with 24 cards remaining to be played ($10^{27}$ states, which can be reduced to $10^{15}$ states using preexisting techniques), we strongly solve all deals. The setrograde algorithm performs a factor of $10^3$ fewer search operations than a standard retrograde algorithm, producing a database with a factor of $10^4$ fewer entries. For applicable domains, this allows retrograde searching to reach unprecedented search depths.