2024/11/13 by Nathan Sturtevant, Stone, Isaac, Sturtevant, Nathan R. +2 · 1 citation
Decision Sciences · #Auction Theory and Applications
paper · pdf · doi:10.48550/arxiv.2411.09089
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 (1027 states, which can be reduced to 1015 states using preexisting techniques), we strongly solve all deals. The setrograde algorithm performs a factor of 103 fewer search operations than a standard retrograde algorithm, producing a database with a factor of 104 fewer entries. For applicable domains, this allows retrograde searching to reach unprecedented search depths.