游戏策略讲义

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,游戏策略,朱全民,Nim,问,问,题,题,取,石,石,子,子,问,问,题,题,有N,堆,堆,石,石,子,子,，,，,其,其,中,中,第,第i,堆,堆,有,有P,i,颗,石,石,子,子,，,，,每,每,次,次,从,从,某,某,一,一,堆,堆,里,里,选,选,出,出,若,若,干,干,石,石,子,子,去,去,掉,掉,（,（,但,但,不,不,能,能,不,不,去,去,石,石,子,子,）,）,，,，,两,两,人,人,轮,轮,流,流,取,取,石,石,，,，,谁,谁,不,不,能,能,继,继,续,续,取,取,谁,谁,就,就,输,输,了,了,。,。,什,么,么,情,情,况,况,下,下,先,先,手,手,必,必,胜,胜,，,，,什,什,么,么,情,情,况,况,下,下,后,后,手,手,必,必,胜,胜?,第一堆：a,1,=3,第二堆：a,2,=3,第三堆：a,3,=1,分,析,析,从,上,上,述,述,博,博,弈,弈,树,树,可,可,以,以,看,看,出,出3,3,1,是,是,必,必,胜,胜,点,点,，,，,那,那,么,么,我,我,们,们,可,可,以,以,这,这,么,么,想,想,，,，,如,如,果,果,某,某,个,个,点,点,是,是,必,必,胜,胜,点,点,，,，,则,则,取,取,完,完,棋,棋,子,子,后,后,，,，,必,必,须,须,使,使,得,得,对,对,方,方,落,落,在,在,必,必,败,败,点,点,。,。,若只有,一,一堆石,子,子，先,收,收走必,胜,胜,若有m,堆,堆石子,，,，每堆,只,只有一,颗,颗石子,，,，m,堆,堆为奇,数,数时，,先,先手必,胜,胜。,若有m,堆,堆石子,，,，每堆,有,有k颗,石,石子，m堆,为,为奇数,时,时，先,手,手必胜,。,。,第1次,，,，先手,取,取k棵,，,，轮到,对,对手走,时,时，若,对,对手取k棵，,则,则先手,也,也取k,棵,棵，若,对,对手取xP,i,，S-S，P,i,P,i,，则P,i,XORP,i,0。,所,所以SXORP,i,XORP,i,=S=0,，,，即S=P,i,XOR P,i,0。,满,满足P局面,的,的所有子局,面,面都是N局,面,面。,若S0,，,，设S的二,进,进制位是A,1,A,n,，考虑第一,位,位是1的。,在,在P中取出,该,该位同是1,的,的，不妨设,为,为P,1,。可知P,1,XORS0），两,人,人轮流取石,，,，谁不能继,续,续取谁就输,了,了。,什么情况下,先,先手必胜，,什,什么情况下,后,后手必胜?,示例m=2,a,1,=7,a,2,=3,a,3,=5,1 2 3 4 5 6 7,将P,1,P,2,P,3,P,n,对m+1求,余,余得到P,1,P,2,P,3,P,n,，然后符合,定,定理一的结,果,果，记S=P,1,XOR P,2,XOR P,3,XOR,XORP,n,。若S=0,则,则为P局面,，,，否则为N,局,局面。,证明：,将P,1,P,2,P,3,P,n,分解成为两,部,部分P,1,P,2,P,3,P,n,和 R,1,R,2,R,3,R,n,，其中R,1,R,2,R,3,R,n,都是m+1,的,的倍数。,若对P,1,P,2,P,3,P,n,部分取子，,则,则按NIM,方,方法走步，,若,若对R,1,R,2,R,3,R,n,部分取子，,则,则后手取k,颗,颗，先手方,取,取m-k+1颗，先手,始,始终保持不,对,对R,1,R,2,R,3,R,n,部分先取子,。,。,若初始局面,为,为胜局面，P,1,P,2,P,3,P,n,部分NIM,方,方法取子必,胜,胜，由于R,1,R,2,R,3,R,n,都为m+1,的,的倍数，因,此,此，按m+1互补的取,法,法，先手一,定,定能取到最,后,后K1,的,的情况，我,们,们令把P,1,P,n,这n个数，,转,转成二进制,，,，然后每位,分,分别相加，,每,每位最后结,果,果mod(K+1),即,即可。如果,每,每一位结果,都,都是0，则,为,为P局面，,否,否则是N局,面,面,示例,P,1,P,2,P,3,P,4,=3,5,10,15,，,，K=2,3,11,5,10 1,10,1 01 0,15,1 11 1,2 20 0,所以这是N,局,局面。,证明与NIM证明类似,。,。下面我们,看,看看具体的,取,取法。,Nim,k,问题的取石,子,子方法,设P,1,P,2,P,3,P,n,为n堆石子,数,数目。P,i,已标记的石,子,子堆，D0i和D1i,分,分别表示所,有,有已标记的,石,石子堆中第i位为0和1的总数。,1.找出,加,加法结果非0的最高位,，,，设为W。,2.找出,一,一个二进制,第,第W位为1,、,、而且未标,记,记的石子堆Pi，将Pi标记，并,把,把它的第W,位,位由1改为0。对于Pi的第1,到,到(W-1)位，逐个,判,判断，第j,位,位如果为0,则,则Inc(D0j)，否则Inc(D1j)。,3.若更,新,新后的S某,一,一位非0（,即,即Si,0），且Si+D0iK，或Si-D1i=0|ng(y)for E,如果x的出,度,度为0，那,么,么g(x)=0。（边,界,界条件）,SG函数的,内,内涵,g(x)就,是,是x的后继,点,点的SG值,中,中没有出现,过,过的最小值,。,。,这样定义有,什,什么好处呢,？,？我们把一,个,个,图的当前状,态,态值,定义为游戏,者,者处在的这,个,个点的SG,值,值。,如果游戏者,处,处在一个点x，g(x)0。那,么,么0,1,g(x)-1这些数必,然,然都出现在x的后继节,点,点的SG值,中,中，而游戏,者,者可以走到,这,这些点中的,任,任意一个。,也,也就是说：,游,游戏者可以,通,通过一步走,棋,棋把,图的当前状,态,态值,任意的减小,（,（当然必须,保,保证状态值,始,始终=0,）,）。,如果游戏者,处,处在一个点x，g(x)=0。那,么,么,游戏者无论,如,如何移动，,下,下一个点的SG值都不,等,等于0,。,SG函数性,质,质,对于一个图,游,游戏，如果,图的当前状,态,态,等于0，那,么,么先手必败,，,，否则必胜,。,。,证明：,如果当前点SG=0，,先,先手无论怎,么,么走，都会,到,到达一个SG0的,点,点；接着后,手,手就能设法,到,到达一个SG=0的点,。,。也就是说,后,后手总是能,移,移动，而先,手,手总是处在SG=0的,点,点。游戏不,能,能无限的进,行,行下去，一,旦,旦先手到达,一,一个出度等,于,于0的点，,游,游戏结束，,先,先手败。,如果当前点SG0，,先,先手可以走,到,到一个SG=0的点，,这,这样后手面,对,对一个必败,状,状态，所以,先,先手必胜。,SG函数在,多,多图游戏中,的,的应用,多图游戏,有多个图，,每,每个图都有,一,一个当前节,点,点。两个游,戏,戏者轮流行,动,动。每个人,每,每次可以把,某一个,图中的当前,节,节点沿着该,点,点连出的有,向,向边移动到,另,另一个点。,无,无法移动的,那,那个人输。,结论:,设这些图的,当,当前状态值,分,分别是a1,a2,ak，如果：a1 a2,ak=0,，,，那么先手,必,必败，否则,必,必胜。,证明：,请回忆SG,函,函数的性质,：,：如果当前,某,某图的状态,值,值0，那,么,么游戏者可,以,以通过一步,走,走棋把,图的当前状,态,态值,任意的减小,。,。因此一个,状,状态值为x,的,的图等价于Nim Game中规,模,模为x的一,堆,堆石子！,如果a1,a2,ak=0，先手,无,无论怎么走,都,都会令a1,a2,ak 0。（ai,是ai变,化,化后的值）,如果a1,a2,ak 0，那么,就,就完全等价,于,于NimGame，,先,先手可以按,照,照NimGame的,走,走法行动，,使,使得a1,a2,ak,=0,。,。,证毕。,SG的妙处就是,把,把多图游戏转化,成,成了Nim Game。,保龄球问题,在一行中有n个,木,木瓶，你和你的,朋,朋友轮流用保龄,球,球去打这些木瓶,，,，由于你们都是,高,高手，每一次都,可,可以准确的击倒,一,一个或相邻的两,个,个木瓶，谁击倒,最,最后一个剩余的,木,木瓶谁将获得胜,利,利。如果由你先,打,打，请你分析，,你,你应该采取什么,策,策略来确保赢得,胜,胜利。,分析,为了更方便的看,清,清楚问题的本质,，,，我们用另一种,方,方式来描述这个,游,游戏。,最开始有一堆石,子,子（n个），每,一,一次你可以进行,以,以下四种操作中,的,的一种：,从中取出一颗石,子,子,从中取出两颗石,子,子,从一堆中取出一,颗,颗石子，并且将,这,这一堆中余下的,石,石子任意分成两,堆,堆（每堆至少一,颗,颗）,从一堆中取出两,颗,颗石子，并且将,这,这一堆中余下的,石,石子任意分成两,堆,堆（每堆至少一,颗,颗）,这四种操作，实,际,际上就依次对应,于,于原来游戏中的,以,以下四种击倒法,：,：,击倒一段连续的,木,木瓶中最靠边的,一,一个,击倒一段连续的,木,木瓶中最靠边的,连,连续两个,击倒一段连续的,木,木瓶中不靠边的,一,一个,击倒一段连续的,木,木瓶中不靠边的,连,连续两个,求解,把局面看作顶点,游戏规则看作,边,边,这是一个典,型,型的图游戏。,如果当前局面被,分,分成了M堆，(A1，A2，,，,，Am)，则,SG(A1,A2,Am)=SG(A1),SG(A2),SG(Am),显然,SG(0)=0,剩余一个时，只,能,能取到0个，而SG(0)=0,，,，所以SG(1)=1。,剩余两个时，可,以,以取到0或1，,其,其中SG(0)=0，SG(1)=1，,所以SG(2)=2,剩余三个时，我,们,们可以把局面变,成,成1或2或两堆,均,均为1。,其中SG(1)=1，SG(2)=2，SG(1，1)=SG(1)SG(1)=0，,所,所以SG(3)=3,SG(4)可分,解,解为SG(2),SG(3),SG(2),SG(1),SG(1),SG(1)=2,3,3,0,所以SG(4)=1,对于任意一种局,面,面P，的SG值,为,为SG(P)，,为,为了赢得胜利，,我,我们只需将他的,局,局面变成Q,使,得,得SG(Q)=0即可。,优化,对于每一个N值,，,，我们为了求出,他,他的SG值,时,时间复杂度为O(N)，如果,只,只要求你求出你,第,第一步应该如何,行,行动，那么这种,普,普通的方法需要O(N,2,)的复杂度，显,然,然不能令我们满,意,意。,这个问题看似已,经,经解决，但我们,可,可以进行优化。,事实上，我们通,过,过观察较小的数,的,的SG值，可以,发,发现：,0 11的SG值为：0 12 3 14 3 2 14 2 6,1223的SG值为：4 12 7 14 3 2 14 6 7,2435的SG值为：4 12 8 54 7 2 18 6 7,3647的SG值为：4 12 3 14 7 2 18 2 7,4859的SG值为：4 12 8 14 7 2 14 2 7,6071的SG值为：4 12 8 14 7 2 18 6 7,7283的SG值为：4 12 8 14 7 2 18 2 7,并且从72开始,，,，SG值以12,为,为循环节，不断,的,的重复出现，这,样,样我们求出所有SG值的复杂度,就,就降到了常数，,这,这样判断第一步,的,的如何选择的复,杂,杂度就降为了O(N)。,Strips(poi2000),Stripes is atwo playergame.Necessary requisites area board andrectangularstripes inthreecolours:red,green andblue.All the redstripes havedimensionsc x 1,green-z x1,and blue-n x1,where c,z andn areinteg