The Winnability of Klondike Solitaire and Many Other Patience Games

Each language version is independently generated for its own context, not a direct translation.

这是一篇关于**“纸牌接龙（Solitaire）到底有多少局能赢”的学术论文。为了让你轻松理解，我们可以把这篇论文想象成一次“用超级计算机给所有纸牌游戏做体检”**的大工程。

1. 核心问题：我们真的知道能赢吗？

想象一下，你坐在电脑前玩 Windows 自带的“克朗代克（Klondike）”接龙。你经常觉得：“这局牌发得真烂，肯定赢不了。”或者“这局牌太好了，闭着眼都能赢。”

但过去，数学家们一直不知道：在随机发牌的情况下，到底有多少比例的牌局是“理论上可以赢”的？
这就好比问：“如果你随机买一张彩票，中奖的概率是多少？”以前大家只能猜，或者只能算出大概的范围。对于克朗代克接龙，这个“能赢的概率”甚至被称为**“应用数学界的尴尬”**，因为玩了这么多年，大家居然算不准。

2. 主角登场：Solvitaire（解牌机）

作者们（Charlie Blake 和 Ian Gent）没有为每一种纸牌游戏单独写一个程序，而是发明了一个**“万能解牌机器人”**，名字叫 Solvitaire。

它的超能力： 它就像一个**“全知全能的侦探”**。你只需要给它一张“规则说明书”（用一种简单的 JSON 语言写成的），它就能读懂任何纸牌游戏的玩法。
它的任务： 它不是像人类那样“试着玩”，而是穷尽所有可能性。它会像疯了一样，在几秒钟内模拟几百万种走法，看看这副牌到底有没有一条路能通向胜利。
它的技巧： 为了跑得更快，它用了很多 AI 技巧：
- 记忆宫殿（转置表）： 它记得自己走过的路，如果发现自己又回到了刚才的某个状态，它就不会再傻乎乎地重走一遍。
- 对称性打破： 如果桌子上的四个空位长得一模一样，它知道把红桃 A 放在第一个空位和放在第二个空位其实是一样的，所以它只试一种，省下一半力气。
- ** dominance（优势策略）：** 这是它最聪明的地方。比如，如果一张牌能直接放到“基础区”（Foundation），它通常就会直接放，因为它证明：“只要这步棋能赢，那么现在就走这一步绝对不会输。” 这就像下棋时，如果有一步棋能直接吃对方老帅，你就不会犹豫去走别的棋。

3. 惊人的发现：我们算得有多准？

以前，对于克朗代克接龙（Windows 里那个），大家只知道大概能赢 80% 左右，误差很大（比如 $\pm 3\%$ ）。这就像说“明天降雨概率是 80%，误差 3%"，听起来很模糊。

Solvitaire 做到了什么？
它把误差缩小到了 $\pm 0.08\%$ ！

以前的结论： 克朗代克接龙能赢的概率大约是 81.9%（误差很大）。
现在的结论： 在“聪明版”（即你知道所有背面牌是什么，相当于开了上帝视角）的规则下，克朗代克接龙能赢的概率是 81.945%，误差极小。
意义： 这就像以前我们说“地球到月球的距离大概是 38 万公里”，现在我们能精确到“是 384,400 公里，误差只有几米”。这是30 倍的精度提升！

4. 他们研究了什么？

他们不仅研究了 Windows 里的接龙，还像**“游戏测试员”**一样，测试了 73 种 不同的纸牌游戏变体，包括：

FreeCell（空当接龙）： 几乎 100% 能赢（除了极少数特例）。
Spider（蜘蛛纸牌）： 能赢的概率也很高。
Canfield： 以前有人猜能赢 71%，现在算出来是 71.245%。
甚至他们自己发明了一些新规则，看看如果改变规则（比如一次发几张牌、能不能把牌拿回来重发），胜率会怎么变。

一个有趣的发现：
如果你把克朗代克接龙的规则改得“更严”（比如一次只能发 1 张牌，或者不能把牌拿回来），胜率会暴跌。

一次发 3 张（标准版）：胜率约 82%。
一次发 7 张：胜率直接掉到 23%。
这说明，发牌的方式对运气的影响巨大。

5. 为什么这很重要？

填补空白： 以前很多纸牌游戏的胜率是未知的，或者只有爱好者猜的。现在有了科学数据。
发现 Bug： 在测试过程中，Solvitaire 发现了一些以前其他解牌程序里的错误。就像两个侦探互相检查，发现对方算错了，然后修正了历史数据。
致敬历史： 论文开头提到，蒙特卡洛方法（一种用随机模拟来解决问题的数学方法）的发明者 Stanislaw Ulam，当年就是在病床上玩纸牌时，为了算出“能赢的概率”才发明了这种方法。这篇论文用现代 AI 技术，终于完美回答了 Ulam 当年那个未解的谜题。

6. 总结：这就像什么？

想象一下，纸牌游戏是一个巨大的**“迷宫”**。

以前的玩家和数学家： 只能站在迷宫口，凭感觉猜：“我觉得大概有一半的路是通的。”
Solvitaire： 是一个拥有无限体力的机器人。它把迷宫里的每一条路都走了一遍。如果有一条路能通到终点，它就记录“能赢”；如果所有路都走不通，它就记录“必输”。
结果： 它画出了一张精确到小数点后三位的地图，告诉我们：在这个迷宫里，81.945% 的入口是可以走通的。

一句话总结：
这篇论文用一台超级聪明的“万能解牌机器人”，把纸牌游戏从“凭运气猜”变成了“精确计算”，不仅算出了 Windows 接龙的真实胜率，还顺便修正了数学界几十年的“尴尬”数据。

Each language version is independently generated for its own context, not a direct translation.

这是一份关于论文《The Winnability of Klondike Solitaire and Many Other Patience Games》（克朗代克纸牌游戏及许多其他耐心游戏的可赢性）的详细技术总结。该论文发表于《人工智能研究杂志》(JAIR)，由 Charlie Blake 和 Ian Gent 撰写。

1. 研究问题 (Problem)

核心问题：单玩家纸牌游戏（通常称为“耐心游戏”或“Solitaire"）的可赢性（Winnability）百分比是多少？即，在随机发牌的情况下，有多少比例的游戏局面是可以通过合法移动赢得的？
背景与痛点：
- 尽管这类游戏（如 Windows 自带的克朗代克 Klondike）非常流行，但其可赢性的精确统计长期以来是应用数学界的“尴尬”之一。
- 以往的研究多针对特定游戏开发专用求解器，缺乏通用性。
- 对于包含隐藏牌的游戏（如标准 Klondike），学术界通常研究“深思熟虑版”（Thoughtful variant），即假设玩家在游戏开始时就知道所有隐藏牌的花色和点数。
- 现有的估计往往置信区间较大，或者仅由爱好者通过非学术方法得出，缺乏严谨的数学证明和统一的评估标准。

2. 方法论 (Methodology)

作者开发了一个名为 Solvitaire 的通用人工智能求解器，用于解决 35 种不同游戏的 73 个变体。

2.1 核心算法：深度优先搜索 (DFS)

策略：采用深度优先回溯搜索（Depth-First Backtracking Search）来穷举状态空间，以确定一个游戏实例是否可解。
目标：优先确保能够确定一个局面是可解还是不可解，而不是寻找最短路径。这使得算法在处理不可解实例时非常高效。
状态管理：使用“回溯（Trailing）”而非“复制（Copying）”来保存和恢复状态，以减少内存开销。

2.2 关键 AI 优化技术

为了在巨大的状态空间中实现高效搜索，Solvitaire 集成了多种 AI 技术：

换位表 (Transposition Tables)：
- 使用缓存记录已访问的状态，避免重复搜索相同的局面。
- 采用压缩表示法以节省内存，并处理循环（Loops）。
对称性破缺 (Symmetry Breaking)：
- 将状态转换为规范形式（Canonical Form）。例如，如果牌堆之间不可区分，则按顺序排列；如果游戏不依赖花色，则忽略花色信息。这极大地减少了搜索空间。
支配性 (Dominances)：
- 这是论文的核心贡献之一。作者定义并首次证明了两个关键支配性规则的正确性：
  - 安全移动至基础牌堆 (Safe Moves to Foundations)：当一张牌可以安全地移动到基础牌堆（Foundation）时，强制执行该移动，无需回溯。论文证明了在特定构建规则下，这种贪心策略不会导致漏解。
  - 未完成牌堆的移动 (Tableau Moves of Incomplete Piles)：限制牌堆中部分牌组的移动。只有当被移开的牌组上方的那张牌可以立即移动到基础牌堆时，才允许移动该部分牌组。作者给出了严格的数学证明，表明这种限制不会排除任何可解路径。
流化器 (Streamliners)：
- 一种启发式技术，通过施加可能不总是成立但通常成立的约束来加速搜索。
- 如果流化器未能找到解，系统会自动回退到完整搜索（Smart Streamliner），确保最终结果的准确性。
灵活的规则描述语言：
- 游戏规则通过 JSON 格式定义，而非硬编码。这使得 Solvitaire 能够处理极其多样的游戏规则（如不同的发牌方式、构建规则、空间填充规则等）。

2.3 实验设计

蒙特卡洛方法：通过生成大量随机实例（使用 Mersenne Twister 伪随机数生成器），统计可解实例的比例。
置信区间：使用 Wilson 方法计算 95% 置信区间，确保统计结果的严谨性。
游戏关系利用：利用游戏规则的强弱关系（例如，允许“回退”的游戏比不允许的更弱），通过在一个游戏中确定的结果来推断另一个游戏的结果，从而大幅减少计算量。

3. 主要贡献 (Key Contributions)

通用求解器 Solvitaire：
- 第一个能够处理如此广泛变体（35 种游戏，73 个变体）的通用求解器，无需针对每个游戏重新编写代码。
精确的可赢性数据：
- 将克朗代克（Klondike）“深思熟虑版”的可赢性置信区间缩小了 30 倍，从之前的 $\pm 3\%$ 左右提升至 $\pm 0.084\%$ （可赢性为 81.945%）。
- 提供了 73 个游戏变体的精确可赢性数据，其中绝大多数是首次发表或显著优于以往结果。
理论证明：
- 首次为耐心游戏中两个广泛使用的“支配性”规则提供了数学正确性证明，解决了长期以来依赖经验直觉的问题。
发现并修复 Bug：
- 通过与现有专用求解器（如 Wolter 的 Canfield 求解器和 Birrell 的 Klondike 求解器）进行大规模对比，发现了这些专用求解器中存在的隐蔽错误（包括错误的支配性规则和随机数生成器偏差），并修正了它们。
规则变体分析：
- 系统分析了克朗代克规则变化（如发牌数量、是否允许回退、空间填充规则等）对可赢性的具体影响。例如，发现随着发牌数量增加，可赢性急剧下降；允许“回退”（Worrying back）虽然略微增加可赢性，但在某些情况下是必须的。

4. 关键结果 (Results)

克朗代克 (Klondike)：
- 标准版（深思熟虑，发 3 张）：81.945% ± 0.084%。
- 发 1 张：约 90.48%。
- 发 7 张：约 23.78%。
- 证明了“回退”操作在约 0.5% 的可解局中是必须的。
其他游戏：
- FreeCell：4 个空位版可赢性约为 99.99888%（与之前研究一致，但验证了第 11982 号牌局不可解）。
- Canfield：可赢性约为 71.245%。
- Black Hole：约 86.944%。
- Accordion：接近 100% (99.99948%)。
- British Canister：极低，仅约 0.000129%。
性能：
- 实验总共消耗了约 30 年的 CPU 时间。
- 在大多数游戏中，Solvitaire 的表现优于或接近现有的专用求解器，特别是在处理不可解实例的判定上。

5. 意义与影响 (Significance)

填补学术空白：这是首次对多种耐心游戏进行大规模的、统一的学术性可赢性研究。此前该领域多由爱好者主导，缺乏系统性和严谨性。
致敬 Ulam：斯坦尼斯瓦夫·乌拉姆（Stanislaw Ulam）发明蒙特卡洛方法的初衷正是为了计算纸牌游戏的可赢性。本文使用现代蒙特卡洛方法和 AI 搜索技术，精确回答了乌拉姆当年提出的问题，具有历史性的呼应意义。
AI 技术的验证：展示了深度优先搜索结合现代 AI 优化技术（如支配性、对称性破缺）在处理复杂组合搜索问题上的强大能力。
开源与可复现：
- 所有实验数据、代码（Solvitaire）和规则定义均已开源。
- 为未来的研究者提供了基准测试集和验证工具，有助于进一步探索纸牌游戏的数学性质。
未来方向：
- 论文指出，目前解决的是“深思熟虑版”（全知视角）。对于包含隐藏信息且不允许悔棋的“真实”游戏，其最优策略下的真实可赢性仍然是一个未解之谜，且难度极大。

总结：
这篇论文通过开发通用的 AI 求解器 Solvitaire，结合严谨的数学证明和大规模计算实验，彻底革新了我们对单玩家纸牌游戏可赢性的认知。它不仅提供了前所未有的精确统计数据，还通过理论证明和代码验证，解决了该领域长期存在的准确性和一致性问题，是应用数学与人工智能结合的典范之作。