游戏AI—纸牌游戏的求解策略

2026-08-04 更新：随着实验继续推进，问题已经从“怎样把 Beam Search 调得更强”，转变为“在不同信息边界下，什么搜索范式才合理”。本文保留原来的算法讨论，同时用最新对照结果修正早期结论。

一、引言：Klondike 的“信息迷雾”

Klondike（接龙）看似简单，实则是一个极好的算法实验场。它没有对手，却同时容纳了两种性质截然不同的问题：

这里有一个重要区别：知道暗牌是什么，不等于可以提前移动暗牌。 全信息 AI 仍然必须遵守正常规则，只是它能提前规划“为了释放那张关键牌，现在应该先搬动什么”。

这条信息边界会彻底改变算法的任务。全信息 AI 面对的是组合搜索；可见信息 AI 面对的则是信念更新、信息价值和风险控制。两者共享同一副牌，却生活在不同的世界里。

二、算法炼金术：从 12% 到两种独立 AI

项目早期的目标很直接：让 AI 每一步都选一个“看起来更好”的动作。随着实验深入，算法逐渐分化成四种思路：

Beam Search 的 12% 来自早期 100 局历史测试，与后两项的规则实现、样本和预算并不完全一致，不能直接当作严格倍数比较。真正具有可比性的是最后两项：它们在相同的 30 个发牌种子上独立运行。

这组对照给出了一个比“哪个算法更强”更有意思的结论：

知道暗牌带来的价值，不只是少走几步，而是把一个不完全信息决策问题，重新变成了确定性的路径搜索问题。

三、理论纵深：Beam Search 为什么会错过真正的解？

1. 分数并不单调

Klondike 中的“好局面”很难用单一分数描述。真正的获胜路径可能从一次短期退让开始：暂时不归组、先腾出空列、反复穿过牌库，甚至撤回一张 foundation 牌，只为几步之后翻开被压住的关键牌。

如果评价函数只奖励当前 foundation 数量、空列或已翻开的暗牌，那么某些必要的中间状态反而会得到低分。Beam Search 会在浅层就剪掉这些分支，此后再大的搜索深度也无法把它们找回来。

2. 宽度更大，不一定更好

Beam Search 用宽度换取时间与内存，但“扩大 beam 就会稳定变强”并不成立。Lemons 等人在 Beam Search: Faster and Monotonic 中专门讨论了这种非单调性，并提出结合 distance-to-go 估计的 Monobeam。

这对 Klondike 的启示是：搜索资源的多少，与搜索资源是否被投入正确方向，是两个问题。 如果评价函数无法识别真正的阻塞关系，更宽的 beam 可能只是更充分地搜索一批相似的错误路线。

3. 回溯是 Beam Search 缺失的记忆

Zhou 与 Hansen 的 Beam-Stack Search 把系统回溯重新引入 Beam Search：算法先快速找到次优解，再回到被剪掉的区间继续改进，最终可以收敛到最优解。

它解释了原始方案最想补上的能力——“如果眼前所有高分路线都失败，允许回头尝试当时的次优选择”。不过当前项目最终没有采用 Beam-Stack，而是直接选择更贴合全信息 Klondike 的启发式 DFS。

4. 从 NLP 借来的不是公式，而是警觉

在序列生成领域，Google 的 GNMT 技术报告 使用长度归一化与 coverage penalty，避免 Beam Search 偏爱过短输出，或遗漏输入中的关键信息。Meister、Vieira 与 Cotterell 的 Best-First Beam Search 则继续讨论单调评分、提前剪枝和搜索顺序。

这些方法不能直接移植到纸牌游戏，但它们提供了一种有价值的类比：

• 路径短，不代表离胜利更近；
• 当前得分高，不代表覆盖了所有关键目标；
• 一个好的启发式，必须同时表达“进度”和“尚未解决的依赖”。

四、从表面进度到阻塞关系

全信息 Klondike 最终更适合 DFS，不是因为 DFS 天生“更聪明”，而是因为它允许算法沿一条很长的假设链推进，并在失败后完整回溯。

Solvitaire 的研究表明，高性能纸牌求解器通常依赖四类思想：论文 · 源码

1. Transposition table： 不重复搜索已经见过的局面；
2. Symmetry breaking： 把空列、空槽位等对称状态折叠起来；
3. Dominance： 对不会损害未来选择的动作直接做出判断；
4. Streamliner： 主动排除理论上合法、实际上很少有价值的路线。

这类方法的共同点不是“算得更深”，而是让同样的预算只用于实质上不同的局面。

最新一轮实验还暴露了另一个细节：只统计暗牌总数是不够的。同样剩下 6 张暗牌，4+1+1 与 2+1+1+1+1 的难度完全不同。前者把风险集中在一条很深的依赖链上；后者给了算法更多并行释放的机会。

因此，评价函数应从“还有多少暗牌”继续追问：

• 暗牌集中在哪些列？
• 最深的阻塞链有多长？
• 哪个动作能创造真正有用的空列？
• 下一张被释放的牌能否立刻参与归组或构建？

这次更新把全信息 AI 从 25/30 提升到 26/30。数字只增加了一局，但它验证了一个更一般的判断：评价函数不应只描述局面有多好，还应该描述局面为什么被卡住。

五、另一种智能：在不知道答案时行动

全信息求解器回答的是“如果我知道所有牌，这副牌怎么解”。可见信息 AI 面对的问题更接近真实玩家：它只能记住已经看过的牌，再推断暗牌可能是什么。

ISMCTS（Information Set Monte Carlo Tree Search）的基本思想，是多次采样与当前观察相容的牌局，在这些“可能世界”中模拟后续动作，再选择整体表现更稳健的一步。

它最大的风险是信息泄漏：如果搜索节点、评价函数或动作排序不小心使用了采样世界中的暗牌身份，算法表面上是在处理未知，实际上仍然在偷看答案。真正可信的对比，必须让未知牌始终停留在信念层，而不是悄悄进入决策状态。

这也解释了为什么“信息更少的算法偶尔赢过全信息算法”并不矛盾。有限预算下，搜索结果不仅取决于信息量，也取决于分支排序和随机探索。更多信息扩大了可利用的决策空间，但不会自动保证某一次有限搜索更成功。

六、当前结果：不要只看两个百分比

当前严格对照使用固定 deal seeds 0..29、独立算法随机种子、相同规则和每局步数上限；全信息搜索的状态预算固定为 20,000。两套 AI 分别从同一初始牌局开始，彼此不回退，也不合并胜局。

成对结果比单独的胜率更有解释力：

当前差值是 7 局、23.4 个百分点。它说明暗牌信息在这组牌局中确实产生了明显价值，但 30 局仍然是很小的样本；两个 Wilson 区间都相当宽，远不足以得出稳定的总体胜率。

同样需要注意：全信息 AI 的失败只代表“在 20,000 个状态内没有找到完整解”，不代表已经证明牌局无解；可见信息 AI 的失败也可能来自信念采样和在线策略，而不是牌局本身不可解。

七、上限的三种口径

原文中的 43%、82% 与当前 86.7%，分别来自不同规则、信息条件和实验方法。把它们排列在一条“算法越来越强”的直线上，会得到错误结论。

1. 当前有限预算实测

本项目的 86.7% / 63.3%，是当前实现对 30 个固定种子的经验结果。它会随搜索预算、启发式、采样次数和样本规模变化。

2. 全信息可解率估计

Blake 与 Gent 使用 Solvitaire 报告 thoughtful Klondike 的可解率为 81.945 ± 0.084%。CP 2025 的 Constraint Models for Klondike 进一步区分规则，将 Deal Three 更新为 81.942 ± 0.080%，将 Deal One 更新为 90.454 ± 0.090%。

本项目讨论的是 Draw One，因此 90.454% 是更接近的研究参照。但它仍然是大规模实验对“牌局是否可解”的估计，不保证任意有限预算求解器都能达到。

3. 可见策略的胜率下界与上限

Jupiter Scientific 曾在 Draw Three、无限回收规则下进行 442 局“human Monte Carlo”，其中赢了 189 局，得到约 43%。原报告把它解释为良好人类策略的经验下界，而不是所有玩家的期望胜率。原始报告

可见信息策略的真正上限仍未确定。它取决于允许的记忆、思考时间、随机策略、撤回规则和发牌方式。这里不存在一个可以脱离规则直接引用的“人类理论上限”。

八、下一步：两条不同的研究路线

全信息方向的核心问题，是怎样更准确地表达隐藏牌之间的依赖关系。比起继续调大搜索宽度，更值得探索的是依赖图、anytime search，以及 DFS 与 SAT / CP 约束模型的混合。

可见信息方向的核心问题，则是怎样让信念跨动作保持一致。持续粒子信念、POMCP / ISMCTS、信息价值评分，都比“每一步重新猜一副牌”更接近真正的不完全信息推理。

实验方法也需要同步升级：先扩大到 100，再到 1,000 副固定牌局；既报告状态预算，也报告相同 wall-time；同时给出 Wilson 区间和成对胜负，而不是只展示一个最好看的百分比。

九、结语：从纸牌看架构思维

Klondike 的求解过程，本质上是在有限资源（算力与内存）、**状态依赖（被压住的关键牌）和信息不确定性（暗牌）**之间寻找平衡。

这种带回溯的搜索，与复杂交易链路仍然有相似之处：

• 当前路径失败时，需要退回稳定状态并尝试替代路线；
• 搜索启发式像业务分级路由，决定有限资源先投向哪里；
• 状态去重与幂等控制一样，避免系统反复处理同一个局面；
• 最重要的是，规则、事实与推断必须分层，不能把“猜测”伪装成“已知”。

纸牌游戏给我的最终提醒是：搜索之前，先定义参与者能看见什么；优化之前，先定义我们测量的究竟是什么。

附录：核心文献

下面保留原文中的主要参考文献，并按用途区分：

• Klondike 求解与可解率： Blake & Gent（Solvitaire）、Dang 等（约束模型）；
• Beam Search 理论： Beam-Stack Search、Best-First Beam Search、Monobeam；
• 跨领域启发： GNMT 的长度归一化与覆盖惩罚；
• 历史经验数据： Jupiter Scientific 报告。它不是同行评审论文，且采用 Draw Three，应与本项目结果分开理解。

@article{blake2026winnability,
  title={The Winnability of Klondike Solitaire and Many Other Patience Games},
  author={Blake, Charlie and Gent, Ian P.},
  journal={Journal of Artificial Intelligence Research},
  volume={85},
  year={2026},
  doi={10.1613/jair.1.17167}
}

@inproceedings{dang2025constraint,
  title={Constraint Models for Klondike},
  author={Dang, Nguyen and Gent, Ian P. and Nightingale, Peter and
          Ulrich-Oltean, Felix and Waller, Jack},
  booktitle={31st International Conference on Principles and Practice of
             Constraint Programming (CP 2025)},
  series={Leibniz International Proceedings in Informatics (LIPIcs)},
  volume={340},
  pages={9:1--9:20},
  year={2025},
  doi={10.4230/LIPIcs.CP.2025.9}
}

@software{blake2019solvitaire,
  title={Solvitaire},
  author={Blake, Charlie and Gent, Ian P.},
  year={2019},
  doi={10.5281/zenodo.3529524},
  url={https://github.com/thecharlesblake/Solvitaire}
}

@inproceedings{zhou2005beamstack,
  title={Beam-Stack Search: Integrating Backtracking with Beam Search},
  author={Zhou, Rong and Hansen, Eric A.},
  booktitle={Proceedings of the Fifteenth International Conference on
             Automated Planning and Scheduling},
  pages={90--98},
  publisher={AAAI Press},
  year={2005}
}

@article{meister2020bestfirst,
  title={Best-First Beam Search},
  author={Meister, Clara and Vieira, Tim and Cotterell, Ryan},
  journal={Transactions of the Association for Computational Linguistics},
  volume={8},
  pages={795--809},
  year={2020},
  doi={10.1162/tacl_a_00346}
}

@inproceedings{lemons2022monobeam,
  title={Beam Search: Faster and Monotonic},
  author={Lemons, Sofia and Linares L{\'o}pez, Carlos and
          Holte, Robert C. and Ruml, Wheeler},
  booktitle={Proceedings of the Thirty-Second International Conference on
             Automated Planning and Scheduling},
  volume={32},
  pages={222--230},
  year={2022},
  doi={10.1609/icaps.v32i1.19805}
}

@article{wu2016gnmt,
  title={Google's Neural Machine Translation System: Bridging the Gap
         between Human and Machine Translation},
  author={Wu, Yonghui and Schuster, Mike and Chen, Zhifeng and others},
  journal={CoRR},
  volume={abs/1609.08144},
  year={2016},
  url={https://arxiv.org/abs/1609.08144}
}

@techreport{jupiter2013winning,
  title={Winning Chances for Klondike Solitaire},
  author={{Jupiter Scientific Staff}},
  institution={Jupiter Scientific},
  year={2013},
  url={https://www.jupiterscientific.org/sciinfo/KlondikeSolitaireReport.html},
  note={Historical human Monte Carlo report using Draw Three; not peer reviewed}
}

与 AI 的讨论

• ChatGPT
• 豆包
• Gemini
• Claude

最后修改于 2026-05-02