国家集训队2007论文集2.王晓珂《解析一类组

解析一类组合游戏四川省绵阳南山中学王晓珂各类取石子游戏1)2人游戏2)没有平局3)2人的待遇相同Alice&Bob的各种消遣游戏国际象棋，中国象棋，围棋判断是否存在必胜策略存在时寻找必胜策略尽量小的时空花费怎样分析组合游戏？归纳分解游戏转化必败状态的特征SG函数值归纳的对象游戏的和：两名参与者轮流操作若干子游戏，每次操作可以选择任意一个子游戏进行操作，最后操作者胜利。这样的游戏称为其子游戏的和！将一个完整的游戏看作若干子游戏的和分析子游戏利用分析子游戏的结论分析原来的游戏分解游戏：Sprague-Grundy函数它是定义在组合游戏状态上的函数用ｇ（ｘ）表示ｘ状态的函数值。它的定如下：ｇ（ｘ）＝ｍｉｎ｛n|n∈N,n≠fory∈F(x)｝请注意ｇ（ｘ）＝０当且仅当ｘ为必败状态游戏状态的SG值必胜状态、策略Sprague-Grundy定理ｇ（ｘ１，ｘ２，……ｘｎ）＝ｇ１（ｘ１）ｘｏｒｇ２（ｘ２）……ｇｎ（ｘｎ）例题1ｎｉｍ游戏两人轮流从若干石堆中取走石子，每次可以取走任意一堆中任意数目的石子，但必须取走至少一枚，取走最后一枚石子的人胜利。先取的人是否存在必胜策略？如果存在，怎样保证必胜？一堆石子的游戏：SG值：0123456789101112…状态：0123456789101112…多堆石子的游戏：g(x1,x2，……，xn)=g(x1)xorg(x2）xor……g(xn)（第ｉ（１＜＝ｉ＜＝ｎ）堆石子的个数是ｘｉ。）等价转化不等价转化转化游戏例题１:ACMICPC2006AsiaRegionalContest,BeijingAFunnyStoneGameDavid玩一个石子游戏。游戏中，有n堆石子,被编号为0..n-1。两名玩家轮流取石子。每一轮游戏，每名玩家选取3堆石子i,j,k(ij,j=k,且至少有一枚石子在第i堆石子中)，从i中取出一枚石子，并向j，k中各放入一枚石子(如果j=k则向k中放入2颗石子)。最先不能取石子的人输。石堆1：石堆2：石堆3：新操作：拿走一个非0的石堆，并放入2个规模小于他的石堆(可以为0)游戏可以分解！例题三IPSC2003GotRoot?Alice&Bob在一个无向图上玩伐木游戏，无向图有唯一的根。两人轮流从图中截取一条边，将与根部相连的部分抛弃。这样，最先不能操作的人输。对于给出的无向图，Alice先行，两人都按最优策略操作,输出胜者的名字。转化成树？转化成链Nim!图转化成树树转化成链求出SG值树转化成链猜想：从末端开始进行这样的操作，将分叉的地方合并成一条链，长度为每条链的异或结果，SG值不变。简单情况：状态只有根节点一个分叉Nim!图转化成树猜想：将环上的点缩为一点，所有的边都保留，如果他的端点缩去了，那么将它的端点替换为缩成的点，SG值不变。self-loop与一条长为1的链是等价的总结：以上三种方法只作启发之用，实际应用之中，我们还不仅要掌握已知的方法，还要将其灵活地结合起来运用。解决组合游戏并不困难，重要的是拓宽知识，多做总结，灵活运用、扩展已知方法。谢谢