国家集训队2009论文集从“k倍动态减法游戏

《国家集训队2009论文集从“k倍动态减法游戏》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOI2009冬令营论文从“k倍动态减法游戏”出发探究一类组合游戏问题摘要组合游戏是指，信息完全轮流操作的双人游戏。本文将从一个游戏——k倍动态减法游戏（k-baseddynamicsubtractiongame）的解答出发，讨论游戏中的一个重要分支——组合游戏，并探讨解决这一类的问题的高效方法。探索的过程力求兼顾游戏论中的普遍真理以及问题的独特性质。作为一篇信息学的论文，本文将着重讨论与组合游戏有关的相关算法和这些算法时间复杂性分析，而不是游戏论中的一些经典的理论、典型的游戏实例或者一些存在性的证明。“k倍动

2、态减法游戏”在k为一般正实数的情况，在2002年的国家集训队3论文中已经给出O(S)的算法，本文将在第4．1节给出一个优化到O(S)的算法。“Nim积”运算是利用SG函数解决游戏论问题的必要工具之一。本文将在2第4．4．5节给出一个O(logx)的计算“Nim积”的算法。2008年的BOI（BalticOlympiadinInformatics）中knight一题就是游戏论问3题，官方解答给出了O(n)的算法，但没有给出算法时间复杂度的证明。本文在3第5章提出了对这个O(n)的上界的质疑，并举出了质疑的确实依据

3、，举出反例证明了官方解答时间复杂度估计的错误之处。同时，本文经过对算法进一步优化，2得到了一个O(n)的算法。上面这些内容都是原创的独立研究成果。关键字NP状态、单调性、SG函数、“Nim和”、“Nim积”、对称性分析、贪心分析、时间复杂度分析共44页-第1页NOI2009冬令营论文从“k倍动态减法游戏”出发探究一类组合游戏问题一．引言1．1．组合游戏的定义“游戏”这个词包含的范围很广，像“石头剪刀布”“斗地主”“军旗”“象棋”“Nim游戏”等等。但是，一个游戏，作为组合游戏，必须具有以下特征：1：双人游戏。2

4、：双方轮流操作。即，组合游戏不包含双方同时进行的操作。3：在游戏中的任意一个时刻，当前玩家可以选择的操作，是一个有限的确定的集合。即，组合游戏不包含随机化的操作。4：信息完全。即，在游戏中的任意时刻，游戏中的任意一方都知道游戏的初始状态，以及从“游戏开始”到“当前”为止的双方的所有的历史操作，没有任何的保密。5：游戏中的某一些状态被规定为“胜利终止状态”，到达这些状态的玩家获胜（即对方把胜利终止状态交给你的话，你就输了）；某一些状态被规定为“失败终止状态”，到达这些状态的玩家失败。本文只讨论，有限次操作后能分出

5、胜负的那一类组合游戏，这一类游戏中将没有“平局”的情况。由于平局的情况是复杂的，本文不讨论。例如，“中国象棋”“围棋”都是经典的组合游戏，但不属于本文讨论范围。所以，像“推箱子”这样的单人游戏，不属于组合游戏；像“石头剪刀布”这样包含同时操作的游戏，不属于组合游戏；像“飞行棋”“大富翁”这样包含掷色子的随机行为的游戏不属于组合游戏；像“斗地主”“军旗”这样的对自己当前状态保密的游戏，不属于组合游戏。所以总结起来，对于一个组合游戏，一般可以用f：XP(x)来描述游戏规则。其中X表示状态集，P(x)表示X的子集簇

6、。f(x)就表示玩家可以从x出发一步操作后到达的状态的集合。我们称任一个yf(x)，y是x的一个后继。也就是说，本文讨论的组合游戏可以被理解成一个有向无环图G=(V,E)，图的点集V=X，边集E=(xy

7、yf(x))。1．2．组合游戏需要解决的问题由于组合游戏是一个双方博弈的游戏，所以对于一个游戏的研究一般需要回共44页-第2页NOI2009冬令营论文从“k倍动态减法游戏”出发探究一类组合游戏问题答两个问题：谁有必胜策略？必胜策略是什么？而在信息竞赛学的问题中需要解决的问题，也与此相对应，分三个层次：（1）

8、判断谁有必胜策略；（2）寻找单回合的必胜选择；（3）维护多回合的必胜选择（交互题涉及）。1．3．衡量解决组合游戏的算法的时间的尺度作为信息学的问题，算法的时间效率至关重要。对于一般的信息学问题，算法的时间复杂度是依据程序运行时间相对于输入文件规模增长的增长来衡量的。这一衡量尺度对于游戏论问题当然是适用的，但是对于游戏论问题，特别是涉及到前面提出的第三类交互式问题的时候，本文也会采用下面的衡量方式。首先，所有当前状态的直接或间接的后继状态的数量S(x)、描述当前状态所必需的数据规模D(x)、最坏情况下结束游戏的回

9、合数T(x)都可以衡量一个游戏的复杂程度，因此程序运行时间的增长与此三者之一的增长速度的关系，也可以衡量一个算法的时间复杂度的尺度。其次，一方面由于对当前状态的描述必须能是的当前状态能区别于其它状态（特别的，包括他的所有直接的或间接的后继状态），所以D(x)(logS(x))。另一方面，由于表达游戏的图是有向无环的，所以对任意yf(x)都有S(x)S(y)1，所以S(x)