[课件]组合数学——组合游戏

1、组合数学（一）,李子星,内容提要,组合游戏 巴什博弈 威佐夫博弈 尼姆博弈 有向图游戏与有向图游戏的和与SG函数 反尼姆博弈与反组合游戏 继续探讨ICG的和,组合游戏,组合游戏（Combinatorial Games），又称为“Impartial Combinatorial Games”（以下简称ICG）。 满足以下条件的游戏是ICG： （1）有两人参与游戏，轮流做出决策，两人都最理性得追求胜利 （2）两名选手交替做出决策，无法做出决策的人失败，然后游戏结束。 （3）游戏总能在有限次决策后结束 （4）游戏的同一个状态不会多次抵达 （5）任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状

2、态有关，而与游戏者无关,组合游戏,定义“先手必败”状态（必败态），和“先手必胜”状态（必胜态）： （1）无法进行任何移动的局面是必败态； （2）可以移动到必败态的局面是必胜态； （3）所有移动都导致必胜态的局面是必败态。 按照这个定义，如果局面不可能重现，那么每个状态或者是必胜态或者是必败态，而且可以通过定义计算出来。,巴什博弈,【问题一】 有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。取走最后一个物品的人获得胜利。问先手是否必胜。,巴什博弈,这显然是一个组合游戏问题 对于一个状态，可以用当前的物品数x来唯一描述。 容易知道，对于一个状态x，如果x%(m+1)=0

3、，那么这个状态肯定是必败态，否则是必胜态。,巴什博弈,设当前状态是x： 如果x=0，那么显然这是一个必败态 如果x%(m+1)0，即0x%(m+1)=m，那么取走x%(m+1)件物品后得到的状态就是一个模m+1等于0的状态 如果x%(m+1)=0，那么不管怎么取，都一定是移动到一个模m+1不等于0的状态 这三条分别对应了必败必胜态定义的三条 所以状态x是必败态当且仅当若x%(m+1)=0,威佐夫博弈,【问题二】 有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，取走最后一颗石子的人获得胜利。问先手是否必胜。,威佐夫博弈,从性质入手： 令必败二元组

4、为(a, b)形式（aa2,b1b2,a1b2,a2b1。 推论二：对于任意两个的必败二元组(a1,b1)，(a2,b2)，有b1-a1b2-a2。即，所有必败二元组的两元之差的绝对值必定各不相同。,威佐夫博弈,利用性质和推论，可以证明如下结论： 将必败二元组按首元为关键字排序，每个必败二元组中首元为未在前面的必败二元组中出现的最小正整数，并且第N组中两个数差为N。,威佐夫博弈,可以利用数学归纳法证明： 前两组为(0, 0)和(1, 2)，显然符合前述的结论 若第0组到第N组都与前述的结论相符，则： 设未在第0到第N组中出现的最小正整数为M，考察二元组(M,M+N+1) 如果选择从数量为M的堆

5、中取石子，不妨设变成了(M-X,M+N+1)，而(M+N+1)-(M-X)=N+1+XN，且M-X一定与之前的某个必败二元组中一元相等，这样就有一个包含M-X，且不与之前任何一组必败二元组相同的二元组，根据推论一，(M-X,M+N+1)这个二元组一定不是必败二元组 如果选择从数量为M+N+1的堆中取石子，不妨设变成了(M,K) 若K=M，由于M与之前的任何一个必败二元组中都未出现，且N+1K-M=0，根据推论二，(M, K)这个二元组一定不是必败二元组 若KN，根据推论一，(M-X,M+N+1-X)这个二元组一定不是必败二元组 即(M, M+N+1)能够扩展到的状态都不是必败态，所以它就是一个

6、必败态 又根据排序的规则，(M,M+N+1)一定是必败二元组序列的第N+1项 所以第0到第N+1组必败二元组也与前述的结论相符,威佐夫博弈,由此，所有的必败态都完美的找到了： (0,0) (1,2) (3,5) (4,7) (6,10) (8,13). 作为经典问题，它还有更强的结论： 第n个必败态一定是： (n*(1+5)/2, n*(1+5)/2+n) 其中“ ”是取下整。 所以判断一个状态(a,b)（a=b）是不是必败态只需要判断a是否等于(b-a)*(1+5)/2。,尼姆博弈,【问题三】 有若干堆石子，两个人轮流从中取石子。每堆石子的数量都是有限的，合法的取石子操作是“选择一堆石子并拿

7、走若干颗（不能不拿）”。拿走最后一颗石子的人获得胜利。问先手是否必胜。,尼姆博弈,当然这一题也可以用必胜必败态的性质用递推来求解。 但若考虑时间复杂度，就会发现是行不通的（尤其是当石子的堆数很多，且每堆石子初始的数量也很多的时候）。 它的解答当然也完全配得上其经典问题的称号：对于一个尼姆博弈的局面(a1,a2,.,an)，它是必败态当且仅当a1a2.an=0，其中“”表示异或(xor)运算。,尼姆博弈,证明很简单。还是由必胜必败态性质入手： 对于局面(0,0,)，显然00=0，且这是一个必败态。 对于局面(a1,a2,.,an)，如果x=a1a2.an0，那么在a1到an这n个数中一定至少存在

8、一个数ap满足0ak，都有 a1a2.pan a1a2.akan=0。,尼姆博弈,对于结论“如果x=a1a2.an0，那么在a1到an这n个数中一定至少存在一个数ap满足apxap”的证明如下： （1）从x的二进制表示入手，设x的二进制最高的非0位是第m位 （2）那么a1到an中至少有一个数的二进制数第m位为1，从其中随便取一个假设为aq （3）那么aqx的结果的二进制数第m位一定为0 （4）且aqx的结果的二进制数中高于m位的部分全部与aq的一样 （5）所以aqx一定小于aq。,尼姆博弈,aq：()1 x： 1 aqx：()0,故aqx aq，由此尼姆博弈问题也就完美的解决了。,更难的博弈问

9、题,既然尼姆博弈的必胜策略已经找到了，那么如果规则改变一些，还能找到必胜策略么？ 比如说【问题四】 有n堆石子，两个人轮流从中取石子。每次可以从第1堆石子里取1颗、2颗或3颗，或者从第2堆石子里取任意奇数颗，或者从第3到第n堆中任选一堆并取走任意正整数颗。取走最后一颗石子的人获得胜利。问先手是否必胜。 这时问题瞬间复杂了很多。接下来我们就来讨论这样更进一步的内容。,有向图游戏,先来研究一个看上去似乎更为一般的游戏：给定一个“有向无环”图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。可以称这个游戏为“有向图游戏”。 很容易发现，这个游戏可以认为是所有组合游

10、戏的抽象模型。 也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。,有向图游戏与SG函数,下面我们就在有向无环图的顶点上定义MEX（minimal excludant）运算和SG（Sprague-Grundy）函数。 （1）首先定义MEX运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如MEX0,1,2,4=3、MEX2,3,5=0、 MEX=0。 （2）对于一个给定的有向无环图，定义关于图的每个顶点的SG函数如下：SG(x)=MEXSG(y)|xy，即一个节点的SG函数值等于其所有后继结点的SG函数值

11、集合经过MEX运算后的结果。,有向图游戏与SG函数,来看一下SG函数的性质。 首先，所有的终结状态所对应的顶点，也就是没有后继结点的顶点，其SG值为0，因为它的后继集合是空集。 然后对于一个SG(x)=0的顶点x，它的所有后继y都满足 SG(y)0。 对于一个SG(x)0的顶点，必定存在一个后继y满足SG(y)=0。,有向图游戏与SG函数,是不是和必胜必败态性质非常相似？ 没错，这三条性质就说明了：顶点x所代表的状态是必败态当且仅当SG(x)=0，我们通过计算有向无环图的每个顶点的SG值，就可以对每种局面找到必胜策略了。 但是这样看的话，SG函数的值域只需要在01范围内就够了，干嘛还要搞个这么

12、麻烦的MEX运算呢？,多棋子有向图游戏与SG函数,因为SG函数的用途远没有这样简单。 如果将有向图游戏变复杂一点：有向图上并不是只有一枚棋子，而是有n枚棋子，每次可以任选一枚进行移动（可以称这个游戏为多棋子有向图游戏），这时怎样确定当前的必胜必败状态？ 这当然还是个ICG，于是肯定也能转化到某个单棋子有向图游戏，但是这样显然太麻烦了。,多棋子有向图游戏与SG函数,让我们再来考虑一下顶点的SG值的意义。 当SG(x)=k时，表明对于任意一个0=ik，都存在x的一个后继y满足SG(y)=i。也就是说，当某枚棋子的SG值是k时，我们可以从这里出发移动到一个SG值为0或1或或k-1的另一个节点，但绝对

13、不能移动到一个SG值为k的另一个节点。 联想一下尼姆博弈，尼姆博弈的规则就是：每次选择一堆石子（假设数量为k），可以把它的数量变成0、变成1、变成k-1，但绝对不能保持k不变。 这表明：如果将n枚棋子所在的顶点的SG值看作n堆相应数量的石子，那么这个尼姆博弈的每个必胜策略都对应于原来这n枚棋子的必胜策略！,多棋子有向图游戏与SG函数,对于n个棋子，设它们对应的顶点的SG值分别为(a1,a2,an)，再设局面(a1,a2,an)的尼姆博弈的一种最佳策略是把ai变成ai。 那么原本的多棋子有向图游戏的一种最佳策略就是把第i枚棋子移动到一个SG值为ai的顶点上去。 是不是很神奇绕了一圈又回到尼姆博弈

14、了！,多棋子有向图游戏与SG函数,只要证明“这种多棋子的有向图游戏的局面是必败态当且仅当所有棋子所在的节点的SG函数值的异或结果为0”就好了。而这个的证明与前面尼姆博弈的证明几乎完全相同，只要适当修改几个名词就行了。 唯一的偏差只有：在有向图游戏中，一个节点的后续节点的SG值可能会大于当前节点的SG值，而尼姆博弈中却不能让某一堆石子的数量增加。 而在多棋子有向图游戏中这个偏差并不会产生错误：由于ICG是有限的（就是说总会结束），而之前关于异或运算的结论并不强制要求每次必须让某一项变小。,多棋子有向图游戏与SG函数,刚才，为了使问题看上去更容易一些，默认了n枚棋子是在一个有向图上移动。但如果不是

15、在同一个有向图上，而是每个棋子在一个独立的有向图上，每次可以任选一个棋子（也就是任选一个有向图）进行移动，这样也不会给结论带来任何变化。 因为你其实可以认为所有棋子还是在一个有向图上，虽然这个图是不连通的。,有向图游戏的和与SG函数,于是，我们可以定义有向图游戏的和（Sum of Graph Games）： 设G1、G2、Gn是n个有向图游戏，定义游戏G=G1+G2+Gn的移动规则是：任选一个子游戏Gi并将上面的棋子移动一步。 则SG(G)=SG(G1)SG(G2)SG(Gn)。 也就是说，游戏的和的SG函数值是它的所有子游戏的SG函数值的异或。,有向图游戏的和与SG函数,再考虑前面的一句话：

16、任何一个ICG都可以抽象成一个有向图游戏。所以“SG函数”和“游戏的和”的概念就不是局限于有向图游戏。 当我们面对由n个子游戏组合成的一个游戏时，只需对于每个子游戏找出求它的各局面的SG值的方法，就可以把这些SG值全部看成尼姆博弈中的石子堆，然后依照找尼姆博弈的必胜策略的方法来找这个游戏的必胜策略了！,有向图游戏的和与SG函数,那么现在，回到前面提出的进阶游戏： 有n堆石子，两个人轮流从中取石子。每次可以从第1堆石子里取1颗、2颗或3颗，或者从第2堆石子里取任意奇数颗，或者从第3到第n堆中任选一堆并取走任意正整数颗。取走最后一颗石子的人获得胜利。问先手是否必胜。,有向图游戏的和与SG函数,我们

17、可以把它看作3个子游戏： （一）第1个子游戏只有一堆石子，每次可以取1、2、3颗，很容易看出x颗石子的局面的SG值是x%4。这实际上就是一个m=3的巴什博弈问题。 （二）第2个子游戏也是只有一堆石子，每次可以取任意奇数颗，经过简单的思考可以知道这个游戏有x颗石子时的SG值是x%2。 （三）第3个子游戏有n-2堆石子，就是一个朴素的尼姆博弈问题。 对于原游戏的每个局面，把三个子游戏的SG值异或一下就得到了整个游戏的SG值，然后就可以根据这个SG值判断是否有必胜策略以及做出决策了。,有向图游戏的和与SG函数,这样，当我们遇到看上去有些复杂的游戏时，思路就应该是： 试图将这个游戏分成若干个子游戏，对

18、于每个比原游戏简化很多的子游戏找出它的SG函数，然后全部异或起来就得到了原游戏的SG函数，就可以解决原游戏了。,有向图游戏的和与SG函数,再举一个小例子： 【问题五】 有n堆石子，每堆初始有ai颗。两个人轮流从中取石子。每次必须任选一堆并取走1到m颗石子。问是否先手必胜。 解法： SG=(a1%(m+1)(a2%(m+1)(an%(m+1),反尼姆博弈,下面我们来看另一个问题： 【问题六】 有若干堆石子，两个人轮流从中取石子。每堆石子的数量都是有限的，合法的取石子操作是“选择一堆石子并拿走若干颗（不能不拿）”。拿走最后一颗石子的人失败。问先手是否必胜。,反尼姆博弈,这个问题的胜利条件与尼姆博弈

19、正好相反，所以被称为反尼姆博弈问题。 这实际上已经不符合我们之前定义的ICG了，那它还有像尼姆博弈那样漂亮的结论么？ 答案是：有的！,反尼姆博弈,SG=0,SG0,存在ai1必败态（1）,不存在ai1必胜态（2）,存在ai1必胜态（3）,不存在ai1必败态（4）,反尼姆博弈,必败态（1）,必胜态（2）,必胜态（3）,必败态（4）,反尼姆博弈与反组合游戏,于是反尼姆博弈问题就这样漂亮的解决了。 但是这个结论能像尼姆博弈一样，推广到任意的“反有向图游戏”和“反多棋子有向图游戏” 么（即胜利条件改为“无法移动棋子的人胜利” ） ？ 答案是：不行！,反尼姆博弈与反组合游戏,回顾一下我们之前讨论SG函数

20、时提到的那个偏差：在有向图游戏中，一个节点的后续节点的SG值可能会大于当前节点的SG值，而尼姆博弈中却不能让某一堆石子的数量增加。 在有向图游戏里，这个偏差不会引发错误，但是在反有向图游戏里，这个偏差就会产生错误了。,反尼姆博弈与反组合游戏,SG=0,SG0,存在ai1“必败态（1）”,不存在ai1“必胜态（2）”,存在ai1“必胜态（3）”,不存在ai1“必败态（4）”,反尼姆博弈与反组合游戏,“必败态（1）”,“必胜态（2）”,“必胜态（3）”,“必败态（4）”,只能到达“必胜态”的状态肯定不是必胜态,反尼姆博弈与反组合游戏,1,0,2,0,“必胜态（2）”,“必胜态（2）”,“必败态（4）”,“必胜态（3）”,反尼姆博弈与反组合游戏,可以发现这个偏差产生错误的当且仅当： （2）不能到达（4），但却能到达（3） 这种情形只有在当前所有ai都是0，并且无法将任意一个改变为1的时候才会出现。 所以想办法屏蔽掉这个偏差产生的错误，反尼姆博弈的结论就可以推广了。 而要屏蔽这个错误，只需要保证“当所有的ai都是0时游戏结束”就行。,继续探讨ICG的和,之前我们提出了“多个游戏之和”某个状态的SG函数值计算方法（各个子游戏的SG函数值全部异或起来）。 而提出的“