博弈论总结

一.NP局面及其转移

1.公平组合游戏（ICG）

两名选手轮流进行决策；
对于一个局面而言，决策的选择是有局限性的；
对于一个局面而言，决策的局限性仅由当前的局面决定，与其它因素无关；
若当前选手的选择集合为空，则判负；游戏不会一直进行下去。

2.NP局面

N(Next)局面：接下来操作的选手必定获胜的局面（先手必胜）。
P(Previous)局面：上一次操作的玩家必胜（先手必败）。

3.NP状态的转移

若当前进行决策后，达到的所有局面中，存在P局面，则当前局面为N状态（可以故意朝着那个P局面走）；反之，若不存在P状态，则当前状态为P状态（无论怎样都无法走到一个对手必败的状态）。

4.NP转移&数学结论的例子

example 1:
有一堆石子，AB轮流取走，规定每个人每次只能取走1~m个石子。设总共有n颗石子，问先手是否必胜。
首先，可以通过暴力算出前面石子总数为0,1,2,3……的情况，然后找规律即可。
下面是m为3的情况

0	1	2	3	4	5	6	7	8	9	10
P	N	N	N	P	N	N	N	P	N	N

不难发现，当n mod (m+1)同余于0的时候为P状态，其余均为N状态。
example 2:
保留版本1的题目不变，将选取石子的范围变为1,3,4。
同样也可以通过暴力来找到规律。
example 3:
保留版本1的题目不变，将选取石子的范围变为：第一个人第一次选取的范围为1~n-1,之后每一次进行的选取不能够超过前一个人选的石子（小于等于）。
这道题有两种解法。
法一:
定义F[i][j]表示还剩i颗石子时，前一次选了j颗的状态（N/P）。那么可以有以下转移：

for(k=1 to j)
    if(F[i-k][k]==P)
        F[i][j]=N;

然后就是O(n∗n)$O(n\ast n)$的时间复杂度解决。
法二：
O(1)结论：若n为2的整次幂，则先手必败，否则先手必胜。
那么可以分情况讨论：

设n=2^p*q，其中q为正奇数。
当q!=1时
若p=0,则n为奇数，先手就先取1，后手也只能取1，又因为有奇数个石子，最后一个石子必定是先手取走的，于是先手必胜。
若p=1，先手就先取2，就变成了n=2*(q-1)。如果说后手一直取2，那么最后两颗石子一定是先手取走的，先手必胜；如果说后手中途在某一次取走了1颗石子，那么n就变成了一个正奇数，变成了p=0的情况，也是先手必胜。所以说，先手必胜。
若p=2，先手就先取4，就变成了n=2^2*(q-1)。如果说后手一直取4，那么肯定最后4颗石子是先手取走的，先手必胜；如果说后手某一次取走2颗石子，那么就变成了p=1的情况，先手必胜；如果说后手取走了1颗石子，那么又是p=0的情况了，先手必胜。综上，先手必胜。
当q=1时
如果说先手先取走的石子>=2^(p-1),那么后手是可以取走剩下的所有的石子的，那么后手必胜；如果说先手先取走的石子<2^(p-1)，那么后手就变成了q!=1的情况的先手，那么后手必胜。综上，后手必胜。
于是我们就有了结论：
若n为2的整次幂，则先手必败，否则先手必胜。

这样就可以O(1)判断了，用于对付n很大的情况。
example 4:
Fibonacci NIM
保留版本1的题目不变，将选取石子的范围变为：第一个人第一次选取的范围为1~n-1,之后每一次进行的选取不能够超过前一个人选的石子的两倍（小于等于）。
结论：先手胜当且仅当n不是Fibonacci数。换句话说，必败态构成Fibonacci数列。
证明如下（借鉴于ryzjyz大佬的证明）：

首先，我们可以用暴力的方法发现n=2,3,5的时候是显然成立的。
然后我们假设n=f(m)，f(m)代表的是第m个斐波那契数。
那么有f(m)=f(m-1)+f(m-2)
情况一：
先手首先取走了大于等于f(m-2)颗石子，因为2*f(m-2)>f(m-1),所以说后手一定能够在接下来的一次选取内取走所有的石子，那么先手必败。
情况二：
先手首先小于f(m-2)颗石子，那么只要证明后手一定能够选走f(m-1)中的最后一颗和f(m-2)的最后一颗，那么一定是先手必败态。
对于f(m-2)而言，设k等于m-2,那么f(k)=f(k-1)+f(k-2)，那么根据情况一的讨论，选取大于等于f(k-2)颗石子时，后手必胜；否则，就继续递归下去，最后总会达到n=2,3,5的情况，然后就是后手必胜，即先手必败态。那么f(m-2)中的最后一颗石子一定是由后手取走的。
对于f(m-1)而言，证明也是同f(m-2)的，f(m-1)中的最后一颗石子一定是由后手取走的。
于是，就证到了后手一定能够取走f(m-1)和f(m-2)中的最后一颗石子，然后就证到了若n为斐波那契数，那么先手必败。

example 5:
Ferguson游戏
有两个盒子，一个有n个糖果，一个有m个糖果，每一次可以将其中一个盒子清空，将另一个盒子里面的糖果的一部分移过来，保证每个盒子里至少有一个糖果。进行最后一步操作的人胜出。
结论：当n，m其中有一个或两个偶数时，先手必胜；反之，则后手必胜。
证明如下：

利用数学归纳法来证明
当(n,m)=(1,1)时，先手必败；
当max(n,m)>1时：
当max(n,m)=2时：
(n,m)=(1,2)或(2,1)或(2,2)，此时只要先手选完后还剩下一个2，那么先手就可以使它变成(1,1)，就是先手必胜态了。
现在假设max(n,m)小于k的情况满足条件时，那么现在就可以证到max(n,m)=k也是成立的就可以了。
若n,m中存在1个偶数，假设是n,那么就把m清空，把n分成两个奇数a,b,那么由于max(a,b)小于k，所以作为新的先手，后手是必败的，即先手是必胜的。
若n,m均为奇数，那么把m清空，把n分成a（偶）,b（奇），那么由于max(a,b)小于k，所以作为新的先手，后手是必胜的，即先手是必败的。
综上，n,m中至少有一个偶数时，先手必胜。反之，先手必败。

然后就可以O(1)来做了。
example 6:
Chomp!游戏
给定n*m的矩阵，左下角为(1,1)，每一次可以选择一个格子，把这个格子的右上方的所有格子（包含当前行和列），最后取到(1,1)的格子的人输掉。
结论：当只有(1,1)这一个格子是，先手必败；否则先手必胜。
证明：

这里需要运用一个博弈的经典思想。有一些很诡异的博弈题，但其实到最后得到的结论往往是“先手必胜”或“先手必败”。
因为游戏的NP只和当前的局面有关，那么假设当前的n>1或m>1,那么假设先手选了右上角的(n,m)那个格子之后，后手有必胜的策略。那么先手可以直接选择后手选择那个格子，就达到了和后手一样的必胜局面，于是就先手必胜了，与假设相悖。综上，先手必胜（n>1或m>1）

二.经典NIM及其运用

经典NIM(多个游戏的结合)
example 1:
有n堆石子，每次可以在任意一堆石子里选取任意数量的石子，取走最后一颗石子的人胜出。
结论：所有石子堆的数量异或起来，若值为0，则为必败态；否则为必胜态。
证明：

这其实是Bonton定理。
而Bonton定理的证明实际上也是由NP状态的转移推出来的。
我们定义NIM和为当前局面的所有石子堆的石子数量的异或和。令S为NIM和为0的集合，T为NIM和不为0的集合。
当前我们已知的终止局面是一个石子也没有的状态，它的异或和也为0，且是先手必败的。
对于每个T集合中的状态，是可以通过一步转移到S集合中的某个状态的。具体的操作方法是这样的：

首先把每堆的石子的数量的二进制写出来，然后列成竖式加法的形式，进行异或加法（不进位加法）。
01010101$01010101$
10110011$10110011$
10101010$10101010$
然后找到最左边的一列，满足那一列异或起来为1。然后找到那一列（位）上为1的一个数字，将那个数字从那一列开始往右扫，调整到每一列都有偶数个1都状态。最后可以保证这样子的改变是合法的，并且转移到了NIM和为0的状态。比如这样：
00011000$00011000$
10110011$10110011$
10101010$10101010$
然后我们就证到了所有T集合中的状态都可以转移到S集合中的状态。
对于每个在S集合中的状态，只能够转移到T集合中的某个状态，因为不可能使得0异或上一个非零的数之后还是0。
又因为全0的状态是P状态，那么就可以通过NP转移来证到：NIM和为0的状态是先手必败态；反之先手必胜。

example 2:
悲观NIM
与example 1相同，但是规定取走最后一颗石子的人输。
结论：Bonton定理仍然适用。
证明:
当至少还有两堆石子的数量大于2是，先手按找普通的NIM游戏进行。

当至少还有两堆石子的数量大于2是，先手按找普通的NIM游戏进行。
接下来就只有一堆石子的数量大于1了，且此时的NIM和必定为非零的状态。如果先手要胜，1颗石子的堆数是奇数的时候，是先手必胜的。
此时先手如果想要胜出，那么就必须面对NIm和为非零的状态。然后先手可以通过将当前数量超过1的那堆石子取至还剩1或0，使得剩下的数量为1的石子堆的数量为奇数，就可以必胜了。最后，面对这样的状态，先手显然必胜。
综上所述，Bonton定理在这里仍然适用。

example 3:
移动硬币
一个数列，每个格子上都放着一些硬币。每次可以将一个硬币放在它左边的某个格子里。硬币可以重叠。最后不能在进行移动的人输。
我们可以把每一个硬币看成是一堆石子，石子的数量就是当前硬币距离1号格子的距离，然后就是经典NIM游戏了。
example 4:
翻硬币游戏
N枚硬币排成一行。H表示正面朝上，T表示反而朝上。一次操作允许将一枚H翻成T，同时可以将它左边的任一枚硬币翻转（也可以选择不翻转）。当所有硬币都是T时，游戏结束。问：对于初始状态，是否必胜。
结论：将所有的正面朝上的硬币的下标记录下来为a[i]，那么a[i]的异或和非零时，先手必胜；a[i]的异或和为0时，先手必败。
证明：

（以下的“+”指的都是不进位加法，即异或）
根据传统的NIM，先手必须保证当前的NIM和为非零的。令当前的转移是a[i]->a’[i]，那么可以对应到本游戏中。
如果a’[i]=0,那么就是把a[i]位置的’H’变成’T’;如果a’[i]!=0,那么就是把a[i]位置的’H’变成’T’,然后翻转a’[i]的硬币（如果本来是’H’,就相当于tot+=a’[i];如果本来是’T’，就相当于tot-=a’[i]），都是tot^=a’[i]的效果。

这样看来，这就是传统的NIM游戏了。
其实就是这样，只要把当前的游戏转化成了传统的NIM游戏，就可以套结论了，这也是这种题的大多数做法。
example 5:
Northcott游戏(题目就自己上网查一下吧(〃’▽’〃))
结论：将每一行上的棋子的相对距离看成一堆石子，然后就是Bonton定理。
证明：

因为当“石子堆”全空时，先手只能不断退让，然后就输掉了，所以是必败态。
那么就转化为了普通的NIM了（两者的间距如果增大了，那么接下来的那个人就又可以把当前这个人抵死，相当于没有变）。

example 6:
楼梯NIM
把地面标号为楼梯0，只能够把石子移到下一次楼梯上。进行最后一次移动的人获胜。
结论：把奇数编号的楼梯的石子数量全部异或起来，若NIM值为非零，则先手必输；反之先手必胜。
证明：

每一次操作只会是两种情况：
1.从奇数楼梯取出石子放入偶数楼梯
2.从偶数楼梯取出石子放入奇数楼梯
把每一层奇数楼梯看成一堆石子，那么操作1就是把奇数楼梯的那对石子减少；操作2就是把奇数楼梯的石子增加，然而下一次选取时，他的对手可以相应的选取操作1，以抵消他的操作，所以说不需要考虑这种情况。
然后就是普通NIM了。

通过这些题，我们可以发现，就算是可能涉及到某一堆石子数量增加的情况，也可以通过逻辑推理将那种情况排除掉（因为对手总是能够做出相应的决策来抵消效果）
example 7:
Moore’s NIM
同经典NIM，但是每次允许从最多k堆石子中取石子。
结论：将每堆石子转化成二进制形式，然后进行不进位加法（类似于异或，但是是在K+1进制的意义下的），若得到的和为0，则先手必败；反之先手必胜。
证明：

转化成二进制之后，才可以使用Bonton定理。加起来的结果必定是每一位上的数都是小于等于K的。于是就可以从最左边的不为0的那一列开始，设那一列加起来的结果为k’,在那一列上将k’个1变为0.因为k’<=K，所以说转移一定是合法的。然后再像经典的NIM一样，从那一列往后扫，调整每一列的和都为0就可以了。

三.SG函数及其运用

1.SG函数的定义

设x,y都代表是两个局面，x可以转移到y。令所有的x组成的集合为X,那么有：

SG(y)=Mex(SG(x)|x∈X)$$SG(y)=Mex(SG(x)|x\in X)$$

其中，Mex(S)函数是求所有的非负整数中的第一个整数，满足其没有在集合S中出现。
对于终止局面（如取石子游戏中有0颗石子的状态），其SG值为0；
SG值为0的状态为P状态；SG!=0的状态为N状态，并且通常有特殊的含义。.
我们可以把所有可能的转移表示成一张有向无环图：

图中红色节点即为终止状态，u->v表示状态u能够转移到v。
例如取石子游戏（一次只能取三颗），SG值如下：

0	1	2	3	4	5	6	7	8	9	10
0	1	2	3	0	1	2	3	0	1	2

然后SG为0的值为P态，SG!=0的值为N态。

2.游戏的组合

游戏的组合是指由许多的子游戏（已经设定了初始状态）组合而成，且各个子游戏不互相干扰。
合并之后，每个节点所代表的状态代表的是一个杂合体，其中包含了每一个游戏。游戏状态的转移也变成了每一个子游戏的转移的并。
游戏的组合的状态的SG值为各个子游戏的状态的SG值的异或和。
游戏的组合的SG值有2个性质：
设b=g1(x1)⨂g2(x2)⨂g3(x3)......⨂gn(xn)$b=g_1(x_1)⨂g_2(x_2)⨂g_3(x_3)......⨂g_n(x_n)$
(1) 对每个非负整数a(a<b$a<b$)，x都有一个后继结点y，使得g(y) = a
(2)x的后继结点的SG函数值均不可能等于b。这样，根据SG函数的定义可知，g(x)一定等于b
性质1的证明：

假设d=a⨂b$d=a⨂b$。我们假设是x1$x_1$进行了转移得到的g(x′)$g(x^{\prime })$，然后我们有d=g1(x1)⨂g1(x′1)$d=g1(x1)⨂g_1(x_1^{\prime })$。接着有d⨂g1(x1)=g1(x′1)$d⨂g_1(x_1)=g_1(x_1^{\prime })$。设d的二进制形式下有k位，那么d的第k位为1。我们还可以假设g1(x1)的第k位为1，并且我们知道d的第k位也为1，那么有g1(x1)⨂b<g1(x1)$g_1(x_1)⨂b<g_1(x_1)$即g1(x′1)<g1(x1)$g_1(x_1^{\prime })<g_1(x_1)$。那么也就是说可以凑出一个小于g1(x1)的数，那么就可以凑出a来了。

性质2的证明：

使用反证法。假设有一个后继节点满足g(y)=b，那么有：

g1(x′1)⨂g2(x2)⨂g3(x3)......=g1(x1)⨂g2(x2)⨂g3(x3)......$$g_1(x_1^{\prime })⨂g_2(x_2)⨂g_3(x_3)......=g_1(x_1)⨂g_2(x_2)⨂g_3(x_3)......$$

那么可以得到：

g1(x′1)=g1(x1)$$g_1(x_1^{\prime })=g_1(x_1)$$

然而是不可能存在某个子局面的后继的SG值不变的，因为是取Mex，从而证得。

有了游戏的组合的SG定理之后，我们就可以把所有的游戏的组合都看成是经典的NIM游戏。每一堆石子的数量为这个子游戏的SG值。
然后游戏的组合的SG的转移和单个的SG的转移是一样的，也是取Mex。这样就可以进行SG的转移了。

大概就是这样了吧(〃’▽’〃)