国家集训队2009论文集组合游戏略述——浅谈

《国家集训队2009论文集组合游戏略述——浅谈》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、IOI2009中国国家集训队论文贾志豪石家庄二中组合游戏略述——浅谈SG游戏的若干拓展及变形石家庄二中贾志豪前言组合游戏是近几年新兴起的博弈游戏，随着张一飞学长关于组合游戏的论文的面世，组合游戏问题开始在国内信息学竞赛这片沃土上生根发芽，与大家一起成长、成熟、成才。最为马上要离开高中信息学舞台的高三学生，我一直希望能为学弟学妹们留下一些我自己的心得，于是这篇论文应运而生！！！这篇论文的一些思想是我早在一年前节开始构思的，感谢计算机学会为我提供这样一个舞台，能让我的论文为更多的人所知道；同时感谢在我写论文时无私帮助过我的所有人

2、，谢谢你们！！！先介绍一下论文的主要内容：第一章作为论文的理论基础，主要从欣赏的角度引入了SG函数、游戏图、NIM游戏等概念，重点谈我对组合游戏尤其是SG函数的体会、理解；第二章主要介绍了几种不同规则的组合游戏以及相应的应对策略，旨在告诉读者，游戏规则变化之后，我们应该如何去分析新的规则、解决新的模型；第三章主要介绍了几种竞赛中常见的组合模型，并将“她”们成功的转化成了NIM模型。鉴于这篇论文的内容较多，在这里给读者提供一些阅读建议：第一章由于篇幅原因，并没有给出SG函数、NIM游戏解法的详细证明过程，对于刚刚接触组合游戏的

3、读者，建议先阅读一些关于SG函数的资料（张一飞关于博弈游戏的论12文、王晓柯关于组合游戏的论文就很不错），然后再从论文的第一章看起，相信你一定会很有收获；第二、三章是论文的重头戏，如题目所言，分别谈SG游戏的拓展和变形，对于钟情于组合游戏的读者，可以重点看一看第三章，相信一定不会让你失望！！！这篇论文主要有两个特点：基本没有例题但处处是例子。为了让读者更好的理解论文中的思想，笔者在选题目的时候刻意将题目的背景剥掉，只剩下一个“光溜溜”的数学模型，这样读者在阅读论文时，就不必花精力去考虑背景向模型的转化，可以全身心去理解笔者

4、想要传达的思想。但读者不必去担心没有地方练习，笔者将这几年的自己做过的组合游戏题收录在了论文的附录里。1《由感性认识到理性认识——透析一类搏弈游戏的解答过程》，张一飞，国家集训队2002论文2《解析一类组合游戏》，.王晓珂，国家集训队2007论文第1页共24页IOI2009中国国家集训队论文贾志豪石家庄二中每一个模型都有详细的证明。大多数人在学习信息学时存在的问题是“知其然，不知其所以然”，因为大多数的比赛模式是只要求结果而不要求过程。但这会使我们对一个事物“只知表皮，不知深髓”，如果将一个我们知道的问题稍加变形的话，我们

5、可能就不会了。这个问题在组合游戏中体现得尤其突出。因此笔者对于文中的每一个定理都给出了证明，希望读者对文中的思想“知其然，知其所以然”。为了方便大家阅读，我将论文中所有的定理表述做成了“HELLOWORLD”将所有的定义表述做成了“HELLOWORLD”，希望这样的改动能引起大家的注意和兴趣。第2页共24页IOI2009中国国家集训队论文贾志豪石家庄二中目录感谢……………………………………………………………………………………4Chapter1……………………………………………………………………………51.1本论文讨论的范围…

6、……………………………………………………………51.2组合游戏中状态空间向图的转化………………………………………………61.3简介SG函数………………………………………………………………………61.4定义NIM-模型……………………………………………………………………7Chapter2……………………………………………………………………………92.1走完最后一步者输——Anti-SG游戏和SJ定理………………………………92.2可以将一堆石子分成多堆——Multi-SG游戏………………………………142.3每一个可以移动的棋

7、子都要移动——Every-SG游戏………………………14Chapter3……………………………………………………………………………183.1翻硬币游戏……………………………………………………………………183.2无向图删边游戏………………………………………………………………193.2.1树的删边游戏………………………………………………………………193.2.2ChristmasGame(PKU3710)………………………………………………213.2.3无向图的删边游戏…………………………………………………………23参考资料…

8、…………………………………………………………………………24附录…………………………………………………………………………………24关键字SG函数NIM模型Anti游戏Multi游戏Every游戏翻硬币游戏删边游戏证明拓展第3页共24页IOI2009中国国家集训队论文贾志豪石家庄二中感谢谨以