编程之美 - NIM“拈”游戏分析

NIM“拈”游戏分析

问题

有N块石头和两个玩家A和B，玩家A先将石头分成若干堆，然后按照BABA……的顺序不断轮流取石头，能将剩下的石头一次取光的玩家获胜。每次取石头时，每个玩家只能从若干堆石头中任选一堆，取这一堆石头中任意数目（大于1）个石头。

请问：玩家A有必胜策略吗？要怎么分配和取石头才能保证自己有把握取胜？

解法与分析

据说，该游戏起源于中国，英文名字叫做“NIM”，是由广东话“拈”（取物之意）音译而来，经由当年到美洲打工的华人流传出去，这个游戏一个常见的变种是将十二枚硬币分三列排成 [3，4，5] 再开始玩 。我们这里讨论的是一般意义上的“拈”游戏。

言归正传，在面试者咄咄逼人的目光下，你要如何着手解决这个问题？

在面试中，面试者考察的重点不是“what”——能否记住某道题目的解法，某件历史事件发生的确切年代，C++语言中关于类的继承的某个规则的分支等。面试者很想知道的是“how”——应聘者是如何思考和学习的。

所以，应聘者得展现自己的思路。解答这类问题应从最基本的特例开始分析。我们用N表示石头的堆数，M表示总的石头数目。

当N=1时，即只有一堆石头——显然无论你放多少石头，你的对手都能一次全拿光，你不能这样摆。

当N=2时，即有两堆石头，最简单的情况是每堆石头中各有一个石子（1，1）——先让对手拿，无论怎样你都可以获胜。我们把这种在双方理性走法下，你一定能够赢的局面叫作安全局面。

当N = 2，M > 2时，既然（1, 1）是安全局面，那么（1, X）都不是安全局面，因为对手只要经过一次转换，就能把（1, X）变成（1, 1），然后该你走，你就输了。既然（1, X）不安全，那么（2, 2）如何？经过分析，（2，2）是安全的，因为它不能一步变成（1，1）这样的安全局面。这样我们似乎可以推理（3, 3）、（4, 4），一直到（X, X）都是安全局面。

于是我们初步总结，如果石头的数目是偶数，就把它们分为两堆，每堆有同样多的数目。这样无论对手如何取，你只要保证你取之后是安全局面（X, X），你就能赢。

好，如果石头数目是奇数个呢？

当M=3的时候，有两种情况，（2, 1）、（1, 1, 1），这两种情况都会是先拿者赢。

当M=5的时候，和M=3类似。无论你怎么摆，都会是先拿者赢。

若M=7呢？情况多起来了，头有些晕了，好像也是先拿者赢。

我们在这里得到一个很重要的阶段性结论：

当摆放方法为（1, 1,…, 1）的时候，如果1的个数是奇数个，则先拿者赢；如果1的个数是偶数个，则先拿者必输。

当摆放方法为（1, 1,…, 1, X）（多个1，加上一个大于1的X）的时候，先拿者必赢。因为：

如果1有奇数个，先拿者可以从（X）这一堆中一次拿走X-1个，剩下偶数个1——接下来动手的人必输。

如果有偶数个1，加上一个X，先拿者可以一次把X都拿光，剩下偶数个1——接下来动手的人也必输。

当然，游戏是两 个人玩的，还有其他的各种摆法，例如当M = 9的时候，我们可以摆为（2, 3, 4）、（1, 4, 4）、（1, 2, 6），等等，这么多堆石头，它们既互相独立，又互相牵制，那如何分析得出致胜策略呢？关键是找到在这一系列变化过程中有没有一个特性始终决定着输赢。这个 时候，就得考验一下真功夫了，我们要想想大学一年级数理逻辑课上学的异或（XOR）运算。异或运算规则如下：

XOR（0, 0）= 0

XOR（1, 0）= 1

XOR（1, 1）= 0

首先我们看整个游戏过程，我们从N堆石头（M₁, M₂, …, M_n）开始，双方斗智斗勇，石头一直递减到全部为零（0, 0,…, 0）。

当M为偶数的时候，我们的取胜策略是把M分成相同的两份，这样就能取胜。

开始：（M₁, M₁） 它们异或的结果是XOR（M₁, M₁）= 0

中途：（M₁, M₂） 对手无论怎样从这堆石头中取，XOR（M₁, M₂）!= 0

我方：（M₂, M₂） 我方还是把两堆变相等。XOR（M₂, M₂）= 0

…

最后：（M₂, M₂） 我方取胜

类似的，若M为奇数，我们把石头分成（1, 1, …,1）奇数堆的时候，XOR（1, 1,…,1）_[奇数个] !=0。而这时候，对方可以取走一整堆，XOR（1, 1,…, 1）_[偶数个]=0，如此下去，我方必输。

我们推广到M为奇数，但是每堆石头的数目不限于1的情况，看看XOR值的规律：

开始：（M₁, M₂, …, M_n） XOR（M₁, M₂, … M_n）=？

中途：（M₁’, M₂’, … M_n’） XOR（M₁’, M₂’, … M_n’）=？

最后：（0, 0, …, 0） XOR（0，0，… 0）=0

不幸的是，可以看出，当有奇数个石头时，无论你如何分堆，XOR（M₁, M₂, … M_n） 总是不等于0！因为必然会有奇数堆有奇数个石头（二进制表示最低位为1），异或的结果最低位肯定为1。 [结论1]

再不幸的是，还可以证明，当XOR（M₁, M₂, … M_n）!= 0时，我们总是只需要改变一个M_i的值，就可以让XOR（M₁, M₂, …M_i’，… M_n）= 0。 [结论2]

更不幸的是，又可以证明，当XOR（M₁, M₂, … M_n）= 0时，对任何一个M值的改变（取走石头），都会让XOR（M₁, M₂, …M_i’，… M_n）! = 0。 [结论3]

有了这三个“不幸”的结论，我们不得不承认，当M为奇数时，无论怎样分堆，总是先动手的人赢。

还不信？那我们试试看：当M=9，随机分堆为（1，2，6）

开始：（1，2，6）

1=0 0 1
2=0 1 0
6=1 1 0
XOR=1 0 1 即XOR（1，2，6）!=0

B先手：（1, 2, 3），即从第三堆取走三个，得到（1，2，3）

1=0 0 1
2=0 1 0
3=0 1 1
XOR=0 0 0 所以，XOR（1，2，3）=0

A方：（1, 2, 2）XOR（1, 2, 2）!=0。

B方：（0, 2, 2）XOR （0, 2, 2）=0

……A方继续顽抗……

B方最后：（0, 0, 0），XOR（0, 0, 0）= 0

好了，通过以上的分析，我们不但知道了这类问题的答案，还知道了游戏的规律，以及如何才能赢。XOR，这个我们很早就学过的运算，在这里帮了大忙。我们应该对XOR说Orz才对！

有兴趣的读者可以写一个程序，返回当输入为（M₁, M₂, …, M_n）的时候，到底如何取石头，才能有赢的可能。比如，当输入为（3, 4, 5）的时候，程序返回（1, 4, 5）——这样就转败为胜了！

扩展问题

8. 1．如果规定相反，取光所有石头的人输，又该如何控制局面？

9. 2．如果每次可以挑选任意K堆，并从中任意取石头，又该如何找到必胜策略呢？

---

---

[JZ1]是参加微软的面试，还是其他公司的面试，请指明。

[JZ2]能不能注明是哪个出版社哪年出版的，相信有心的读者会去找来看，我也想看看：）

[JZ3]咱们先别自己下结论为好，读者能不能受益，还得读者说了算，呵呵。