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

[博弈论之NIM取石子游戏与SG函数.zip]下载(貌似Google Documents已被墙,会翻墙的自己翻墙下,不会的在下面留个邮箱。)

前言:

恩,本文会简要介绍一下NIM取石子游戏与SG函数,并附上一些有趣的例题。

1.简单的取石子游戏

首先,让我们来看一看最简单的取石子游戏。
游戏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,没得取的人输,两个人都按照最优策略进行游戏,问哪些是必胜态。
恩,这个问题留给大家思考。

2.基本的NIM取石子游戏

游戏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的局面,可以同样的分析,先手必败。

3.例题1

例题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游戏了。

4.NIM取石子游戏与SG函数的关系

刚刚我们研究了一下最最朴素的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取石子的神奇之处。

5.例题2

例题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)

6.例题3

例题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}。

7.例题4

例题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)。

8.例题还有很多

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

链接:

  • 《由感性认识到理性认识——透析一类搏弈游戏的解答过程》 张一飞 国家集训队2002论文
  • 《组合游戏略述——浅谈SG游戏的若干拓展及变形》 贾志豪 国家集训队2009论文
  • 《Sprague-Grundy Theory》 http://blog.sina.com.cn/s/blog_617615cd0100f6xv.html
  • 《博弈论(二):Sprague-Grundy 函数定理》 http://hi.baidu.com/yangchenhao/blog/item/c2883f1e70869df01bd57688.html

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注