棋类游戏的先手优势与概率解释

哈耶克

棋类游戏，包括围棋，象棋，国际象棋，五子棋等等，有个共同特点，那就是事先双方都知道规则，同时每步，双方都完全了解局势，也就是所谓的完全信息。更重要的一点是，局面的形势虽然变化很多，是个天文数字，但依然是有限的。从博弈论上来说，这样的博弈过程可以看作是完全信息的重复博弈。

先看看博弈论中最经典的模型：Nim游戏：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

关于它，有个定理，那就是根据初始状态的不同，要么先手有必胜策略，要么后手有必胜策略。有兴趣的人可以参看wikipedia上面的论述：

http://en.wikipedia.org/wiki/Nim

有下面的定理：

Theorem. In a normal Nim game, the first player has a winning strategy if and only if the nim-sum of the sizes of the heaps is nonzero. Otherwise, the second player has a winning strategy.

很明显，先手是有优势的，因为对于先手来说，只要nim sum不为0就有必胜策略，而nim sum在很多情况下有多种取值可能，取到0的可能性较小。当然后手必胜的情况也是存在的。

先手优势在棋类游戏中广泛存在。中国象棋为了抵消先手优势采用用时的不同，围棋采用贴目，围棋如果在9道小棋盘上下，肯定是先手必胜。五子棋就更不用提了，因为没有禁手的情况下，先手必胜。但这些先手优势只有顶级高手才能体会深刻，一些菜鸟或者业余爱好者往往会怀疑它们的存在性，说些“没有最强的职业，只有最强的玩家”这种废话。还有黑白棋，因为研究它的人数较少，而且电脑的开局是固定套路的，没有发挥先手的变化性等优势，另外游戏到所有格子都下满才决胜负，比较冗长，不像象棋虐菜鸟，二十几步就能将死对手，所以先手优势不明显，。

什么情况下后手必胜或者先手优势不明显呢？一种情况是，先手者其实选择也很少，或者先手虽然看上去开始的选择余地很多，但是基本等效；或者是游戏的步数很长，必须到终局才能结算胜负，不会很快决胜负，这样先手优势不能很快给人留下深刻印象，尤其对于菜鸟。什么情况下，先手优势特别明显呢？那就是决胜负的步数可以很长，也可以很短，这样低手也能体会到先手优势，而不仅仅是高手或者未来的超级电脑才能发现这点。

为什么这么多棋类游戏都会这样呢？我花了一段时间思考这个问题，最后发现可以用概率的思想来解释这个问题，尽管各种棋类多半是个确定性的游戏。有个数学家（忘了叫啥名字，有人能告诉我么）曾说过：“那些最优美的定理都有个特点，它们可以被证明，但很难被理解”，这里的“理解”当然不是指看懂定理，而是指定理指出的现象总让人感受到自然的奇妙，世界的神奇，神秘的联系让人在哲学上陷入困惑。我的后面的解释，其实不是证明，但能帮助我们理解这个现象。

由于双方是轮流下棋的，用图论模型建模下棋过程，各种状态是顶点，可以过渡的局面间用边连接起来。我们把先手移动的边染成白色，后手移动的边染成黑色。其实每个状态之后，如果没和局的话，也没循环局的话，都有必胜或者必败的策略。假定开局时，先手有n种选择，每种选择对应下一个状态，每个状态，先手都可能必胜或者必负，如果先手随机走一步，不好好利用先手的优势的话，那么先手必胜或者必负的概率也就是1/2，但是假定每种状态先手必负的可能性是1/2，那么先手必负的话，需要这n个状态下他都必负，如果认为这些状态是独立的，那么先手必负的可能性只有（1/2）^n，这里需要排除明显会导致自己失败的开局，这种开局后的胜负判断不适用于概率算法，因为它们不够复杂，从而难以表现出伪随机性。如果先手有10种可能的有效开局，那么他必败的可能只有1/1024，然而必败和必胜是互补事件，所以他必胜的概率就是1023/1024，也就是接近99.9%的可能必胜


这种概率论思想来思考问题，当然不够严谨，但却往往很有启发性，在数论中，很多猜想的提出都是用概率性的思想来猜一个结论。比如说孪生质数的分布，著名的哈代-李特尔伍德第一猜想给出其渐进表达式，大部分人相信表达式是对的，而且数据验证也支持。这个表达式的提出就是假定形如ak+b与ak+b+2分别为质数这个“概率事件”是独立的，从而利用独立事件同时发生的概率公式来进行推导

动力系统在演变时，表现出一种伪随机性，所以在确定性的系统里，用概率方法往往有时候依然有效

哈耶克

后来思考了一下这个问题，发现需要修正原先的模型，但结论依然成立

假定先手走到任意一步，然后自己必负的概率是p,因此如果先手有n种开局选择，假定相互独立，为了先手必负，必须这n个开局都必败，也就是先手必负的概率是p^n,但是走了一步后就轮到后手了，后手此时处于“先手”地位，假定先手随机走了一步，那么此时后手面对的局面就类似于先手一开始的局面了，假定此时后手的胜率等于先手一开始的胜率，那么我们就得到方程：p=1-p^n

当n=10时，解这个一元十次方程，得到近似解p=0.835,从而我们知道先手必胜的概率是83.5%，这比我上面得到的99.9%的必胜率是低了很多，但依然是相当的高，依然拥有先手优势。

我不是马甲

LZ.你的模型反正我没看懂，程序看懂看不懂就不知道!

更重要的一点是，局面的形势虽然变化很多，是个天文数字，但依然是有限的。

请LZ解释下，“局面的形势虽然变化很多，是个天文数字，但依然是有限的”这个论断是怎么得到的？！

zpbyeah

- -棋牌类游戏。。。
单机？？
单机的话基本还是靠设计好AI难度的吧。
网游的话因为是人人对战，你搞好规则就行。。。

哈耶克

我不是马甲: Re:棋类游戏的先手优势与概率解释

LZ.你的模型反正我没看懂，程序看懂看不懂就不知道!

更重要的一点是，局面的形势虽然变化很多，是个天文数字，但依然是有限的。

请LZ解释下，“局面的形势虽然变化很多，是个天文数字，但依然是有限的”这个论断是怎么得到的？！

就以变化最为复杂的围棋为例，如果19×19的棋面上有n个黑子，那么变化最多就是C(361,n),考虑棋盘的对称性，其实数字远小于此数，对n从0到361求和，就得到棋面的最多变化种类，也是个有限数。下棋的过程就是从一个局面转向另一个局面，可以用图论中的有向图来表示所以可行的转化方向，就得到一个有限图。

Mr_I

不知道提子或劫变算不算在C(361,n)里。

哈耶克

提子或劫变属于“可行的转化方向”范畴，并不影响“变化最多就是C(361,n)”这个判断，而且围棋还禁止全局同形再现。所以变化必然在有限时间里结束

不过我最近用离散动力系统分析了下我后面的模型，发现这个动力系统的平衡解（p+p^n=1的解）是不稳定的，这让人很郁闷

instemast

这年头像LZ这样的网友和这样的帖子不多见。顶

bilu51

很有意思