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

* 石家庄二中 贾志豪 第*页 Cutting Edges游戏 考虑上题给出的提示 将环处理掉即可 时间原因，直接给出方法。 * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 对于偶环 G’1 G’2 G’3 G’4 G’5 G’6 缩成一个点！！！ * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 对于偶环 G’1 G’2 G’3 G’4 G’5 G’6 缩成一个点！！！ * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 对于奇环 G’1 G’2 G’3 G’4 G’5 缩成点加边！！！ * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 对于奇环 G’1 G’2 G’3 G’4 G’5 缩成点加边！！！ * 石家庄二中 贾志豪 第*页 Say Goodbye 谢谢观看！！！ Thanks for watching ！！！ 欢迎提问！！！ Question Time ！！！ 石家庄二中 贾志豪 石家庄二中 贾志豪 石家庄二中 贾志豪 石家庄二中 贾志豪 组合游戏略述 ——浅谈组合游戏的若干拓展及变形 石家庄二中 北校区 高三18班 贾志豪 * 石家庄二中 贾志豪 第*页 内容概述content introduction 组合游戏的规则拓展 走完最后一步者输——Anti-SG游戏和SJ定理 可以将一堆石子分成多堆——Multi-SG游戏 每一个可移动的棋子都要移动——Every-SG游戏 组合游戏的模型变形 翻硬币游戏 无向图删边游戏 每一个可移动的棋子都要移动——Every-SG游戏 无向图删边游戏 * 石家庄二中 贾志豪 第*页 Every-SG游戏 何为Every-SG游戏？？？ 有N个单一游戏，游戏者轮流进行决策； 游戏者的决策必须满足：对于所有还没有结束的单一游戏，游戏者必须对该单一游戏进行一步操作； 无路可走者输 怎么办？ 怎么办？？ 怎么办？？？ * 石家庄二中 贾志豪 第*页 Every-SG游戏 贪心策略： 对于某一个单一游戏，如果当前是先手必胜局，那么先手不会放弃游戏的胜利！！！ 那么，游戏者需要做的，就是让自己可以取得胜利的游戏尽可能长的玩下去，让自己不能取得胜利的游戏尽可能短的玩下去！！！ * 石家庄二中 贾志豪 第*页 Every-SG游戏 解决方法： 对于SG值为0的点，我们需要知道最少几步能将游戏带入终止状态 ； 对于SG值不为0的点，我们需要知道最多几步游戏会被带入终止状态 ； 以上两个值，我们都用step来表示 * 石家庄二中 贾志豪 第*页 Every-SG游戏 结论： 先手必胜当且仅当step值最大的单一游戏为先手必胜游戏 思考： step值最大的既有先手必胜游戏，又有先手必败游戏时，是否意味着平局？？？ 所有先手必胜的游戏的step值为奇数！所有先手必败的游戏的step值为偶数！ * 石家庄二中 贾志豪 第*页 Every-SG游戏 发现宝藏（长与短的博弈） 一般的组合游戏只有输与赢的博弈； 而Every-SG游戏又增加了长与短的博弈，这使得Every-SG游戏更有嚼头，更有味道 输 赢 长 短 * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 退化版： 给出一个有N个点的树，有一个点作为树的根节点。 游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。 谁无边可删谁输 如何做？ 如何做？？ 如何做？？？ * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 从树结构入手?? 树结构是一种特殊的拓扑结构 从最简单的例子入手?? 根节点只有一个分支 * 石家庄二中 贾志豪 第*页 考虑：已知左图的SG值，如何求右图的SG值 Cutting Edges游戏 根节点 G’ G’图 根节点 中间节点 G’ G图 由特殊例子给出猜想： SG( G )=SG( G’ )+1 * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 证明猜想（数学归纳法） 即证：它的后继状态的SG值为0到SG(G)的所有值； 以树中节点个数作为阶段； 一个节点和两个节点显然成立； 假设N个节点时成立， 情况一：若去掉与根节点相连的边 根节点 中间节点 G’ G图 * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 情况一：若去掉与根节点相连的边 G’ 根节点 中间节点 G’ 根节点 中间节点 SG值为0 * 石家庄二中 贾志豪 第*页 Cutting Edges游戏 证明猜想（数学归纳法） 以树中节点个数作为阶段； 一个节点和两个节点显然成立； 假设N个节点时成立， 情况一：若去掉与根节点相连的边 情况二：若去掉G’中的边 * 石家庄二中 贾志豪 第*页 Cutting Edges游