预览加载中，请您耐心等待几秒...

算法合集之《组合游戏略述——浅谈SG游戏的若干拓展及变形》.pdf

预览
1/10
2/10
3/10
4/10
5/10
6/10
7/10
8/10
9/10
10/10

亲，该文档总共24页，到这已经超出免费预览范围，如果喜欢就直接下载吧～

下载提示 文本预览

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

IOI2009中国国家集训队论文贾志豪石家庄二中 组合游戏略述 ——浅谈SG游戏的若干拓展及变形 石家庄二中贾志豪 前言 组合游戏是近几年新兴起的博弈游戏，随着张一飞学长关于组合游戏的论文 的面世，组合游戏问题开始在国内信息学竞赛这片沃土上生根发芽，与大家一起 成长、成熟、成才。最为马上要离开高中信息学舞台的高三学生，我一直希望能 为学弟学妹们留下一些我自己的心得，于是这篇论文应运而生！！！ 这篇论文的一些思想是我早在一年前节开始构思的，感谢计算机学会为我提 供这样一个舞台，能让我的论文为更多的人所知道；同时感谢在我写论文时无私 帮助过我的所有人，谢谢你们！！！ 先介绍一下论文的主要内容：第一章作为论文的理论基础，主要从欣赏的角 度引入了SG函数、游戏图、NIM游戏等概念，重点谈我对组合游戏尤其是SG函 数的体会、理解；第二章主要介绍了几种不同规则的组合游戏以及相应的应对策 略，旨在告诉读者，游戏规则变化之后，我们应该如何去分析新的规则、解决新 的模型；第三章主要介绍了几种竞赛中常见的组合模型，并将“她”们成功的转 化成了NIM模型。 鉴于这篇论文的内容较多，在这里给读者提供一些阅读建议：第一章由于篇 幅原因，并没有给出SG函数、NIM游戏解法的详细证明过程，对于刚刚接触组 合游戏的读者，建议先阅读一些关于SG函数的资料（张一飞关于博弈游戏的论 文1、王晓柯关于组合游戏的论文2就很不错），然后再从论文的第一章看起，相信 你一定会很有收获；第二、三章是论文的重头戏，如题目所言，分别谈SG游戏 的拓展和变形，对于钟情于组合游戏的读者，可以重点看一看第三章，相信一定 不会让你失望！！！ 这篇论文主要有两个特点： 基本没有例题但处处是例子。为了让读者更好的理解论文中的思想，笔 者在选题目的时候刻意将题目的背景剥掉，只剩下一个“光溜溜”的数 学模型，这样读者在阅读论文时，就不必花精力去考虑背景向模型的转 化，可以全身心去理解笔者想要传达的思想。但读者不必去担心没有地 方练习，笔者将这几年的自己做过的组合游戏题收录在了论文的附录 里。 1《由感性认识到理性认识——透析一类搏弈游戏的解答过程》，张一飞，国家集训队2002论文 2《解析一类组合游戏》，.王晓珂，国家集训队2007论文 IOI2009中国国家集训队论文贾志豪石家庄二中 每一个模型都有详细的证明。大多数人在学习信息学时存在的问题是 “知其然，不知其所以然”，因为大多数的比赛模式是只要求结果而不 要求过程。但这会使我们对一个事物“只知表皮，不知深髓”，如果将 一个我们知道的问题稍加变形的话，我们可能就不会了。这个问题在组 合游戏中体现得尤其突出。因此笔者对于文中的每一个定理都给出了证 明，希望读者对文中的思想“知其然，知其所以然”。 为了方便大家阅读，我将论文中所有的定理表述做成了“HELLOWORLD”将 所有的定义表述做成了“HELLOWORLD”，希望这样的改动能引起大家的注意和兴 趣。 IOI2009中国国家集训队论文贾志豪石家庄二中 目录 感谢……………………………………………………………………………………4 Chapter1……………………………………………………………………………5 1.1本论文讨论的范围………………………………………………………………5 1.2组合游戏中状态空间向图的转化………………………………………………6 1.3简介SG函数………………………………………………………………………6 1.4定义NIM-模型……………………………………………………………………7 Chapter2……………………………………………………………………………9 2.1走完最后一步者输——Anti-SG游戏和SJ定理………………………………9 2.2可以将一堆石子分成多堆——Multi-SG游戏………………………………14 2.3每一个可以移动的棋子都要移动——Every-SG游戏………………………14 Chapter3……………………………………………………………………………18 3.1翻硬币游戏……………………………………………………………………18 3.2无向图删边游戏………………………………………………………………19 3.2.1树的删边游戏………………………………………………………………19 3.2.2ChristmasGame(PKU3710)………………………………………………21 3.2.3无向图的删边游戏…………………………………………………………23 参考资料……………………………………………………………………………24 附录…………………………………………………………………………………24 关键字