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页

石家庄二中 贾志豪



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