Windows游戏中的NP完全问题

上篇文章扫雷是NP完全问题之后，You Xu提到＂不光扫雷是NP 完全问题，空当接龙问题也极有可能是一个NP完全问题。目前最好的通用 planner只能解半副牌＂。他说对了，不光扫雷，Windows自带的游戏都是NP完全的。Windows自带的游戏除了扫雷，还有空当接龙和蜘蛛纸牌。

论文：Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.

论文：Springer Berlin, Heidelberg, The Complexity of Solitaire, Mathematical Foundations of Computer Science 2007: 182-193, 2007

顺便提一下蜘蛛纸牌的可以获胜的概率高达82-91.5%。而我平时自己玩的时候20%都不到。差距啊。

写于2008年六月 13日

At 2008.06.14 05:02, 哈哈哈 said:

短短的

[Reply]
At 2008.08.30 13:01, 严酷的魔王 said:

蜘蛛纸牌很好获胜的吧……觉得没有怎么输
也许我有50%+的胜率

[Reply]
At 2008.12.28 17:16, CAQ said:

The Complexity of Solitaire那篇文章说的是普通的Klondike纸牌把，就是所谓的“接龙”。看文章说有人提出胜率超过70%
蜘蛛纸牌不知道高级（4花色）的胜率是多少……

[Reply]
At 2011.08.15 09:25, GWeekly[20] = 这周.病了 – 我住包子山 said:

[...] Windows游戏中的NP完全问题要想用机器解决windows游戏还是需要点人品了 [...]

[Reply]

阅微堂