公平组合博弈的解法初探.doc

公平组合博弈的解法初探信息科学技术学院 姚金宇 00648043摘要：公平组合博弈是博弈论中的一类基础问题，也是进行深入研究的基础。本文介绍了公平组合博弈的基本理论，并对具体问题的分析，阐述了其应用方法，尤其是如何将公平组合博弈的联合的理论应用于较复杂的博弈问题中。此外，还从游戏设计的角度探讨了如何在约束条件下设计游戏初始局面的问题。关键字：博弈论 公平组合博弈一、 引言博弈论（Game Theory）是一个古老而迷人的学科。一些简单的博弈问题经过数学模型的抽象后能够得到完备的解决，或者得到在概率论下的理想解释。我们经常会碰到诸如此类的问题：游戏1：有n枚石子组成的石碓，两人轮流进行游戏。每次游戏者可以取走石碓中不超过k枚的石子。谁取走最后一颗石子为胜。游戏2：有n堆石子，第i堆有ai枚。两人轮流进行游戏，每次游戏者可以从任意一堆石子中取走任意多个。谁取走最后一颗石子为胜。游戏3：有n堆石子，第i堆有ai枚，两人轮流进行游戏，每次游戏者可以从任意一堆取走任意多枚石子，也可以将任意的一堆石子任意的分成两堆。谁取走最后一颗石子为胜。游戏4：把上面三个游戏联合起来，即同时玩所有的游戏，但每人每一次只能进行某个游戏的某一步，不能继续进行下去的人算输。我们还可能碰到更为复杂的问题，比方说下面的二维硬币游戏：游戏5：在一个T*T的方格阵中，每个格子里放一枚硬币。有的正面朝上，有的反面朝上。两个人做游戏，轮流翻硬币。规则是这样的：选一个跟方格阵平行的矩形，将它的四个角上的硬币翻转，并且要求矩形的右下角必须从正面翻到反面。不能操作的人就输了。上述问题的提出都是从游戏参与者的角度考察胜负情况。有时候我们还需要从游戏设计者的角度，在某些限制条件下设计出满足要求的游戏局面，例如下面的问题：问题6：在游戏5中，要求设计出一个初始局面，使得先手必败。但必须满足一定的约束条件：在某些实现规定的位置必须放置正面向上或者反面向上的硬币。本文的目的就是针对上述问题，对相关游戏操作和游戏设计的解法进行系统的理论分析。就问题6而言，我们至少需要解决两个方面的子问题：1.先手必败的充要条件是什么；2.如何在约束条件下实现这个充要条件。为了解决这些，我们先从博弈论中的公平组合博弈的基本理论着手。二、 公平组合博弈（Impartial Combinatorial Game）的基本理论 本节内容大部分援引自参考文献1 2.1公平组合博弈的定义本文所讨论的公平组合博弈，是指满足下面几个条件的博弈游戏：1 它是两人参与的游戏2 游戏局面的状态集合是有限的3 对于同一个局面，两个游戏者的可操作集合完全相同4 游戏者轮流进行游戏5 当无法进行操作时，游戏结束，此时不能进行操作的一方算输 6 无论游戏如何进行，总可以在有限步之内结束。(the Ending Condition)逐条验证我们不难发现，引言中提到的五个游戏都满足公平组合博弈的定义，因此都属于本文所讨论的范畴。公平组合博弈是博弈论中最简单的博弈类型之一，也是对于其他类型深入讨论和研究的基础。 2.2 N局面和P局面由于公平组合博弈在有限步之内必定会结束，因此不存在平局的状况。我们可以得到这样的结论：在两个游戏者都采用最佳策略的前提下，对于每一个游戏局面，要么就是先手必胜，要么就是后手必胜。我们称先手必胜的局面为N局面(N-position, winning for the Next player)，后手必胜的局面为P局面(P-position, winning for the Previous player)。我们可用下面的方式定义N局面和P局面定义1：1) 每一个最终局面都是P局面2) 对于一个局面，若至少有一种操作使它变成一个P局面，则它是一个N局面3) 对于一个局面，无论如何操作都必然变成一个N局面，则它是一个P局面 2.3 Sprague-Grundy函数对于一般的博弈问题，要判断一个局面是N局面还是P局面往往需要利用博弈树模型，即穷举所有可能的操作步骤，然后根据性质1自底向上逐个局面进行判断。在公平组合博弈中，我们还可以通过Sprague-Grundy函数（以下简称SG函数）来判断N局面和P局面。在定义SG函数之前，我们先定义一个局面的后继局面的概念：定义2：局面y被称为局面x的后继局面，当且仅当局面x可以通过一步操作变成局面y。我们把局面x的后继局面的集合定义为F(x). 定义3：在非负整数集上定义局面x的SG函数g(x)如下： gx=minn0:ngy for yFx通过下面的定理，我们可以建立SG函数与N局面和P局面的关系：定理1：对于任意的局面x，若g(x)=0则x是P局面，否则x是N局面.证明：我们对局面作数学归纳法：1) 对于最终局面x，由定义x是P局面，而此时g(x)=0，定理1成立。2) 假设局面x的所有后继局面都满足定理1。a) 若x的后继局面中存在P局面y，则x是N局面；同时g(y)=0，故g(x)不等于 0b) 若x的后继局面中不存在P局面，则x是P局面；同时由于不存在g(y)=0，故g(x)=0由a)b)可得局面x满足定理1 由归纳假设，定理1对于所有局面x成立. 2.4 公平组合博弈的联合有时候我们面对的游戏，可以分解成若干个简单游戏的联合。例如引言中的游戏2，如果我们把一堆石子看成一个独立的子游戏，则游戏2就是由n个等价的子游戏联合而成的。对于公平组合博弈的联合的定义如下：定义4：对于n个给定的公平组合博弈G1, G2, , Gn，定义他们的联合为G=G1+G2+Gn.对于游戏Gi，设Xi为它的局面集合；对于一个局面xiXi，设Fi(xi)表示xi的后继局面集合。那么G的局面集合X=X1 X2 Xn（其中为笛卡儿积）；对于G的一个局面x=x1,x2,xn，它的后继局面集合F(x) = F(x1, x2, , xn ) = F1(x1) x1x2. xn x1 F2(x2)x3. xn x1 x2. xn-1Fn(xn)也就是说，每一次每一个游戏者只能选择其中一个子游戏进行一步操作。我们通过下面的定理给出一个联合游戏的SG函数值的求法。定理2（Sprague-Grundy 定理）：设gi(x)为Gi的SG函数(1in)，则G=G1+G2+Gn的SG函数g(x1, x2, , xn)=g1(x1)g2(x2)gn(xn)（其中为异或运算）证明：对于G的任意局面x=x1,x2,xn，设b= g1(x1)g2(x2)gn(xn)，如果我们能证明下面两个事实：1) 对于任意一个非负整数ab，都存在x的一个后继局面y，使得g(y)=a2) 不存在x的后继局面y，使得g(y)=b则b就是满足要求的x的SG函数值，命题也就随之得证。对于事实1，令d=ab，设k是d的二进制位的最高位，即2k-1d2k。由于ab，故a的第k位为0，b的第k位为1。故g1(x1),g2(x2),gn(xn)中至少有一个二进制位第k位为1，不妨设为g1(x1)，那么有dg1(x1)0，我们有：gx=minn0:ngy for (x-k)yx。通过简单计算可得g(x)=x % (k+1) (%为取模运算)，于是可知当x=C(k+1)时(C是任意非负整数)，局面x为P局面，否则为N局面。问题得到解决。 3.2游戏2的解决游戏2是经典的Nim游戏。我们先分析一堆石子的情况。设一堆石子的枚数为x，它的SG函数为g(x)，则 gx=minn0:ngy for 0yx。可得g(x)=x(x0)再考虑n堆石子的情况，根据游戏的联合理论及定理2，我们可以将n堆石子的Nim游戏看成是n个一堆石子的子游戏的联合。设此时的SG函数为gn(x1,x2,xn)，其中x1,x2,xn为各堆石子的枚数，我们有：gn(x1,x2,xn) = g(x1)g(x2)g(xn) = x1x2xn因此根据SG函数定义，若x1x2xn = 0，则局面x1,x2,xn为P局面（后手必胜），否则为N局面（先手必胜）。Nim游戏得到解决。很多游戏可以经过适当的变形转换成Nim游戏，从而得到解决，下面的问题就是这样一个例子。（POJ1704 Georgia and Bob）Georgia 和Bob在玩一个游戏：他们在纸上画了一个很长的方格条，将方格从左到右编号为1,2,3,，然后在上面放了n个棋子。如下图： 两个人轮流进行游戏。每一次操作者可以选择一枚棋子将它向左移动至少1格（但不能跨越其他棋子，也不能跨越左边界）。整个游戏过程中必须保证每一个格子上至多只有一枚棋子。如果谁无法继续操作就算输。现在给你棋子的初始位置，请问在两人都采用最佳策略的前提下，是先手获胜还是后手获胜。分析：我们不妨把棋子的左移看成是它们之间空格的右移。设棋子的初始位置为a1a21)将他们移动到左边相邻的一堆，或者将第1堆的若干枚(1)拿走。无法继续操作的人为失败。对等价后的游戏进行分析。首先，若k为偶数，则若游戏者A移动第k堆的若干枚石子到第k-1堆上，那么另一个游戏者B只需要在下一步将同样多的石子从k-1堆移动到k-2堆上即可（第0堆表示将是将石子移走）。因为k是偶数，故k=2，所以可以保证B的操作是一定可以进行的。故对于当前游戏者来说，不到万不得已他是绝对不会移动偶数堆上的石子的。因此我们可以说，偶数堆上的石子对于游戏者来说意味着“已经被拿走了”。在一个必胜策略中，操作者只会移动奇数堆上的石子，而且当他把奇数堆上的石子移动的时候（必然移到偶数堆上），就相当于把这些石子“拿走了”。事实上，如果哪个游戏者操作完后，所有的石子都在编号为偶数的堆上，那么他就已经提前获胜了。这样我们就把等价后的游戏转化成了局面为b1,b3,b5,的Nim游戏，只需要判断这个游戏的胜负，就能决定最开始的游戏是先手获胜还是后手获胜了。 3.3游戏3的解决该游戏的操作集合较为复杂。还是先考虑一堆石子的情况，设g(x)表示x枚石子组成一堆的局面的SG函数，有： gx=minn0:ngy 且 ng(y)gx-yfor 0yx 通过归纳证明可知 具体证明参看参考文献1： gx=0 当x=04k+1 当x=4k+14k+2 当x=4k+24k+4 当x=4k+34k+3 当x=4k+4n堆的情况类似于Nim游戏，可得它的SG函数gn(x1,x2,xn)为gn(x1,x2,xn) = g(x1)g(x2)g(xn) 根据gn的值即可判断原问题的胜负情况。 3.4游戏4的解决游戏4实际上就是游戏1游戏3的联合。根据定理2，设对于游戏1，局面x1的SG函数是g1(x1)；对于游戏2，局面x2的SG函数是g2(x2)；对于游戏3，局面x3的SG函数是g3(x3)。那么对于该游戏，局面x1,x2,x3的SG函数g(x1,x2,x3) = g1(x1)g2(x2)g3(x3) 3.5游戏5的解决对于这个问题，如果能够将原游戏分解成若干个子游戏，例如如果游戏：（H表示正面朝上）能够分解成：，和的联合，我们就只需要考虑只有一枚硬币的局面，这样问题就能大大简化。现在我们要证明下面的结论：定理3：设g(G)是局面G的SG函数，局面G共有n个正面向上的硬币，则G可以分解成n个之包含1个正面向上硬币的局面G1,G2,Gn的叠加。有：g(G) = g(G1)g(G2)g(Gn)证明：由于局面不可逆，所以我们在局面上作数学归纳法。 1o 若G是终局状态，则它的分解出来的G1,G2,Gn都是终局状态，此时g(G)=g(G1)=g(Gn)=0，故g(G)= g(G1)g(G2)g(Gn) 结论成立。 2o 假设G的所有子局面和后继局面都满足定理3。令b= g(G1)g(G2)g(Gn)。类似于定理2的证明，我们需要说明两个事实： 1) 对于任意的非负整数ab，存在一个G的后继局面G使得g(G)=a2) 不存在一个G的后继局面G使得g(G)=b对于事实1，令d=ab，设k是d的二进制位的最高位，即2k-1d2k。由于ab，故a的第k位为0，b的第k位为1。故g(G1),g(G2),g(Gn)中至少有一个二进制位第k位为1，不妨设为g(G1)，那么有dg(G1) g(G1)，根据SG函数的定义，必存在G1的一个后继局面G1，使得g (G1)=dg (G1)将G1到G1所进行的操作作用在G上，得到G的后继局面G（因为G1中放置正面向上硬币的那个位置在G2,Gn中都是放置的反面向上的硬币，所以G的该位置一定是正面向上，因此该操作必然可以进行）由归纳假设，G和G1都满足定理三，设G的分解为G1,G2,Gn1，G1的分解为G11,G12,G13，有：g(G) = g(G1)g(G2)g(Gn)g(G1)=g(G11) g(G12)g(G13)在抑或运算中xx=0，0x=x，我们经过适当的添加整合项，必然有：g(G) = g(G1)g(G2)g(Gn) = (g(G11) g(G12)g(G13)g(G2)g(Gn) = g(G1)g(G2)g(Gn) = dg(G1)g(G2)g(Gn) =a故事实1成立。对于事实2，反设若存在这样的后继局面G，设从G到G的操作是以(x, y)为右下角硬币的操作，不妨设G1中的唯一一枚硬币放置在(x, y)处，则在G1上执行同样的操作得到后继局面G1。由于G和G1都满足定理三，我们有：b = g(G) = g(G1)g(G2)g(Gn)= g(G) = g(G1)g(G2)g(Gn)即g(G1)=g(G1)，与SG函数定义矛盾。因此事实2成立。由归纳原理，综合1o2o，可得对于一切局面G，定理三都成立。根据定理三的结论，计算局面G的SG函数值的问题就转化成了计算只有一枚硬币的局面的SG函数值的问题。设g(x, y)表示在(x, y)位置上有一枚正面向上硬币的局面的SG函数。根据SG函数的定义： gx, y=minn0:ng(a, b)g(x, b)ga,y for 1ax and 1by根据g(x, y)便可得到任意局面G的g(G)值，从而就可以判断局面G是N局面还是P局面了。至此游戏5得到解决。四、 问题6的解决问题6给出一些必须放正面朝上硬币的位置，设为(a1,b1),(a2,b2),(an1,bn1)；还有一些必须放反面朝上硬币的位置。剩下的就是可以选择的位置，设为(x1,y1)(xn2,yn2)。令F = g(a1,b1)g(a2,b2) g(an1,bn1)，定义元素可重集合S=g(xi, yi) | 1=i=n2。由于状态X是后手必胜状态的充要条件是g(X)=0，通过上面的分析我们很自然的得到如下结论：从S中选出若干个数g(xp1, yp2)g(xpm, ypm)使得： g(xp1, yp2)g(xpm, ypm) = F则取(ai, bi)(1=i=n1)与(xpj, ypj)（1=j=m）的位置放置正面向上的硬币，其他地方放置反面向上的硬币，所得到的状态为后手必胜局