简单博弈论和SG定理

        博弈论是ACM和数学竞赛中的重要一项，它考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

Nim游戏

        先来看这样一个经典问题（Nim游戏）：

        给定若干堆石子，你和队手轮流选取任意一堆石子，拿走其中的若干颗（没有上界，不能不拿）。首先拿走所有石子的人获胜（也就是面临所有石子都被拿走局面的人判负）。

        在这种游戏规则下，给定每一堆石子的数量，如何判断先手有没有必胜的可能？这里直接给出定理：

【Bouton定理】Nim游戏中，先手必败等价于$A_1 xor A_2 xor … xor A_n=0$

        这里的$A_i$为第i堆石子的数量，xor表示按位求和并模2取余，也就是异或，对应C语言中的^。这种操作也称Nim和。

P/N点

        Nim游戏拥有很简洁的结论，下面的SG函数以及SG定理则将其推广到更一般化的问题上。要了解SG函数，需要理解以下两个概念。

• $P-position(P点)：$ 必败点。在P点时，无论如何操作，只要队手不失误，必败。
• $N-position(N点)：$ 必胜点。在N点时，无论对手如何操作，只要自己不失误，必胜。

        P/N点有以下性质：

• 当游戏到达没有任何合法操作的局面时（比如Nim游戏中的石子全部被取走时），面临该局面的一方判负，也就是P点。
• P点的后继一定是N点。
• N点的后继中至少有一个P点。

        接下来是公平组合游戏(ICG)的概念，它是满足以下几点条件的游戏：

1. 有且仅有两人参与。
2. 游戏局面的状态集合有限。
3. 对于同一个局面，两个游戏者的可操作集合完全相同。
4. 游戏者轮流进行游戏。
5. 当无任何合法操作时游戏结束，面临者判负。
6. 无论游戏如何进行，总可以在有限步数之内结束。

        由此来看Nim游戏是ICG，象棋不是ICG（因为双方只能操作自己的棋子，不满足第3条）。这里只探讨ICG。
        对于一个ICG，可以将其抽象为一个有向无环图，图的节点是游戏的一个局面，有向边表示局面通过合法操作进行的转化。显然没有出度的节点必然代表着游戏的结束。ICG的进行可以看作是在图上移动棋子的过程：起初棋子在最初局面上，然后双方轮流将棋子沿有向边移动到下一个节点，直到有一方无法移动时判负。
        对于每一个节点，都可以判定它是P点还是N点，如果可以找到处态的P/N性质，那么判定先手能否获胜的问题就得到解读。终点显然是P点，下面来探讨其余点的P/N性质。根据P点和N点的定义有以下结论：

• 如果一个节点的后继均为N点，则该点为P点。
• 如果一个节点的后继存在P点，则该点为N点。

SG定理

        通过这种递推关系，可以得到初态的P/N性质。在博弈论中，SG函数用来描述一个局面的P/N性质，要理解SG函数需要先引入mex(minimal excludant)运算。设$N$为自然数集合，对于任何$S\subseteq N$，定义：

$$mexS=\min\{x|x\in N,x\notin S\}$$

        也就是说，mexS表示不在S中的最小自然数。我们用mex运算来定义SG函数，定义如下：

$$SG(x)=mex\{SG(p_1),SG(p_2),...,SG(p_m)\}$$

        这里的$p_i$是x的m个后继。特别地，当x没有后继时（也就是终点），其SG值为$mex\varnothing$，即为0。这样易知一个局面为P点等价于其SG值非0。简单归纳证明如下：
        首先所有终点都为P点，SG值为0，成立。
        如若后继中存在P点，则取mex后值一定大于0，该点即为N点；若后继中不存在P点，则取mex后值一定为0，该点即为P点。这与P点N点定义及性质一致。
        SG函数是解决ICG问题的利器。但是既然可以直接递推求出P/N性质，为何还要引入SG函数呢？这是因为SG函数有一个强大的定理——SG（Sprague-Grundy）定理。
        引入SG定理前，先来认识游戏和的概念。
        一个游戏可能是由多个子游戏组成的（将其记作$G_1,G_2…G_n$），如果整个游戏进行时，玩家可以任意选取一个子游戏进行上面的合法操作，所有子游戏均无法进行合法操作时判负。这时的整个游戏称为子游戏的游戏和，记作$G=G_1+G_2+…+G_n$。于是有SG定理：

【SG定理】游戏和的SG值为所有子游戏SG值的Nim和。

        这样可以将一个游戏分成若干子游戏，从而分而治之，求出SG值。从这里可以发现Bouton定理与SG定理的内在联系。
        Nim游戏其实就是由若干子游戏组成的，每个子游戏都是如下的形式：给一堆石子，从中拿走至少一个石子，先全部拿走者胜。这个子问题很无聊，因为只要一开始石子数非零，则先手必胜（直接全部拿走即可）。但是可以从另一个角度去理解这个问题。注意到当前石子数是局面的唯一描述变量，设其为x。我们证明SG(x)=x，证明如下：
        采用归纳证明。显然SG(0)=0；假设x≤k时均成立，由于可以从k+1个石子中任意拿石子，故0~k都是k+1这个局面的后继，所以：

$$SG(k+1)=mex\{SG(k),SG(k-1),...,SG(0)\}=mex\{k,k-1,...,0\}=k+1$$

        即对x=k+1也成立，故SG(x)=x是正确的。这样根据SG定理，游戏和（即Nim游戏）的SG值为：

$$SG=SG(A_1)\ xor\ SG(A_2)\ xor\ ...\ xor\ SG(A_n)=A_1\ xor\ A_2\ xor\ ...\ xor\ A_n$$

        这个值为0时，说明游戏初态局面为P点，先手必败，于是证明了Bouton定理。可以发现Bouton定理是SG定理在Nim问题上的直接应用。

例题

        SG函数以及SG定理是解决组合游戏问题的利器，下面举几个例子。

        Mr.Jia和Boy next door在玩一个游戏。一开始有一个正整数x，可以进行对其进行两种操作：x/2(向下取整)和x-1。现在Mr.Jia和Boy next door轮流进行任意一种操作，先得到0的一方胜利。现在若Mr.Jia先进行操作，给定初始的数x，判断Mr.Jia能否获胜。

        不要吐槽Boy next door。这是TJU某次编程竞赛的第四题，用SG函数可以轻松做出。注意到SG值非零的时候表示必胜，它的具体值并没有意义，不妨将其统一为1，这样可以简化算法。

int SG(int x) {
    if (x == 0)return 0;
    int a = SG(x / 2), b = SG(x - 1);
    if (a != 0 && b != 0)return 0;//后继无0说明x为P点
    return 1;//后继有0说明x为N点
}

        用上面代码求出SG值即可，需要用递推或记忆化优化，这里只点明思路。
        其实在做这题时，发现如果把x写成k2^s（k为奇数），则s为偶数则Mr.Jia赢，否则Boy next door赢。这是一个靠眼力得出的结论，实际上也是正确的，现在来用SG函数来证明这个结论。这里的SG函数可以看成是一个bool类型的函数，有递推式：

$$SG(x)=\begin{cases}false\ & x=0\\ !SG(x/2)||!SG(x-1)\ & x>0 \end{cases}$$

        发现x=1时SG(1)为true，表示Mr.Jia赢，1对应的s为0，0是偶数，这是正确的。假设x≤p时都正确，下证x=p+1也正确。
        若x为偶数且x=k2^s（k为奇数且s>0）。注意到x-1一定是奇数，根据归纳假设SG(x-1)=true。x/2必然为k2^s-1，若s为偶数，则s-1为奇数，由归纳假设SG(x/2)=false，则SG(x)=true，成立；若s为奇数，则s-1为偶数，由归纳假设SG(x/2)=true，则SG(x)=false，同样成立。
        若x为奇数（只考虑大于1的情况），设x=k2^s+1，这里k为奇数。若s为偶数，则由归纳假设SG(x-1)=true，SG(x/2)=SG(k2^s-1)=false，那么SG(x)=true，成立；若s为奇数，则由归纳假设SG(x-1)=false，SG(x)必然为true，也成立。
        综上所述，结论是正确的，也就是说可以用给定数中2因子的个数来判定答案，这样对于一个数n，就可以在O(logn)复杂度下判断。
        另一题（洛谷P1290）：

        欧几里德的两个后代Stan和Ollie正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N，从Stan开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于>0。然后是Ollie，对刚才得到的数，和M，N中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。下面是他们用(25，7)两个数游戏的过程：
Start：25 7
Stan：11 7
Ollie：4 7
Stan：4 3
Ollie：1 3
Stan：1 0
Stan赢得了游戏的胜利。
现在，假设他们完美地操作，谁会取得胜利呢？

        这仍然是一个ICG，可以考虑SG函数，发现有如下的递推式（假设n≥m）：

$$SG(n,m)=mex\{SG(n-m,m),SG(n-2m,m),...,SG(n\%m,m)\}$$

        递推式通俗易懂，但它并不利于实际操作，这时适当的观察是有益的。发现：

$$SG(n-m,m)=mex\{SG(n-2m,m),...,SG(n\%m,m)\}$$

        这个式子说明只要知道SG(n%m，m)，就可以递推求出上面式子中的所有值。若SG(n%m，m)=0，则SG(n%m+m，m)=1，SG(n%m+2m，m)=2…之后的值均非零。若SG(n%m，m)=1，则SG(n%m+m，m)=0，之后的值均非零，于是得出一个重要结论：当SG(n%m，m)=0时，SG(n，m)必非零；当SG(n%m，m)=1时，若n/m>1则SG(n，m)非零，若n/m=1则SG(n，m)=0。
        与上一题思想相似，非零全部按1处理，于是有：

int getSG(int x, int y) {
    if (x < y)swap(x, y);
    if (y == 0)return 0;
    if (x / y == 1 && getSG(y, x % y) == 1)return 0;
    return 1;
}

        求出SG值判断即可。
        第三题，洛谷P2148，山东2009年省选题：

        小E 与小W 进行一项名为“E&D”游戏。

        游戏的规则如下： 桌子上有2n 堆石子，编号为1..2n。其中，为了方便起见，将第2k-1 堆与第2k 堆 （1 ≤ k ≤ n）视为同一组。第i堆的石子个数用一个正整数Si表示。 一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆 石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子 数必须保证大于0。显然，被分割的一堆的石子数至少要为2。 两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为1，则此时 没有石子可以操作，判此人输掉比赛。

        小E 进行第一次分割。他想知道，是否存在某种策 略使得他一定能战胜小W。因此，他求助于小F，也就是你，请你告诉他是否存在必胜策略。 例如，假设初始时桌子上有4 堆石子，数量分别为1,2,3,1。小E可以选择移走第1堆， 然后将第2堆分割（只能分出1 个石子）。接下来，小W 只能选择移走第4 堆，然后将第3 堆分割为1 和2。最后轮到小E，他只能移走后两堆中数量为1 的一堆，将另一堆分割为1 和1。这样，轮到小W 时，所有堆的数量均为1，则他输掉了比赛。故小E 存在必胜策略。

        这是一个游戏和，子游戏是从两堆石子中任取一堆分割。对于石子堆数为x，y的一个组合，可以用SG(x，y)表示这个子游戏的SG值。x与y均为1时SG值为0，当两者均非1时，显然有两种总的策略：分x和分y。发现分割操作只与一个数有关而与另一个数无关，不妨只探讨一个数p的分割情况，并观察其SG值的规律。
        算出1~10的SG值（实质上是SG(1，1)~SG(1，10)，自行理解）并写出mex后继集合：用二进制数表示，0表示不存在，1表示存在，那么有：

1：0000000
2：0000001
3：0000010
4：0000011
5：0000100
6：0000101
7：0000110
8：0000111
9：0001000
10：0001001

        惊奇地发现，x对应的mex后继集合居然就是x-1的二进制表示！那么SG(n，m)就是(n-1)|(m-1)的二进制表示中第一个0出现的位置！那么getSG函数可以轻松写出：

int getSG(int a, int b) {
    int ans = (a - 1) | (b - 1), r = 0;
    while ((ans & 1) == 1)ans >>= 1, r++;
    return r;
}

        那游戏和的SG值如何求呢？整个游戏有2n堆石子，是由n个子游戏组成的。根据SG定理，将这n组的SG值一一求出，取Nim和就可以得到游戏和的SG值，于是问题迎刃而解。
        从这里可以看出，找SG函数的规律是一个很实用的技巧，可以先找到SG函数的规律再用这个规律快速求SG值，从而解出原题。

常见博弈类型

        上文已经提到Nim游戏，下面是另外三种博弈类型。

巴什博弈

        给定一堆$n$个物品，两个人轮流取，每一次至少取1个，最多取$m$个，最后取光者获胜。
        易知$n=m+1$时，必败。当$n\%(m+1)=0$时，后手总是能用合理的策略使得先手进入$n=m+1$的状态，因此当$n\%(m+1)=0$时，先手必败。
        另外，若规定最后取光的人输，则$(n-1)\%(m+1)=0$时先手败。

威佐夫博弈

        有两堆若干个物品，两个人轮流取物，每一次能从某一堆或者总两堆中取同样数量的物品，至少取一个，最多不限数量，最后取光者胜。
        这里直接说结论了，当两个堆数量满足以下条件时：

$$x=\lfloor \frac {(1+\sqrt 5)k}{2}\rfloor\\ y=x+k$$

        k取自然数。这样时先手必败。

斐波那契博弈

        有一堆物品，数量为$n$，两个人依次取物，每一次取的物品数量满足下面条件：

• 先手不能一次性取完所有物品。
• 之后取的物品数量介于1和对手刚取的数量两倍之间（含端点）。

        取光者胜。
        解决思路：当$n$为斐波那契数时，先手必败。