浅谈SG函数_qzc.pptx

浅谈SG函数 -----秦正才;(hdu1847) （问题引入）：作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她们打牌的规则是这样的：1、??总共n张牌;2、??双方轮流抓牌；3、??每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）4、??抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生~），并且每次都是Kiki先抓牌，请问谁能赢呢？当然，打牌无论谁赢都问题不大，重要的是马上到来的CET-4能有好的状态。;“Impartial Combinatorial Games”（以下简称ICG）。; 给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判 负。事实上，这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义Sprague-Garundy函数。 首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、 mex{2,3,5}=0、mex{}=0。 对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。 所有的terminal position所对应的顶点，也就是没有出边的顶点，其SG值为0，因为它的后继集合是空集。然后对于一个g(x)=0的顶点x，它的所有后继y都满足 g(y)!=0。对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。;该题的SG函数分析：;Code;NIM游戏：（1堆向多堆的过渡）;(Bouton‘s Theorem)：对于一个Nim游戏的局面(a1,a2,...,an)，它是P-position当且仅当a1^a2^...^an=0，其中^表示异 或(xor)运算。;有向无环图中顶点的SG值的意义：当g(x)=k时，表明对于任意一个0=ik，都存在x的一个后继y满足g(y)=i。也就是 说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏，Nim 游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶点的 SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！ 对于n个棋子，设它们对应的顶点的SG值分别为(a1,a2,...,an)，再设局面(a1,a2,...,an)时的Nim游戏的一种必胜策略是把 ai变成k，那么原游戏的一种必胜策略就是把第i枚棋子移动到一个SG值为k的顶点。其实我们还是只要证明这种多棋子的有向图游戏的局面是P-position当且仅当所有棋子所在的位置的SG函数的异或为0。这个证明与上节的 Bouton‘s Theorem几乎是完全相同的，只需要适当的改几个名词就行了。 所以我们可以定义有向图游戏的和(Sum of Graph Games)：设G1、G2、……、Gn是n个有向图游戏，定义游戏G是G1、G2、……、Gn的和(Sum)，游戏G的移动规则是：任选一个子游戏Gi 并移动上面的棋子。Sprague-Grundy Theorem就是：g(G)=g(G1)^g(G2)^...^g(Gn)。也就是说，游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。;Code：;Lasker‘s Nim游戏：（hdu 3032 Nim or not Nim? ）;分析：很明显：sg(0) = 0，sg(1) = 1。 状态2的后继有：0，1和（1，1），他们的SG值分别为0，1，0，所以sg(2) =2。 状态3的后继有：0、1、2、（1，2），他们的SG值分别为0、1、2、3，所以sg(3) = 4。 状态4的后继有：0、1、2、3、（1，3）和（2，2），他们的SG值分别为0，1，2，4，5，0，所以sg(4) = 3. 再推一些，推测得到：对于所有的k = 0，有 sg( 4k+1 ) = 4k+1； sg( 4k+2 ) = 4k+2； sg( 4k+3 ) = 4k+4； sg( 4k+4 ) = 4k+3。 假设游戏初始时有3堆，分别有2、5和7颗石子。三堆的SG函数值