《无聊之余玩下纸牌，发现有的死局，于是百度乎。》
2014-11-21 17:02阅读：
是否每局Windows纸牌游戏（Solitaire）都是可以被解决的？也就是说每局都可以赢。一直以来我都以为Windows纸牌是每局都能赢的，即便一局失败，重新开始该局游戏换一种路线（叠牌顺序）还是能赢的。可是今天遇到了一盘死局，无论我怎么改换路线，都无法胜利，找另一个同学来玩还是如此（当然，可能大家游戏的思路都一样也说不定）。
So...问题出现了：究竟是不是每一局纸牌游戏都可以被解决？
如果是，那么游戏系统发牌时是如何做决策的，也就是说它背后所依赖的算法是什么，或者说和哪种算法模式更为匹配？如果不能，即便纸牌能赢局数的概率是99.9%，总还是有无法解决的残局，那么这是否就意味着该算法是不完备的，甚至可以说该游戏是有BUG的？
好问题！
首先，每局可以赢这个肯定不是。这个构造一个简单的例子就可以：
1. 翻牌区从左到右是J, J, J, J, K, K, K；
2. 发牌区，无论是三张还是一张发牌方式，都不出现Q和A（被压在翻牌区或者发牌区里）；
这局面一上来就是死局。
事实上，solitaire的局面判定是个相当有难度的问题。有人已经证明了，给定一个初始局面，判断是否有解是NP-Complete：http://www.springerlink.com/content/b40703p37h74j220/
。也就是说，这个小游戏是肯定没足够的时间来对每一个随机生成的初始局面判断是否有解，从而总是给你一个有解的局面。要不然，很可能你一点new
game，就卡得你不想玩了。。
至于windows的发牌算法实
现，我想有两个要点。第一是开局尽量是一个活局。但是这个上面说了，由于是npc问题，肯定不能完全保证。但是可以有heuristics。比如，刚开始的牌面可以移动出现翻牌的机会；发牌区出现A；翻牌区里的牌尽量按顺序排列。第二，电脑还可以随时作弊帮你化解困难。比如，它可以不定时的evaluate一下当前局面是不是再翻几张牌就死了。只搜索几步，这个电脑还是不需要花很多时间，造成卡顿的。如果是，那就在你下一次获得翻牌/发牌机会时，给你一张想要的牌，帮助游戏进行下去。
基于以上分析，可以知道，出现无解局面这个不是游戏bug，而是游戏本身太难。
（via~人人）
