按年被提到
20192019 · 2 次2026
算法与数据结构›游戏复杂度与博弈论·arXiv:1906.12314 · cs.AI

The Winnability of Klondike Solitaire and Many Other Patience Games

Klondike 纸牌与多种耐心纸牌游戏的可胜率
Charlie Blake, Ian P. Gent · 2019

用通用搜索程序 Solvitaire 精确估计多种纸牌游戏的可胜率

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 5 人首次 2019-07-02 · 最近 2025-02-05
5不同的人
5活跃月份
5讨论串
2被引(OpenAlex)

论文展示了通用 AI 程序 Solvitaire 能以 ±0.1% 或更好的 95% 置信区间,确定 35 种单人纸牌游戏共 73 个变体的可胜率。例如在「谨慎」变体(玩家知道所有牌)中,Klondike 的可胜率为 81.945% ± 0.084%,置信区间比此前最好结果缩小约 30 倍。Solvitaire 基于深度优先搜索,并用到转置表、对称性消除、支配关系等技术,论文首次给出两个关键支配关系的正确性证明。

HN 为什么提它

HN 评论者在讨论纸牌游戏胜率这个著名未解难题时引用它,作为 Klondike 可胜率最新进展的出处。

实证研究难度 3 / 5约 45 分钟经得起时间
读之前最好知道
1深度优先搜索
2约束求解与搜索剪枝
3转置表(transposition table)
4置信区间与蒙特卡洛采样

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用sourcepluck · 2024-12

“Some progress has been made on Solitaire here, although I understand it's still not fully peer-reviewed (I think)”

提到纸牌接龙已有进展,但似乎尚未完全通过同行评审
How God Plays Chess (2018)原评论 ↗
引用palsecam · 2025-01

“Here we show that a single general purpose Artificial Intelligence program, called “Solvitaire”, can be used to determine the winnability percentage of 45 different single-player card games”

引其摘要:Solvitaire 能测定 45 种单人纸牌游戏的可胜率
Hitting the Jackpot: The Birth of the Monte Carlo Method – LANL (2023)原评论 ↗
被提交为 story · 3 次