算法合集之《解析一类组合游戏》

《算法合集之《解析一类组合游戏》》由会员分享，可在线阅读，更多相关《算法合集之《解析一类组合游戏》（15页珍藏版）》请在金锄头文库上搜索。

1、 组合游戏的简单分析四川省绵阳南山中学 王晓珂【关键字】组合游戏 游戏的和 nim 和 Sprague-Grundy 函数【摘要】本文的主要内容是分析组合游戏的方法。 在介绍这些方法之前，会先介绍相关的概念 对于每一种方法,本文附有相应的例题帮助理解。 【组合游戏与相关的概念】1组合游戏组合游戏游戏是一个常见的概念，通常它是指娱乐性质的游戏。不过它也可以有一些其它的内 涵比如竞争、寻找最优，像商业竞争、外交谈判就是这样的意义下的游戏，尽管不那么有 趣、不过战争也可以算作是游戏。 在 OI 中有许多题目从游戏中提出问题。Alice g(i) = minn N | n g (p,q) for n

2、p 0 且 n q 0。 应用以上结论，我们可以递推求得子游戏任意状态的 SG 函数值。用 SG 定理可以求得 和游戏的任意状态的 SG 函数值。SG=0,David 可以保证他的胜利，否则就不行。至于策略， 只要操作之后留下的状态 SG 值为 0 就行了。 时间复杂度分析： 以上算法包含 O (n)个 SG 值的计算，计算每一个的时间最多为 O(n2)，判断必胜状态 需要 O ( Si )，寻找最优策略需要 O (n3)的时间，综上,该算法的时间复杂度为 O(n3+Si)。【归纳】归纳也是分析组合游戏的一种常见方法。通过归纳，我们可以在很短的时间内完成对 许多状态的分析。例如对于 nim 游

3、戏的 1 堆情形，我们在递推的简单基础上，我们可以归 纳得出规模为 x 的状态，其 SG 函数值为 x，x 必败当且仅当 x=0。由于归纳结果往往简单 得出人意料，所以我想读者们在自己分析组合游戏的时候一定会自然而然地用上这种方法。归纳的对象除了我们常见的必败状态还可以是刚刚介绍的 SG 函数。 通常我们做出归纳的基础都是游戏中的简单情形的特点。不过，游戏中简单的情形给 予我们的启示是有限的。有时，我们需要在经验而不是事实的基础上做出猜想。许多游戏 与经典游戏有着种种相似而又不完全相同，找出其模型上的相似之处，进行合理的猜想有 时比从原始数据上进行归纳更直接有效。 例题 2： staircas

4、e nim 经典组合游戏游戏开始时有许多硬币任意分布在楼梯上，共 n 阶楼梯从地面由下向上编号为 0 到 n。游戏者在每次操作时可以将楼梯 j(1=j=n)上的任意多但至少一个硬币移动到楼梯 j-1 上。游戏者轮流操作，将最后一枚硬币移至地上的人获胜。分析： 这个问题与 nim 游戏的区别在于移走的硬币不是被扔掉而是被放进了另一堆硬币之 中，考虑能否将这一部分楼梯排除考虑范围。奇数号楼梯只能将硬币扔到偶数号楼梯之中， 同样偶数号楼梯上的硬币也只会被扔上奇数号楼梯。只考虑奇数号楼梯 nim，若偶数楼梯 只作容器，那么游戏变为 nim。当偶数号楼梯上的硬币可以将硬币移出时，我们是不是仍然可以用 n

5、im 的方法判断必败状态？ 将奇数台阶的硬币数 nim 和为 0 称作条件 A,结束状态满足条件 A；任何满足条件 A 的 状态都到达满足条件 A 的状态；任何不满足条件 A 的状态都可以到达满足条件 A 的状态 (nim)。因此一个状态为必败状态当且仅当它满足条件 A。 例题 3 翻转硬币(经典组合游戏) 在一条直线上排列着一行硬币，有的正面朝上、有的背面朝上。2 名游戏者轮流对硬 币进行翻转。翻转时，先选一枚正面朝上的硬币翻转，然后，如果愿意，可以从这枚硬币 的左边选取一枚硬币翻转。最后翻转使所有硬币反面朝上的玩家胜利。图 1例如图 1 所示的状态，将 2 和 12 同时翻转就构成一个合法

6、的操作。 分析： 基于转化的思想，如果将位置 i 上的 H 看作一堆规模为 i 的石子，我们就能看到游戏 与 nim 的相似点。不过有许多 nim 中的合法操作在这个游戏中是无法实现的，比如图一状 态中，我们就无法从一堆规模为 10 的石子中取出其中的 5 个。不过我们将 10 与 5 同时翻 转，所得到的状态。对应的 nim 状态 SG 值与从 10 中取 5 是相同的。因此我们猜想这个游 戏的状态 SG 函数值与对应的 nim 相同。由于事实上虽然这个游戏无法实现 nim 的所有操作， 但它的状态所能到达的状态 SG 函数值集合与对应的 nim 游戏状态相同。因此，它的状态 SG 函数值与

7、对应 nim 相同。 【转化游戏】现实中有许多游戏在一定的形式的掩饰下，隐藏了许多我们分析所必要的特点，有的 游戏状态本身包含多种元素和关系异常复杂。面对这些令我们无法下手的情况时，我们应 该想到对游戏的转化。本文介绍 2 种方法，一是转化游戏的形式(等价转化)，而是对状态进行一定条件下的 不等价转化。一、等价转化同一个组合游戏往往有不同表现形式，比如例题一中所提到的 take &break 游戏就可 以转换成形式截然不同的石子游戏(只要将例题一稍加改变就能与 take &break 游戏等价)。同一个游戏，从不同的角度，我们能够观察到的性质也不同。比如例 1 在原型下很难体现 其游戏的和的本

8、质，经过巧妙的转化后这一性质就浮出水面了。 例题 4 ：POI2003/2004 stage I Game 该游戏在 m*1 的平板上进行。平板的一些单位格上放有一枚硬币。两名游戏者轮流 移动硬币。移动时，选取一枚硬币，将它放在右边最近的空格里，如果不存在，则将它扔 掉，扔掉最后一枚硬币的人获胜图 2在图一表示的状态下，当千玩家可以将 2 的硬币移动到 4，3 到 4，6 到 7。 对于给出的状态输出先行者能保证胜利的第一步策略数。 输入第一行输入 m,n 。m 如题是般的大小，n 为硬币的数量。第二行 n 个数分别表示每一 枚硬币所在的位置。 输出进一行，保证先行者胜利的策略数。 分析： 首

9、先每一枚硬币都相互影响，因此很难将其看作任何子游戏的和。状态繁多、关系 复杂很难直接找到他的必败状态。考虑转换该游戏，经过多次尝试后可以这样转化一下， 将任意空格与其左边最近的空格之间的空间看作一阶楼梯，最后一个空格的右边看作一个 地面，每段空间中的硬币数为楼梯数那么这个游戏就与 staircase nim 游戏完全等价了。 小结： 如果，我们不能将例二成功转化，那么对它的分析过程可以让人非常沮丧 。面对组 合游戏，从不同的角度来观察(转化)它应该作为我们的基本手段之一。我们最熟悉取石子/ 硬币这类游戏，它可以作为我们的首选。无论怎样转化，我们都要实现对游戏本质和特点 的挖掘。二、不等价的转化

10、二、不等价的转化我们分析组合游戏，只需要 SG 函数值就可以完成，将游戏原汁原味地转化，保持游 戏本质不变是不是有些浪费呢？ 由于，只需要 SG 函数值，我们可以期望在保证状态 SG 函数值不变时，将复杂状态 化进行不等价的转化，化简到最朴素的状态，最后轻松解决。 例题 5IPSC 2003 Got Root?Alice & Bob 有一天发现了一株奇怪的灌木、他的枝分叉之后又可以汇合、更奇特的 是来自不同的不仅是同一点的分叉可以汇合、即使分叉点相差很远、两根枝条仍然可以生 长到一起(组织连在一块儿了)。在我们看来他可以抽象为一个无向图。其中有唯一结点是 根。 他们认为这是用来玩游戏的绝佳材料

11、。于是他们打算在这棵树上玩伐木游戏，规则 如下： 1.两人轮流从灌木上截下枝条(图上的边)，每截下一根枝条就将与根不再相连的部 分去掉。 2.截去最后一根枝条的人获胜 Alice 先手。 对于给出的无向图输出输出胜利的人的名字。 分析： 既然要转化、那么我们就要有一个目标，一个更简单的状态。我们先考虑树的情 形是否会更简单。经过初步分析以后树形的状态也难以得到直接的结论、它还需要进一步的简化。那么再来考虑图构成一条长链的情况。这时，终于有了令人满意的结果，问 题变为了典型的单堆 nim，可以直接求得 SG 函数值。 那么怎样将图转化成链呢？我们分两步进行，先把图转化成树，在将树转化成链， 整个

12、过程保持状态的 SG 函数值不变。 先做第二步，在只有一个分叉点时，这是一个简单的 nim，可以转化为一个长为每 根单链异或运算结果的单链。在更复杂一些的树上，猜想从末端开始进行这样的操作， 将分叉的地方合并成一条链，长度为每条链的异或运算结果，不会改变整个状态的 SG 值。 这种合并方式可以推广为更一般的结论：对于任意 2 棵树 H1,H2 如果他们玩伐木游戏 的 SG 值相同，则将他们接到两个相同图的对应点后，产生的新图 SG 值是一样的。 它的证明对于证明 2 个状态的 SG 函数值相通这样的命题具有一般性，令产生的 2 个 图为 G1,和 G2。先证明 G1+G2 后行者有必胜策略：p

13、layer1 截下的是不是 H1 或 H2 的边， player2 截下相同的边；如果 player1 截下的是 H1 或 H2 的边，则 player2 截下 H1、H2 中 SG 值较高一个的某一边让 SG 相同。因此 g(G1+G2)=0 即 g(G1)=g(G2)。 接下来要将图转化成树。 图与树的区别在于图有环而树没有，把图转化成树最朴素的思想就是将图中的环一 次缩成单个的点，那么相关的边怎么处理？图中的边是游戏操作的对象，我们最好将它们 全都留下来，至于端点，如果已经被合并，那么边就变成一个到自己的环。 我们希望这样的转化，可以保持状态的 SG 函数值。这个结论证明比较长，这里就不

14、 再证明，只附在附录中。 不过，这样操作最终会留下大量的 self-loop，不难发现，一个 self-loop，和一条长为 1 的单链是等价的，这样，图到树的转化，我们就有了理论依据。 算法： 有了以上的结论，我们可以设计算法将图在 SG 值不变的条件下转化成一条单链。我 们知道，在无向图中，有这样一个划分，每一个集合内删除任意一条边都能保持连通，集 合之间则存在桥。每一个集合，可以通过缩环的操作收缩成一个点与成堆的自己到自己的 边。我们的算法可以将图用 O(e)的时间对图进行这样的收缩，再用 O(n)的时间完成到树和 链的转化，整个过程保持状态 SG 函数值不变。完成转化后，问题就很容易解

15、决了。 该算法时间复杂度为 O(e)。【小结】三种方法一一讲述之后，笔者希望读者对组合游戏和它的的分析过程有了比较全面的 认识，在竞赛中能灵活地运用这些方法。 组合游戏包含的内容很多，这些方法有许多问题是无法解决的，感兴趣的读者不要拘 泥于本文的范围，可以从各种相关的书籍中更多地了解组合游戏。 解决组合游戏并不困难，重要的是拓宽知识，多做总结，灵活运用、扩展已知方法。 【感谢】感谢叶诗富老师，刘汝佳老师对我的帮助和指导。 感谢何森与古楠同学给我提出的宝贵建议【参考资料】GameGame TheoryTheory fergusonferguson 【附录】一、 融合原则的证明(摘自 ISPC 官

16、方网站,其中所提到的colon principle 是指把树转化为链所用到的结论)Proof of the Fusion Principle. Suppose the contrary. Take the counterexample with the least number of edges, if there are more such counterexamples, choose the one with the least number of vertices. Call this graph G. We can deduce the following facts about G: For arbitrary vertices x, y on some cycle in G if we fuse x and y, SG value of G changes (otherwise we would get a smaller counterexample). When we remove the ve