描述 Description

三堆数量随机的石头，两个人轮流从其中一堆中拿走任意数量的石头，拿走最后一块的人输，必胜法是什么？

分析 Analysis

简单分析

用（a，b，c）表示某种局势，首先（0，0，0）显然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，接下来都可以变为（0，n，n）的情形。

异或分析

anti 问题：三堆数量随机的石头，两个人轮流从其中一堆中拿走任意数量的石头，拿走最后一块者胜

这个 anti 问题的解决方案就是大名鼎鼎的 “异或大法”。

简单地说，就是将三堆石头的块数化为二进制，再进行 “异或运算”（），然后，先手一方只要保持三个数进行“异或”后结果是 0 就可以获胜，而对于三个数初始异或结果为 0 的情况，则是后手获胜 。

比如，初始时，石头数三堆的石头数是 2、3、5，而，，，而，在十进制下，这个数是 4，所以先手只要从 5 块石头中取走 4 块即可获胜。由于当所有的数的异或值等于零时，二进制的每一位都出现偶数次，所以必然可以办到。

再如，初始时，石头数三堆的石头数是 3、4、7，而，，，而，所以，这是后手方必胜的情况。
[三堆数量随机的石头-知乎]

定理分析

易证三个定理:

1.游戏结束时，所有的数都是0，异或结果为0

2.任何一个“异或结果为0的局面”，经过一次操作，必然异或结果不是0。

3.任何一个“异或结果[不]为0的局面”，经过一次操作必然可以让它变为0。(非常重要！)

所以可以得出结论:按位异或后结果为0的局面，是一种“必负局”。因为你任何操作都会把他变为“非必负局”，而对手必然可以有一种方法把它变为“必负局”。游戏结束时的局面属于“必负局”，游戏必然会在有限步内结束。所以必胜策略很简单，每次操作使得局面按位异或结果为0。如果你遇到的局面结果是0，那么认输就行了。

奇异局势的判定

对于一个普通的局势，如何判断其是不是奇异局势？对于一个局势\(s1,s2,...sk\)，对所有石子个数做位的异或运算，s1^s2^s3^...^sk，如果结果为0，那么局势\(s1,s2,...sk\)就是奇异局势（平衡），否则就不是（非平衡）。从二进制位的角度上说，奇异局势时，每一个bit位上1的个数都是偶数。

玩家的策略

就是把面对的非奇异局势变为奇异局势留给对方。也就是从某一堆取出若干石子之后，使得每一个bit位上1的个数都变为偶数，这样的取法一般不只有一种。可以将其中一堆的石子数变为其他堆石子数的位异或运算的值（如果这个值比原来的石子数小的话）。

先手必胜当且仅当:

(1)所有堆的石子数都为1且游戏的SG值(即各堆石子数的异或和)为0。

(2)至少有一堆的石子数大于1且游戏的SG值不为零。

即：获胜情况对先取者的讨论

异或结果为0，先取者必败，无获胜方法。后取者获胜；

结果不为0，先取者有获胜的取法。

[贾志豪《组合游戏略述——浅谈SG游戏的若干拓展及变形》]

[winning ways for your mathematical plays]

sg函数

sg函数为以下形式：SG(x)=mex(S)

S表示x的所有后继状态，mex表示不在集合里最小的非负整数

必败态的sg值为0，然后还要结合sg定理：游戏和的SG函数等于各个子游戏SG函数的Nim和。于是就可以把各个子游戏分而治之。

举个例子

假设我们用sg函数处理上述所说的例二，我们就可以把游戏分为两个单堆Nim子游戏。对于单堆的Nim游戏，如果我们可以取任意正整数多个，那么很容易就可以明，sg(x)=x。那么我们整个游戏的必败态则为sg1(x)∧sg2(x)=0显然只有当a=b时游戏为必败态，和我们的讨论结果一致。

关于sg定理的证明

对于必胜状态，一定存在后继的必败态

我们假设现在的Nim和为X，现在的最大的一堆的数量为Y，那么我们只需要把这最大的一堆取成Z=X∧Y即可。因为除了最大的这堆外其他的Nim和为X∧Y，因此我们取完后，现在的Nim和即为sg′(X)=X∧Y∧(X∧Y)=0，显然为必败态了。而且我们也可以保证Z≤Y，即我们总有办法实现它。对于必败态，它的所有后继状态都是必胜的。由于只能更改一堆的状态，无论哪一位的1被改变，那么原来那位上1的奇偶个数一定会改变，所以就会变为必胜态。

[博弈问题入门]

代码 Code