当前位置:首页 >> 其它课程 >>

组合游戏的简单分析与探讨 信息竞赛论文


【关键字】 组合游戏 游戏的和 nim 和 Sprague-Grundy 函数 【摘要】 本文的主要内容是分析组合游戏的方法。 在介绍这些方法之前,会先介绍相关的概念 对于每一种方法,本文附有相应的例题帮助理解。 【组合游戏与相关的概念】 1.组合游戏 游戏是一个常见的概念, 通常它是指娱乐性质的游戏。 不过它也可以有一些其它的内涵 比如竞争、寻找最优,像商业竞争、外交谈

判就是这样的意义下的游戏,尽管不那么有趣、 不过战争也可以算作是游戏。 在 OI 中有许多题目从游戏中提出问题。Alice & Bob 就因此出了名。在这些游戏中 组合游戏占了很大一部分, 组合游戏其实对我们来说并不陌生, 它是是满足这样一些条件的 游戏: 1) 游戏有2名参与者。 2) 游戏过程中任意时刻有确定的状态。 3) 参与者操作时可以的操作时将游戏从当前状态改变为另一状态, 规则规定了在 任意一状态时,可以到达的状态集合。 4) 参与者轮流进行操作。 5) 在游戏出于某状态,当前参与者不能进行操作时,游戏结束。此时参照规则决 定胜负。 6) 无论参与者做出怎样的操作游戏在有限部数之内结束(没有平局)。 7) 参与者拥有游戏本身,和游戏过程的所有信息,比如规则、以前自己和对手的 操作。 本文讨论的组合游戏还有一个公平性的限制、即2名参与者的操作规则 是相同的。 组合游戏也可以用一个有向图来表示 G=(X, F)X 为游戏的状态集合 F(X)为 X 可以到 达的状态集合,而结束状态均宣布当前参与者失败。 如果原游戏的结束状态为胜利,那么有必要将图改一下适应题目规则。 组合游戏必然是一个无环图(无平局)。 2.必胜、必败状态 在组合游戏中必胜状态定义为当前玩家有策略能使无论对手做什么操作也可以保证自 己胜利的状态。相反,如果之前操作的玩家能够保证胜利、则它是必败的状态 在组合游戏中一个状态如果不是必败状态就是必胜状态,这是显而易见的。通常我们 分析做和游戏的目的就是判断一个状态为必胜还是必败,如果必胜,则找出必胜策略。完成 这一点仅凭以上定义是不够的,而以下的性质(可以用来判定一组划分是否为必败状态与必 胜状态的划分)则明确的指出了一种递推的方法。 1) 结束状态的性质由规则决定。 2) 一个非结束状态,如果它能到达任何必败状态,那么它是必胜状态,否则它就 是必败状态。 尽管这对每个组合游戏都适用,但它可不是万能的,有时一个游戏的状 -1- 态非常多,计算机无法处理,这时你就得借用别的方法了。 3.Sprague-Grundy 函数 它是定义在组合游戏状态上的函数,用 g (X)表示 X 状态的函数值。它的定如下: g (X)= min{n| n∈N ,n≠ for y∈F(x)} 形象的说就是 X 的函数值为与 X 所能到达的任意点函数值不同的最小自然数。 我想细心的读者已经发现 g (X)=0当且仅当 X 为必败状态,这用其定义很容易验证: 1) 当 X 为结束状态时,由于 g (X)=0它是必败状态。 2) 当 X 不是结束状态时,如果它能到达必败状态,那么 g (X)>0,X 是必胜状 态。 3) 如果 X 不是结束状态且它到达的所有状态未必败状态, 那么 g (X)=0它是必败 状态。 这个冗长的定义,看上去毫无意义,因为直接判断一个状态的性质比使 用这个函数要方便多了。但实际上与感觉的相反,这确是许多方法的基石,他的一些性质, 使我们分析组合游戏的重要工具。 【概述】 组合游戏是一直是一个有趣的话题,有了电脑,我们可以更轻松的分析这些游戏。这些

相关文章:
科技竞赛论文
科技竞赛论文_营销/活动策划_计划/解决方案_实用文档...学生只精通上网聊天,精通网络游戏,估计也不是学校的...关的信息,经过筛选、组合,制作成适合学生年龄特点、...
MathorCup竞赛优秀论文
这样分析,于是 2048 游戏就可化成建立一个模型解决信息对称的双人对弈问 题。 ...2006年研究生数模竞赛C题... 22页 1下载券 2014MathorCup优秀论文B... 18...
历届北京高中数学知识应用竞赛获奖论文题目
历届北京高中数学知识应用竞赛获奖论文题目 PP 快看!...浅谈数学建模中的比例分析法 2 一等奖 电脑游戏中的...商品组合陈列对销售的影响 关于城市快速路灯的设计...
参考1-游戏类毕业论文
参考1-游戏类毕业论文_工学_高等教育_教育专区。浙江...信息学院 专业名称 计算机科学与技术 班 级 06 ...分析了近年来国内外小游戏领域的研究现状发展趋 势...
2016年电子竞赛简易电子秤论文_图文
2016年电子竞赛简易电子秤论文_信息与通信_工程科技_专业资料。2015 年全国大学...优点:输出信号频率等于两输入信号频率之、差或其他组合的电路。通常由非线 性...
关于游戏的毕业论文正文(全)
毕业论文 我国网络游戏产业发展现状及对策研究 我国...2004年9月上旬举行的网络 游戏年会上,信息产业张淇...国网络游戏产业发展的机遇与问题进行了系列分析, 并...
国家集训队2007论文集2.王晓珂《解析一类组
国家集训队2007论文集国家集训队2007论文集隐藏>> 组合游戏的简单分析—四川省绵阳...分析这些游戏.这些 游戏渐渐进入了信息竞赛,掌握合理分析组合游戏的方法的必要...
全国电子设计大赛一等奖论文
全国电子设计大赛一等奖论文_电子/电路_工程科技_专业...或者由多个具有最小公倍数的频率 组合的多频信号...方便简单.软件流程图如下: 主流程图 周期性分析和...
2014Ti杯电子竞赛论文
2014Ti杯电子竞赛论文_电子/电路_工程科技_专业资料...根据以上分析结果,选用 STC12C5A60S2 为核心的微...构成简单的驱动电路,整个电路的 驱动能力大,通过调节...
J2ME手机游戏设计分析论文
J2ME手机游戏设计分析论文_管理学_高等教育_教育专区。移动电话应用程序蓝牙对战五子...与信息工程学院 xxx 班 仉晓东 2006152xxxx 指导教师 xxx 副教授摘要 信息技术...
更多相关标签:
论文文献探讨怎么写 | 数学竞赛中的组合问题 | 排列组合竞赛题 | 简单机械竞赛题 | 广告创意策略探讨论文 | 商誉会计处理探讨论文 | 四轮定位的探讨论文 | 数学竞赛组合 |