组合博弈中最经典的尼姆（Nim）游戏，怎么玩才能必胜？

作者：大神团·冯伟

作者介绍：冯伟，新东方超尖生计划授课老师，清华硕士。全国初中数学、物理、化学三项竞赛一等奖，中国西部数学奥林匹克银牌，北京市大学生数学竞赛一等奖，全国大学生物理竞赛一等奖，清华大学优秀硕士毕业生。

有这样一个游戏，估计大家小时候都曾玩过：

这个游戏的名字，叫尼姆（Nim）游戏。

这是一个十分古老的游戏，十六世纪初在欧洲已有关于此游戏的记载，游戏起源已不可考 (有说起源于中国民间)。规则很简单，不过想赢却并不容易。1940年纽约世界博览会上曾经展出过一台尼姆机，这称得上是世界上第一台电子游戏机，游客可以同机器一较高下，然而胜者却寥寥无几。

下面我们就来研究这个游戏。

如此“跟随策略”可以保证后手总能拿走最后一颗石子而取胜，我们称这种先手必败的局面为必败局。所有石子都取光的局面称为零局。零局时无子可取而必败，故也是必败局。

如果两堆石子数量不一样，则先手可以通过在数量多的那堆取子使两堆数量一样，继而在后手取子后采取“跟随策略”保证胜利，故两堆石子数量不一样的开局为必胜局。

从上表我们发现似乎大部分第三堆石子数是前两堆石子数之和。

于是，我们可以建立一个如下的一个映射表，横行和竖行的表头分别代表其中两堆石子的数量，它们交叉的地方则是使之成为必败局的第三堆的石子数。

我们现在换个角度思考一下。

我们认为这种“平衡”的开局优势互相抵消。

有了局势比较这种思想之后，我们不妨参照物理中对势能的处理，规定一个势能零点作为基准，很容易想到我们可以令零局[0]的局势值为0，而局面[1]比零局[]0有一个子的优势，于是[1]的局势值为1。

也就是说对于局势值不同的两个游戏局，先手可以每次从局势值高的石子堆中取石子，把它的局势值降至和另一个游戏局的局势相同，使二者局势达到平衡，而后手拿子后会破坏这种平衡，由于最终的零局可以看做[0]+[0]的平衡状态，因此对于局势值不同的两个游戏局总是必胜局。

反之对于局势值相同的两个游戏局，先手总会破坏这种平衡，而后手会使之恢复到平衡状态，因而这种局面为必败局。

我们将这种思想扩展到n=3来试试。

到底是不是这样呢？我们来验证一下。

既然对于一个含两堆石子的游戏局，我们可以找到一个局势值相同的只含一堆石子的游戏局与之平衡，而每种局面中任意两堆石子是相互独立的（因为一次只能从其中一堆取石子），这样我们就可以把两堆石子用一堆“等价”的石子替换掉而不影响游戏结果！

有了“等价代换”这一思想利器，再结合上表，我们惊喜的发现现在已经可以处理堆数n比较大的尼姆游戏了。

因为我们不断的进行这种等价代换，就能将堆数最终减少到1，而对于堆数为1的游戏局面，只有零局是必败局，其他任何局势值大于0的局面都是必胜局。

无论如何拆分，我们都得到了相同的结果，这也说明了我们“等价代换”的正确性。

“等价代换”不仅可以正着用，还可以反着用，也就是说我们可以把一堆石子用两堆甚至多堆石子替换掉。这可以帮助我们考察映射关系。

同学们可能看出来了，这实际上就是利用数的二进制表示，并消去相同位数上的数字。这种运算操作叫异或运算。

当然仅判断出输赢是不够的，我们得要还原出能够获胜的具体策略才行。那游戏中应该怎么玩呢？

我们只需看哪一堆和12异或操作之后比原堆石子数小即可，而这是总能办到的 （原因可见下节）。

如此往复，由于石子数总是减少的，最终一定停止在局势值为0的零局，而这一平衡状态只能由先手完成，于是最终能取得胜利。

对于局势值为0的必败局，则要么让对方先走，要么只能企盼对手犯错，之后用同样的方法来战胜对方了。

到这里我们基本可以完胜没有经验的对手了。

不过用到的方法没有进行严密的证明，学霸们一定不会止步于此，为了满足各位的需求，下面我们把理论和相关的证明写出来，给读者们参考。

理论与证明

尼姆游戏的完整策略是1901年由Charles L. Bouton首次阐述的。值得一提的是 Nim 这个名字也是由他给出的。

下面给出破解 Nim 游戏奥秘的 Bouton 定理 (Bouton's Theorem)：

证毕。

尼姆游戏，是组合博弈理论中的最基本的也是最重要的一个模型，他属于无偏博弈（Impartial Games）。

限于篇幅今天就讲到这里，在后续的文章中我会继续给同学们介绍组合博弈中的小游戏和相关理论。

你学会了吗？快去找小伙伴们PK吧！

作者介绍：冯伟，新东方超尖生计划授课老师，清华硕士。全国初中数学、物理、化学三项竞赛一等奖，中国西部数学奥林匹克银牌，北京市大学生数学竞赛一等奖，全国大学生物理竞赛一等奖，清华大学优秀硕士毕业生。新东方智慧学堂（zhihuixuetang_xdf），与精英为伍，成就未来精英。