Set-Based Retrograde Analysis: Precomputing the Solution to 28-card Bridge Double Dummy Deals
Authors: Isaac Stone, Nathan R. Sturtevant, Jonathan Schaeffer
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | The 7-trick computation represents the largest endgame database to date in any game. ... This paper describes our set-based approach to endgame databases, making the following contributions. ... Setrograde Analysis is demonstrated using 28-card Bridge deals. ... Here we discuss Setrograde Analysis performance on Bridge database generation. ... Table 1 shows one measure of Setrograde s performance. ... In Table 2 the storage and computational resources for Retrograde and Setrograde Analysis are presented. |
| Researcher Affiliation | Academia | Isaac Stone1 , Nathan R. Sturtevant1,2 , Jonathan Schaeffer1 1University of Alberta 2Alberta Machine Intelligence Institute (Amii) EMAIL |
| Pseudocode | Yes | Algorithm 1 Retro/Setrograde Analysis ... Algorithm 2 General Setrograde Analysis ... Algorithm 3 Setrograde Helper Functions |
| Open Source Code | No | No explicit statement or link for open-source code for the methodology described in this paper is provided. |
| Open Datasets | No | The paper does not use a publicly available or open dataset for its experiments. Instead, it describes solving the state space of 28-card Bridge deals and creating an endgame database. |
| Dataset Splits | No | The paper describes solving the entire state space of 28-card Bridge deals, rather than using a pre-existing dataset with train/test/validation splits. Validation is mentioned for the generated databases, but this is not dataset splitting for model training. |
| Hardware Specification | Yes | The 24card databases and some of the 28-card databases were computed on a machine with 48 cores, 187 GB of RAM, and 256 GB of swap using an Intel(R) Xeon(R) Gold 6248R CPU @ 3.00GHz. The remainder of the 28-card databases were produced using several clusters provided by the Digital Research Alliance of Canada. |
| Software Dependencies | Yes | The program is written in Julia, and compiled in version 1.8 or higher using the LLVM compiler. All code is compatible with version 1.11. |
| Experiment Setup | Yes | Generalization: In Retrograde Analysis, when a state is reached that is not in the database, it will have its value computed and added to the database. Instead, Setrograde Analysis finds a generalization of the state (a set) in which all states have the same value (consistent). It does this using a generate-and-test approach, where sets are generated until the best consistent set (along some metric) is found. In Bridge, this is done by replacing some cards with x s. ... Set Representation: As discussed in the background section, and depicted in Fig. 1, representing sets of deals with low cards unspecified is not a new idea. ... Low-Cost Generalization: State generalization uses binary search. The lowest card in a suit can always be marked as x and it is possible that an entire suit (13 cards) could be xs. Hence for each suit a binary search is done on the number of xs. The program starts in the middle of the range and introduces that number of xs. Depending on whether the resulting set is consistent, the search either tries adding more or eliminating some xs. ... Low-Cost Querying: State lookups, matching a state to a set to retrieve a value, are achieved using a depth-limited tree data structure. At each node, a bitwise AND operation can be used to determine whether a state is in a set. |