tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 设计/艺术 >>

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


世爵平台 http://www.15es.com/ wenku1

组合游戏略述
——浅谈组合游戏的若干拓展及变形
石家庄二中 北校区 高三18班 贾志豪

内容概述content introduction
? 组合游戏的规则拓展
?走完最后一步者输——Anti-SG游戏和SJ定理 ?可以将一堆石子分成多堆——Multi-SG游戏 ?每一个可移动的棋子都要移动——Every-SG游戏

? 组合游戏的模型变形
?翻硬币游戏
?无向图删边游戏

2013-12-6

第2页

石家庄二中 贾志豪

Every-SG游戏
? 何为Every-SG游戏???
?有N个单一游戏,游戏者轮流进行决策; ?游戏者的决策必须满足:对于所有还没有结束的

单一游戏,游戏者必须对该单一游戏进行一步操 作; ?无路可走者输
怎么办?
2013-12-6

怎么办??

怎么办???
第3页

石家庄二中 贾志豪

Every-SG游戏
? 贪心策略:
?对于某一个单一游戏,如果当前是先

手必胜局,那么先手不会放弃游戏的 胜利!!! ?那么,游戏者需要做的,就是让自己 可以取得胜利的游戏尽可能长的玩下 去,让自己不能取得胜利的游戏尽可 能短的玩下去!!!

2013-12-6

第4页

石家庄二中 贾志豪

Every-SG游戏
? 解决方法:
?对于SG值为0的点,我们需要知道最少几步能将

游戏带入终止状态 ; ?对于SG值不为0的点,我们需要知道最多几步游 戏会被带入终止状态 ; ?以上两个值,我们都用step来表示
0 v为终止状态 ? ? step(v) ? ?max ?step(u ) ? ? 1 SG(v) ? 0 ? u为v的后继状态 ? SG(u ) ? 0 ? min ?step(u ) ? ? 1 SG(v) ? 0 ? u为v的后继状态 ?
2013-12-6 第5页 石家庄二中 贾志豪

Every-SG游戏
? 结论:
?先手必胜当且仅当step值最大的单一游戏为先手

必胜游戏
? 思考:
?step值最大的既有先手必胜游戏,又有先手必败

游戏时,是否意味着平局???

所有先手必胜的游戏的step值为奇数! 所有先手必败的游戏的step值为偶数!
2013-12-6 第6页 石家庄二中 贾志豪

Every-SG游戏
? 发现宝藏(长与短的博弈)
? 一般的组合游戏只有输与赢的博弈; ?而Every-SG游戏又增加了长与短的博弈,这使得

Every-SG游戏更有嚼头,更有味道

输 赢 长 短
2013-12-6 第7页 石家庄二中 贾志豪

Cutting Edges游戏
? 退化版:
?给出一个有N个点的树,有一个点作为树的根节

点。 ?游戏者轮流从树中删去边,删去一条边后,不与 根节点相连的部分将被移走。 ?谁无边可删谁输
如何做?
2013-12-6

如何做??

如何做???
第8页

石家庄二中 贾志豪

Cutting Edges游戏
? 从树结构入手??
?树结构是一种特殊的拓扑结构

? 从最简单的例子入手??
?根节点只有一个分支

2013-12-6

第9页

石家庄二中 贾志豪

Cutting Edges游戏
?考虑:已知左图的SG值,如何求右图的SG值

G’ G’
根节点

中间节点

G’图 由特殊例子给出猜想: G图 SG( G )=SG( G’ )+1
2013-12-6 第10页

根节点

石家庄二中 贾志豪

Cutting Edges游戏
? 证明猜想(数学归纳法)
?即证:它的后继状态的SG值为0

到SG(G')的所有值; ?以树中节点个数作为阶段; ?一个节点和两个节点显然成立; ?假设N个节点时成立,
?情况一:若去掉与根节点相连的边

G’

中间节点

根节点

G图
2013-12-6 第11页 石家庄二中 贾志豪

Cutting Edges游戏
?情况一:若去掉与根节点相连的边

G’
中间节点

G’
中间节点

根节点

根节点

SG值为0
2013-12-6 第12页 石家庄二中 贾志豪

Cutting Edges游戏
? 证明猜想(数学归纳法)
?以树中节点个数作为阶段; ?一个节点和两个节点显然成立; ?假设N个节点时成立, ?情况一:若去掉与根节点相连的边
?情况二:若去掉G’中的边

2013-12-6

第13页

石家庄二中 贾志豪

Cutting Edges游戏
?情况二:若去掉G’中的边

G’
中间节点

G’
中间节点

根节点

根节点

SG值不确定
2013-12-6 第14页 石家庄二中 贾志豪

Cutting Edges游戏
?考虑左图的SG值意味着什么??

G’
G’
根节点

定理:SG(G)=SG(G’)+1
根节点

中间节点

至多有N个点
由归纳假设

至多有N-1个点

SG值为0到SG( G’ )-1, 取不到SG( G’ ) 2013-12-6

SG值为1到SG(G’ ),取不 到SG(G’ )+1 贾志豪 石家庄二中 第15页

Cutting Edges游戏
?更复杂的情况

G’2 G’1 G’T
根节点
第16页 石家庄二中 贾志豪

2013-12-6

Cutting Edges游戏
? 根据树结构的拓扑性
? 试着去对G图进行拆分
?拆法一(一般树形结构拆法)

G’2 G’1 G’T

G’1

G’2



G’T

2013-12-6

第17页

石家庄二中 贾志豪

Cutting Edges游戏
? 试着去对G图进行拆分
?拆法二(很大胆的尝试)

G’2 G’1 G’T

G’1

G’2



G’T

2013-12-6

第18页

石家庄二中 贾志豪

Cutting Edges游戏
完美在哪了??? ? 哦。。。 ? 对应NIM取石子模型!!!
?

G’2 G’1 G’T

G’1

G’2



G’T

SG(G) ? (SG(G1 ' ) ? 1) ? ...... ? (SG(GT ' ) ? 1)
2013-12-6 第19页 石家庄二中 贾志豪

Say Goodbye

2013-12-6

第20页

石家庄二中 贾志豪

Cutting Edges游戏
? 稍加拓展:
?A和B轮流从图中删边,删去一条边后,不与根

节点相连的部分将被移走。A为先手。 ?图是通过从基础树中加一些边得到的。 ?所有形成的环保证不共用边,且只与基础树有一 个公共点。
不要慌!
2013-12-6

不要慌!!

不要慌!!!
第21页

石家庄二中 贾志豪

Cutting Edges游戏
? 环的处理成为关键
? 惊人发现,
?任何奇环的SG值为1

根节点
2013-12-6 第22页

根节点
石家庄二中 贾志豪

Cutting Edges游戏
? 环的处理成为关键
? 惊人发现,
?任何奇环的SG值为1 ?任何偶环的SG值为0

根节点
2013-12-6 第23页

根节点
石家庄二中 贾志豪

Cutting Edges游戏
? 环的处理成为关键
? 惊人发现,
?任何奇环的SG值为1 ?任何偶环的SG值为0

? 策略
?将偶环删去,将奇环替换成一条边!!!

2013-12-6

第24页

石家庄二中 贾志豪

Cutting Edges游戏
? 环的处理成为关键
? 惊人发现,
?任何奇环的SG值为1 ?任何偶环的SG值为0

? 策略
?将偶环删去,将奇环替换成一条边!!!

2013-12-6

第25页

石家庄二中 贾志豪

Cutting Edges游戏
? 环的处理成为关键
? 惊人发现,
?任何奇环的SG值为1 ?任何偶环的SG值为0

? 策略
?将偶环删去,将奇环替换成一条边!!!

2013-12-6

第26页

石家庄二中 贾志豪

Say Goodbye

2013-12-6

第27页

石家庄二中 贾志豪

Cutting Edges游戏
? 再次拓展
?一个无相联通图,有一个点作为图的根。 ?游戏者轮流从图中删去边,删去一条边后,不与

根节点相连的部分将被移走。
? 怎么办?

好难!
2013-12-6

好难!!

好难!!!
第28页 石家庄二中 贾志豪

Cutting Edges游戏
? 考虑上题给出的提示
?将环处理掉即可

? 时间原因,直接给出方法。

2013-12-6

第29页

石家庄二中 贾志豪

Cutting Edges游戏
? 对于偶环

G’1

G’2

G’6

G’3

G’5
2013-12-6 第30页

G’4
石家庄二中 贾志豪

Cutting Edges游戏
? 对于偶环

G’1

G’2 G’3

G’6 G’5
2013-12-6 第31页

G’4
石家庄二中 贾志豪

Cutting Edges游戏
? 对于奇环

G’1

G’2

G’3 G’5 G’4

2013-12-6

第32页

石家庄二中 贾志豪

Cutting Edges游戏
? 对于奇环

G’2 G’1 G’3 G’5

G’4
石家庄二中 贾志豪

2013-12-6

第33页

Say Goodbye

2013-12-6

第34页

石家庄二中 贾志豪


推荐相关:

国家集训队2013论文集组合游戏略述浅谈_图文.ppt

国家集训队2013论文集组合游戏略述浅谈 - 世爵平台 http://www


国家集训队论文:组合游戏略述浅谈SG游戏的若干拓展....ppt

国家集训队论文:组合游戏略述浅谈SG游戏的若干拓展及变形 - 组合游戏略述 浅谈组合游戏的若干拓展及变形 石家庄二中 北校区 高三18班 贾志豪 内容概述...


组合游戏略述浅谈SG游戏的若干拓展及变形.pdf

组合游戏略述浅谈SG游戏的若干拓展及变形 - IOI2009 中国国家集训队论文 贾志豪 石家庄二中 组合游戏略述 浅谈 SG 游戏的若干拓展及变形 石家庄二中 ...


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

IOI2009 中国国家集训队论文 贾志豪 石家庄二中 组合游戏略述 浅谈 SG 游戏的若干拓展及变形石家庄二中 贾志豪 前言组合游戏是近几年新兴起的博弈游戏, 随着...


国家集训队论文分类整理.pdf

组合游戏略述浅谈 SG 游戏的若干拓展及变形》 数位问题 动态统计 组合...国家集训队2009论文集数... 22页 免费 2013集训队论文集 137页 5下载券 ...


国家集训队论文分类.xls

国家集训队论文分类_计算机软件及应用_IT/计算机_专业资料。ACM ...《组合游戏略述浅谈SG游戏的若干拓展及变形》 毛杰明《母函数的性质及应用...


中国国家集训队论文集目录(1999-2009).txt

浅析最大最小定理在信息学竞赛中的应用》 国家集训队2009论文集 武森 《浅谈信息学竞赛中的“0”和“1”》贾志豪 《组合游戏略述浅谈SG游戏的若干...


历年国家集训队论文题目.doc

历年国家集训队论文题目_法律资料_人文社科_专业资料...由感性认识到理性认识透析一类搏弈游戏的解答过程...浅谈特殊穷举思想的应用 周源 - 浅谈数形结合思想在...


国家集训队论文目录.txt

国家集训队论文目录_文学研究_人文社科_专业资料。...由感性认识到理性认识透析一类搏弈游戏的解答过程...浅谈特殊穷举思想的应用 周 源 - 浅谈数形结合思想...


算法合集之《组合游戏略述浅谈SG游戏的若干拓展及....ppt

算法合集之《组合游戏略述浅谈SG游戏的若干拓展及变形》_IT/计算机_专业资料...国家集训队2009论文集组... 24页 免费 算法合集之《解析一类组... 20页 免...


组合游戏略述浅谈SG游戏的若干拓展及变形_图文.ppt

组合游戏略述浅谈组合游戏的若干拓展及变形 浅谈组合游戏的若干拓展及变形...国家集训队2013论文集组... 34页 免费 团体拓展训练游戏 20页 1下载券 团体...


目录.txt

浅析最大最小定理在信息学竞赛中的应用》 国家集训队2009论文集 1.武森《浅谈信息学竞赛中的“0”和“1”》 2.贾志豪《组合游戏略述浅谈SG游戏的...


国家集训队2008论文集浅谈随机化思想在几何_图文.ppt

国家集训队2008论文集浅谈随机化思想在几何 - 感受随机的美 浅谈随机化思


国家集训队2004论文集_周源.pdf

论文IOI2004 国家集训队论文 周源 浅谈数形结合思想...事实 上,正如前文所,一般的计算机都是以数为...但从细节 上分析,它们之间仍有差异。 其一,三者...


NOI国家集训队论文分类(至2008)(摘抄自C博客).doc

NOI国家集训队论文分类(至2008)(摘抄自C博客)_学科竞赛_高中教育_教育专区。...《组合游戏略述浅谈 SG 游戏的若干拓展及变形》 母函数 2009 - 毛杰明《...


国家集训队2009论文集浅谈几类背包题.pdf

国家集训队2009论文集浅谈几类背包题_IT/计算机_...8 9 / 20 浅谈几类背包题 这道题需要在 treedp...


国家集训队2009论文集浅谈如何解决不平等博_图文.ppt

国家集训队2009论文集浅谈如何解决不平等博_IT/计算机_专业资料。国家集训队2009...第一部分:介绍如何利用Surreal Number分析一类不平 等组合游戏 第二部分:介绍...


国家集训队2007论文集2.王晓珂《解析一类组.doc

国家集训队2007论文集2.王晓珂《解析一类组 - 组合游戏的简单分析 四川省绵阳南山中学 王晓珂 【关键字】 组合游戏 游戏的和 nim 和 Sprague-Grundy 函数 【...


noi论文分类.doc

noi论文分类_计算机软件及应用_IT/计算机_专业资料。国家集训队论文分类组合数学 ...《组合游戏略述浅谈 SG 游戏的若干拓展及变形》 母函数 2009 - 毛杰明《...


2013中国国家集训队选拔考试_论文.pdf

2013中国国家集训队选拔考试_从业资格考试_资格考试/认证_教育专区。24 中等数学 201 3中 国国家集训队选拔考试 中圈分类号 :G424.79 文献标识码 :A 文章编号...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com