1、浅谈如何解决不平等博弈问题 广东省中山市第一中学 方展鹏 引言 给出 n棵竹子，高度分别为 a1, a2 a n，玩家 L和 R在这些竹子上面进行游戏，规则如下： 两人轮流操作，玩家 L先手； 对于每次操作，先选定一棵高度不为 0的竹子，然后砍掉该竹子的某一段，并且将与竹子底部不相连的部分也去掉； 最先无法进行操作的人输。 假设玩家 L和 R都采取最优策略，问对于给出的局面谁 会获胜。 Hack This 引言 对于上述问题，根据 The Sprague-Grundy Theorem，我们可以轻松地设计出一个时间复杂度为 O(n)的算法。 详见 2007年王晓柯前辈的论文 )() . . .(
2、)(), . . .,( 2121 nn xgxgxgxxxg 引言 The Sprague-Grundy Theorem能在本题使用的前提条件 对于任意局面，玩家 L和玩家 R的可选决策都相同 如果两者的可选决策不相同会怎样 ? 我们不妨在游戏规则处再多加一条：竹子的每一段都被标上了 L或者 R，玩家 L只能砍被标上 L的段，玩家 R只能砍被标上 R的段。 加上上述规则后，玩家 L和玩家 R的可选决策就不相同了。 同时我们还发现 The Sprague-Grundy Theorem在上述问 题上也不再成立。 引言 本文所要探讨的正是如何解决这类两个玩家的 可选决策集合不相同的博弈问题，也称之
3、为不 平等博弈问题（ Partizan Games） 概览 第一部分：介绍如何利用 Surreal Number分析一类不平等组合游戏 第二部分：介绍如何通过动态规划、迭代等方法解决不平等博弈问题 第三部分：总结全文 Surreal Number的定义 一个 surreal number由两个集合组成。我们称这两个集合为“左集合”与“右集合”。 通常情况下，我们会将 surreal number写作 L | R ，其中 L表示左集合， R表示右集合。 左集合和右集合中的元素也为 surreal number，且右集合中不存在元素 x使得左集合中存在元素 y满足 x y。 的定义 对于 surreal number x = XL | XR 和 y = YL | YR ，我们称 当且仅当不存在 使得 以及不存在 使得 。 得出 的定义后，我们还可以定义 1， | -1 -1，所以令 1 | = 2， | -1 = -2。 因为 0 0 | 1 1，且 0 | 1 + 0 | 1 = 1，因此我们令 0 | 1 = 1/2。 同理我们可以得出 -1 | 0 = -1/2。
