算法合集之《浅谈如的何解决不平等博弈问题》.pdf

IOI2009 冬令营论文 方展鹏 浅谈如何解决不平等博弈问题 广东省中山市第一中学 方展鹏 摘要 本文主要介绍如何解决一类游戏双方可选决策不相同的博弈问题。全文分为 四个部分。 第一部分：引言，通过寻找博弈问题的区别，提出需要解决的问题。 第二部分：另辟蹊径，介绍如何利用Surreal Number 解决一类不平等的组合 游戏（Partisan Combinatorial Games ）。 第三部分：回到起点，利用局面分析的办法，通过迭代、动态规划等方法解 决不平等博弈问题。 第四部分：总结全文。 关键字 不平等博弈问题 Surreal Number 局面分析 递推 迭代 目录 摘要 1 关键字 1 目录 1 正文3 一、引言3 二、另辟蹊径4 2.1 Surreal Number 介绍4 2.1.1 Surreal Number 的构造4 2.1.2 Surreal Number 的一些基本定理6 2.1.3 Surreal Number 的运算法则6 1 IOI2009 冬令营论文 方展鹏 2.2 Surreal Number 与组合游戏7 2.2.1 组合游戏的定义与表示7 2.2.2 Surreal Number 在组合游戏中的应用8 2.3 例一：Procrastination 9 题目描述9 分析 10 小结 12 三、回到起点 13 3.1 例二：Procrastination 13 题目描述 13 分析 13 小结 17 3.2 例三：The Easy Chase 17 题目描述 17 分析 17 扩展 19 四、总结20 感谢20 参考文献20 附录20 附录1 论文原题20 附录2 参考程序25 2 IOI2009 冬令营论文 方展鹏 正文 一、引言 在信息学竞赛中，博弈问题十分常见，下面就是一个例子： 引例：Green Hackenbush （经典问题） 给出n 棵竹子，高度分别为a , a … a ，玩家L 和R 打算在这些竹子上面玩 1 2 n 砍竹子游戏，规则如下： 1、两人轮流操作，玩家L 先手； 2 、对于每次操作，先选定一棵高度不为 0 的竹子，然后砍掉该竹子的某一 段，并且将与竹子底部不相连的部分也去掉； 3、最先无法进行操作的人输。 假设玩家L 和R 都