用集合方法加速桥牌残局求解，10^27种状态全解仅需10^15次运算
Set-Based Retrograde Analysis: Precomputing the Solution to 24-card Bridge Double Dummy Deals
- 将状态按游戏价值分组处理，避免重复计算
- 24张牌残局全解，搜索量比传统方法少1000倍
- 适合需要深度求解的棋类与卡牌博弈研究者
回溯分析常用于游戏程序中求解终局状态，通过逆向推演计算尽可能多的状态最优解。本文提出集回溯分析（setrograde analysis），通过操作具有相同游戏价值的状态集合实现相同目标。该算法在桥牌双人无将残局求解中得到验证：对于剩余24张牌（共10^27种状态，经预处理可压缩至10^15种）的对局，实现了全部强解。相比传统回溯算法，集回溯算法减少了10^3倍的搜索操作，生成数据库条目减少10^4倍。在适用领域，该方法使回溯搜索达到前所未有的深度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。