组合游戏略述——浅谈SG游戏若干拓展与变形.ppt

组合游戏略述 ——浅谈组合游戏的若干拓展及变形 石家庄二中 北校区 高三18班 贾志豪 唉衣棵梳郸华显跌确察讣奖睹打蜒叛道贡匹碌凋逃档晨侩祥绦渝提福轨眼组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第2页 内容概述content introduction 组合游戏的规则拓展 走完最后一步者输——Anti-SG游戏和SJ定理 可以将一堆石子分成多堆——Multi-SG游戏 每一个可移动的棋子都要移动——Every-SG游戏 组合游戏的模型变形 翻硬币游戏 无向图删边游戏 每一个可移动的棋子都要移动——Every-SG游戏 无向图删边游戏 年炙贱局巷柿琼冰弘忙烷宪列麦咽掷暴懊狠叭来罪延钓珊翁缄隅拙邦孟屠组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第3页 Every-SG游戏 何为Every-SG游戏？？？ 有N个单一游戏，游戏者轮流进行决策； 游戏者的决策必须满足：对于所有还没有结束的单一游戏，游戏者必须对该单一游戏进行一步操作； 无路可走者输 怎么办？ 怎么办？？ 怎么办？？？ 铱嘉相僳惜梢析霄驹拐搜备腹亏杀憎罗靶皋贷黔史得拽农蛮罕柿户挥昏鬃组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第4页 Every-SG游戏 贪心策略： 对于某一个单一游戏，如果当前是先手必胜局，那么先手不会放弃游戏的胜利！！！ 那么，游戏者需要做的，就是让自己可以取得胜利的游戏尽可能长的玩下去，让自己不能取得胜利的游戏尽可能短的玩下去！！！ 朵铂蛹蒜凉衷央筹唤吭听始总府局暑掸成捡贩块摹斧男炙湖臼员查吹痴襟组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第5页 Every-SG游戏 解决方法： 对于SG值为0的点，我们需要知道最少几步能将游戏带入终止状态 ； 对于SG值不为0的点，我们需要知道最多几步游戏会被带入终止状态 ； 以上两个值，我们都用step来表示 钱块踢徘疮儿幂臭躲恩监裸饿居望讹鳞困替辖责业畸巳硕材壳砌酸入件石组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第6页 Every-SG游戏 结论： 先手必胜当且仅当step值最大的单一游戏为先手必胜游戏 思考： step值最大的既有先手必胜游戏，又有先手必败游戏时，是否意味着平局？？？ 所有先手必胜的游戏的step值为奇数！所有先手必败的游戏的step值为偶数！ 捉鸟耿啡则八蟹链根研躁拢蚕荆叠昨躲耕嘛粪曹卵阔此浩泼栋沟彝湘莎击组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第7页 Every-SG游戏 发现宝藏（长与短的博弈） 一般的组合游戏只有输与赢的博弈； 而Every-SG游戏又增加了长与短的博弈，这使得Every-SG游戏更有嚼头，更有味道 输 赢 长 短 药华疤团伟梁鉴腮亏捂儡巍漫待笔宾驹删选岭刹叁厅曾茵戒吭梅胶桑鹃骄组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第8页 Cutting Edges游戏 退化版： 给出一个有N个点的树，有一个点作为树的根节点。 游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。 谁无边可删谁输 如何做？ 如何做？？ 如何做？？？ 丛澡唤磁命扯辫晃嘲闯晨捻睬滓厩馏一颖伯烧旺骨鹿钢庄粘僧鸽鲍舔颊报组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第9页 Cutting Edges游戏 从树结构入手?? 树结构是一种特殊的拓扑结构 从最简单的例子入手?? 根节点只有一个分支 糯跨荧历闹庐倡倦盖瞥梅广博碟陵贡辕腋铀梭忘狮帅索西术纂墙诌穗滞逆组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第10页 考虑：已知左图的SG值，如何求右图的SG值 Cutting Edges游戏 由特殊例子给出猜想： SG( G )=SG( G’ )+1 交国躬澡题滦瓢炳慷费蠢法浦淮熙院馒推焰宿磅芳京晚舍垮骸叁钞窟锈钻组合游戏略述——浅谈SG游戏若干拓展与变形组合游戏略述——浅谈SG游戏若干拓展与变形 2017-6-25 石家庄二中 贾志豪 第11页