博弈论之NIM取石子游戏与SG函数[信息学资料]

首先，让我们来看一看最简单的取石子游戏。

游戏1
规则：
有x个石子，两人轮流取，最多取y个，不能不取，没得取的人输，两个人都按照最优策略进行游戏，问先手必胜的充要条件。

答案：
x mod (y+1) != 0

恩，刚才那个游戏很简单，下面让我们来看一个稍微难一点的。

游戏2
规则：
有x个石子，两人轮流取，最多取y个，最少取z个，且z<=y，没得取的人输，两个人都按照最优策略进行游戏，问先手必胜的充要条件。

恩，如果大家都没想出来的话。那我就不公布答案了，我其实想借这个问题引入必胜态和必败态的概念。

我们定义必胜态为先手一定能赢的局面，必败态为先手一定不能赢的局面。
然后，对于一个局面，不是必胜态就是必败态（因为没有平局）。
那么显然，对于一个局面a，设B为所以可以转移到局面a的局面的集合。
那么a为必胜态当且仅当存在b属于B，满足b是必败态；
那么a为必败态当且仅当对于所有b属于B，满足b是必胜态。
这个东东的证明是很简单地，如果存在b是必败态，一个聪明的人就会让对方处于必败态，然后自己取胜，如果所有b都是必胜态，那么再怎么聪明的人也只能让对方处于必胜态，然后自己心甘情愿的输掉比赛。

有点无聊，那我们就来点数据吧：
对于游戏2，x=9,y=2,z=4，写出0-9的先手必胜态表，必胜态用W表示，必败态用L表示。
0123456789
LWWWWLLWWW
如果用熟悉的的动态规划来做，那么动规方程就是f[i]=or{!f[j];4>=i-j>=2且j>=0}（f[i]=true表示i为必胜态）。
然后问题再变难一点。

游戏3
规则：
有y个石子，两人轮流取，可以取x个，x属于数集X，没得取的人输，两个人都按照最优策略进行游戏，问哪些是必胜态。

恩，这个问题留给大家思考。

游戏4
规则：
有n堆石子，每堆有xi个石子，两人轮流取，可以在一堆中取任意的石子，但不能不取，也不能跨堆取，没得取的人输，两个人都按照最优策略进行游戏，问哪些是必胜态。

比如有这样3堆：7 11 13。
大家可以先讨论一下。

下面我们引入用异或解NIM取石子问题。
让我们来证明一些东西：
对于a1,a2,...,an，设SG=a1 xor a2 xor ... xor an。

引理1
若SG!=0，那么必然存在0<=k<ai，使得SG xor ai xor k=0，即SG xor ai=k。
即存在0<=(SG xor ai)<ai，显然0<=(SG xor ai)对于1<=i<=n恒成立，我们设SG的二进制最高位为h，那么必然存在ai，满足ai的第h位为1（若不存在，那么SG的h位不可能为1，所以必然存在），这时SG xor ai和ai相比高于h位的地方不会变，而h位变成0了，所以SG xor ai<ai。

引理2
若SG=0，那么不存在0<=k<ai，使得SG xor ai xor k=0，这是显然的，反证法，若存在，那么0 xor ai xor k=0，ai=k，与k<ai矛盾。

下面，我们把异或和NIM联系到一起。
对于一个局面(a1,a2,...,an)，设SG=a1 xor a2 xor ... xor an。
则它为必败态当且仅当SG=0。
首先，我们知道(0,0,...,0)是必败态，这时SG=0，所以命题在这总情况下成立。
然后对于一个局面(a1,a2,...,an)，若a1 xor a2 xor ... xor an != 0，由引理1可知，存在0<=k<ai，使得SG xor ai xor k=0，即a1 xor a2 xor ... xor ai xor ... xor an xor ai xor k=a1 xor a2 xor ... xor k xor ... xor an=0，这就是说，我们可以把ai变成k，使得对方处于一个SG=0的局面(a1,a2,...,k,...,an)。
然后对于一个局面(a1,a2,...,an)，若a1 xor a2 xor ... xor an = 0，由引理2可知，不存在0<=k<ai，使得SG xor ai xor k=0，所以无论如何，都会让对方走到一个SG!=0的局面。
由于棋子数一直在减小，所以最后会结束在SG=0的局面。
若先手处于SG!=0的局面，那么，先手的人会走到一个SG=0的局面，对手又不得不走到一个SG!=0的局面，一直到石子被取完，后手输为止。
若先手处于SG=0的局面，可以同样的分析，先手必败。

例题1（POJ1704[Georgia and Bob]）
题目描述：
两个人玩游戏，在标有1,2,3,4,5...的格子上有一些棋子，规则是选一枚棋子移动，要求不能跨越棋子移动，必需向左移动（可以移动任意格），不能移动的就输掉比赛。
下面是一个棋局的例子：
+--+--+--+--+--+--+--+--+--+
|1x|2 |3x|4 |5 |6x|7x|8 |9 |（旁边标有x的表示在这里有棋子）
+--+--+--+--+--+--+--+--+--+
给出棋子的初始位置，若先手胜，输出"Georgia will win"，否则输出"Bob will win"（不含引号）。
输入格式：
多组数据。
对于每组数据，第一行是有一个T，表示有T组数据。
对于每组数据，第一行有一个N，表示有N枚棋子。
接下来的一行有N个数，分别为每个棋子的位置。
输出格式：
对每组数据，输出一行，如题目描述那样。
样例输入：
2
3
1 2 3
8
1 5 6 7 9 12 14 17
样例输出：
Bob will win
Georgia will win
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
我们从右到左，将每2个棋子看成一对来处理。
如果对方移动某对棋子中的左边棋子x步，那么我方就移动右边棋子x步。
如果对方一定某对棋子中的右边棋子，那么就可以看作NIM游戏了。

刚刚我们研究了一下最最朴素的NIM游戏，下面我们要更深入的理解SG函数。
首先SG函数的定义SG(x)=mex({SG(y);x局面可以转变到y局面})，其中mex(X)=min{i;i不属于X且i为自然数}。
先解释一下mex函数，mex函数的参数是一个由一些自然数组成的数集，返回最小的没有出现在这个数集中的自然数，特别的，如果mex作用在空集上，返回的是0。
再解释一下SG函数，SG函数的参数是一个局面，返回一个自然数，就是这个局面的SG值。
首先，对于一个局面x，
如果SG(x)!=0，x可以转移到SG值为0到SG(x)-1的局面，类比NIM游戏，就是当前有SG(x)颗石子，可以取它，剩下0到SG(x)-1颗石子，与此同时x可能转移到某些SG值大于SG(x)的局面y，但是此时对手总可以再将局面y转移回SG值为SG(x)的局面，直至当前选手必选将局面转移到SG值为0到SG(X)-1的局面；
如果SG(x)=0，那么要不是x不能转变到任何状态（必败态），就是x只能转到SG值非0的状态，类比NIM游戏，就是取到0颗后就不能再取了，因为如果能够转到y，那么SG(y)!=0，对方又可以让y转到SG值为0的状态，直至没有前驱。
一个局面x，设y=SG(x)，那么它就相当于有y颗石子的堆。
对于局面(x1,x2,...,xn)，它有子局面x1,x2,...,xn，那么就相当于有n堆石子，分别有SG(x1),SG(x2),...,SG(xn)颗石子。
所以局面(x1,x2,...,xn)为必败态当且仅当SG(x1) xor SG(x2) xor ... xor SG(xn)=0。
并且对于局面(x1,x2,...,xn)不给证明的给出下面的结论，SG((x1,x2,...,xn))=SG(x1) xor SG(x2) xor ... xor SG(xn)。
证明：

对于a1,a2,...,an，设SG=a1 xor a2 xor ... xor an。

引理3
对任意0<=SG'<SG，必然存在0<=k<ai，使得SG xor ai xor k=SG'。
即存在0<=(SG xor ai xor SG')<ai，显然0<=(SG xor ai xor SG')对于1<=i<=n恒成立。
因为SG'<SG，所以必然存在h，SG'的h位为0而SG的h位为1，且高于h位时SG'和SG相同。
这时必然存在ai，满足ai的第h位为1（若不存在，那么SG的h位不可能为1，所以必然存在）。
这时SG xor ai xor SG'和ai相比高于h位的地方不会变，而h位变成0了，所以0<=k=SG xor ai xor SG'<ai。

引理4
不存在0<=k<ai，使得SG xor ai xor k=SG，这是显然的，反证法，若存在，那么SG xor ai xor k=SG，ai=k，与k<ai矛盾。

由引理3和引理4可知对于局面(x1,x2,...xn)，若我们定义SG((x1,x2,...,xn))=SG(x1) xor SG(x2) xor ... xor SG(xn)，则满足SG((x1,x2,...,xn))=mex{SG((x1,x2,...,xn)')}。又因为显然对于任何局面，其SG值是唯一确定的，所以这便是我们要求的局面(x1,x2,...,xn)的SG函数。

然后如果我们用定义来计算在游戏4中，局面(a)的SG值，我们发现SG(a)=a，这就是NIM取石子的神奇之处。

例题2（POJ2960[S-Nim]）
题目描述：
两个人玩游戏，规则是有n堆石子，分别有a1,a2,...,an颗石头，每次从一堆石子中取一些石子，但是可取的石子数是规定了的，必须是{s1,s2,...,sk}中的一个，谁无法操作就输。
输入格式：
多组数据。
对于每组数据，第一行是有一个k，接下来有k个数，分别为s1,s2,...,sk。
第二行有一个数m，表示会给出m个局面。
接下来的m行，先是一个n，然后有n个数，分别为a1,a2,...,an。
若k=0，表示数据结束。
输出格式：
对每组数据，输出一行m个字符组成的字符串，分别表示该组数据中的n个局面是必胜态还是必败态，必胜态用W表示，必败态用L表示。
样例输入：
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
样例输出：
LWW
WWL
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
SG(x)=mex{SG(y);0<=y<x且x-y属于{s1,s2,...,sk}}
SG(GAME)=SG(a1) xor SG(a2) xor ... xor SG(an)

例题3（POJ3537[Crosses and Crosses]）
题目描述：
两个人玩游戏，规则是在标有1,2,3,4,5...，n的格子上画X，一直画一直画，画到有三个X相邻就获胜。
输入格式：
一个数n，就是题目描述中的n。
输出格式：
输出一行，先手胜输出1，否者输出2。
样例输入1：
3
样例输出1：
1
样例输入2：
6
样例输出2：
2
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
+--+--+--+--+--+--+--+--+--+
|.....|AX|BX|CX|DX|EX|.....|
+--+--+--+--+--+--+--+--+--+
如果选手A在CX处画了X，那么显然如果选手B在AX,BX,DX或EX处再画一个X，那么下一步选手A就能获胜，所以选手B要想不输就只能在其他地方画X。
于是游戏n变成了游戏(n-CX-2)和游戏(CX-1-2)，所以SG(n)=mex{SG((n-i-2,i-2-1));i>=3且i<=n-2}=mex{SG(n-i-2)xorSG(i-2-1);i>=3且i<=n-2}。

例题4（POJ2425[A Chess Game]）
题目描述：
两个人玩游戏，规则是给定一个有向无环图，在一些节点上放了棋子，两人轮流移动棋子，每次只能选一颗棋子沿边走一步（一个地方可以放任意多的棋子），最后如果不能走了就输。
输入格式：
多组数据。
每组数据的第一行是N，表示图有N各节点，依次标号为0,1,...,N-1。
接下来的N行，分别表述0,1,..,N-1的出边。
这N行，第一个数x表示出度，接下来的x个数分别为该节点的后继。
接下来有一些询问。
每个询问以一个数M开头，若M=0则表示询问结束，否则有M个数，分别为M个棋子所在的节点编号。
输出格式：
对每个询问，如果是先手必胜输出"WIN"，否者输出"LOSE"（不含引号）。
样例输入：
4
2 1 2
0
1 3
0
1 0
2 0 2
0

4
1 1
1 2
0
0
2 0 1
2 1 1
3 0 1 3
0
样例输出：
WIN
WIN
WIN
LOSE
WIN
数据范围：
不管了，大家想算法就行了，不管时空复杂度。

题解：
对于一个棋子SG(x)=max{SG(y);y是x的前驱}。对于m个棋子，SG((x1,x2,...,xm))=SG(x1) xor SG(x2) xor ... xor SG(xm)。

其它题目推荐POJ2975[Nim]，POJ2234[Matches Game]，POJ1067[取石子游戏]，USACO[Holiday 2010 Bonus Competition/glod]rocks。