1、 浅谈如何解决不平等博弈问题广东省中山市第一中学 方展鹏引言 给出n棵竹子，高度分别为a1, a2 an，玩家L和R在这些竹子上面进行游戏，规则如下：两人轮流操作，玩家L先手；对于每次操作，先选定一棵高度不为0的竹子，然后砍掉该竹子的某一段，并且将与竹子底部不相连的部分也去掉； 最先无法进行操作的人输。假设玩家L和R都采取最优策略，问对于给出的局面谁会获胜。Hack This引言 对于上述问题，根据The Sprague-Grundy Theorem，我们可以轻松地设计出一个时间复杂度为O(n)的算法。 详 2007 的 )().()(),.,( 2121 nn xgxgxgxxxg 引言 T
2、he Sprague-Grundy Theorem 在 题 的 对于 局面，玩家L和玩家R的可选决策都相 如 两 的可选决策不相 会 ? 我们不 在游戏规则 一 ：竹子的每一段都 上 L R，玩家L 砍 上L的段，玩家R 砍 上R的段。 上上述规则后，玩家L和玩家R的可选决策不相 。时我们The Sprague-Grundy Theorem在上述问题上也不 。 引言 currency1“的如何解决这两个玩家的可选决策fifl不相 的博弈问题，也 为不平等博弈问题Partizan Games 第一部分：如何 Surreal Number分一不平等”fl游戏 第部分：如何 规 等方法解决不平等博弈
3、问题 第部分： Surreal Number的定 一个surreal number 两个fifl”。我们 这两个fifl为fifl 与fifl 。 下，我们会将surreal number 作 L | R ， 中L fifl，R fifl。 fifl和fifl中的 也为surreal number，且fifl中不 在 x fifl中 在 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。
