《组合游戏略述——浅谈SG游戏的若干拓展及变形课件.ppt》由会员分享，可在线阅读，更多相关《组合游戏略述——浅谈SG游戏的若干拓展及变形课件.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、组合游戏略述组合游戏略述浅谈组合游戏的若干拓展及变形浅谈组合游戏的若干拓展及变形18班班 贾志豪贾志豪2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第2 2页页内容概述content introductionv组合游戏的规则组合游戏的规则拓展拓展走完最后一步者输走完最后一步者输Anti-SG游戏和游戏和SJ定理定理可以将一堆石子分成多堆可以将一堆石子分成多堆Multi-SG游戏游戏 每一个可移动的棋子都要移动每一个可移动的棋子都要移动Every-SG游戏游戏 v组合游戏的模型组合游戏的模型变形变形翻硬币游戏翻硬币游戏 无向图删边游戏无向图删边游戏 每一个可移动的棋子都要移动每一个可移动
2、的棋子都要移动Every-SG游戏游戏无向图删边游戏无向图删边游戏2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第3 3页页Every-SG游戏游戏v何为何为Every-SG游戏？游戏？有有N个单一游戏，游戏者轮流进行决策；个单一游戏，游戏者轮流进行决策；游戏者的决策必须满足：对于所有还没有结束的游戏者的决策必须满足：对于所有还没有结束的单一游戏，游戏者必须对该单一游戏进行一步操单一游戏，游戏者必须对该单一游戏进行一步操作；作；无路可走者输无路可走者输怎么办？怎么办？怎么办？怎么办？怎么办？怎么办？2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第5 5页页Every-SG游戏游
3、戏v解决方法：解决方法：对于对于SGSG值为值为0 0的点，我们需要知道最少几步能将的点，我们需要知道最少几步能将游戏带入终止状态游戏带入终止状态；对于对于SGSG值不为值不为0 0的点，我们需要知道最多几步游的点，我们需要知道最多几步游戏会被带入终止状态戏会被带入终止状态；以上两个值，我们都用以上两个值，我们都用step来表示来表示2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第6 6页页Every-SG游戏游戏v结论：结论：先手必胜当且仅当先手必胜当且仅当step值最大的单一游戏为先手值最大的单一游戏为先手必胜游戏必胜游戏v思考：思考：step值最大的既有先手必胜游戏，又有先手必败
4、值最大的既有先手必胜游戏，又有先手必败游戏时，是否意味着游戏时，是否意味着平局？平局？所有先手必胜的游戏的所有先手必胜的游戏的step值为奇数！值为奇数！所有先手必败的游戏的所有先手必败的游戏的step值为偶数！值为偶数！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第7 7页页Every-SG游戏游戏v发现宝藏发现宝藏（长与短的博弈）（长与短的博弈）一般的组合游戏只有输与赢的博弈；一般的组合游戏只有输与赢的博弈；而而Every-SG游戏又增加了游戏又增加了长与短的博弈，长与短的博弈，这使得这使得Every-SG游戏游戏更有嚼头，更有味道更有嚼头，更有味道 输 赢 长 短2023/3/
5、29石家庄二中石家庄二中 贾志豪贾志豪第第8 8页页Cutting Edges游戏v退化版：退化版：给出一个有给出一个有N个点的树，有一个点作为树的根节个点的树，有一个点作为树的根节点。点。游戏者轮流从树中删去边，删去一条边后，不与游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。根节点相连的部分将被移走。谁无边可删谁输谁无边可删谁输如何做？如何做？如何做？如何做？如何做？如何做？2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第1010页页考虑：已知左图的考虑：已知左图的SG值，如何求右图的值，如何求右图的SG值值Cutting Edges游戏根节点GGG G图图根节
6、点中间节点GGG G图图由特殊例子给出猜想：由特殊例子给出猜想：SG(G)=SG(G)+12023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第1212页页Cutting Edges游戏情况一：若去掉与根节点相连的边情况一：若去掉与根节点相连的边GG根节点中间节点GG根节点中间节点SG值为值为02023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第1414页页Cutting Edges游戏情况二：若去掉情况二：若去掉G G中中的边的边GG根节点中间节点根节点中间节点GGSG值不确定值不确定2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第1515页页Cutting Edges游戏根节
7、点GGSG值为值为0到到SG(G G)-1，取不到取不到SG(G G)至多有至多有N-1N-1个点个点根节点中间节点GG至多有至多有N N个点个点SG值为值为1到到SG(G G)，取不，取不到到SG(G G)+1考虑左图的考虑左图的SG值意味着什么？值意味着什么？由归纳假设由归纳假设定理：定理：SG(G)=SG(G)+12023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第1616页页Cutting Edges游戏更复杂的情况更复杂的情况GG1 1GG2 2GGT T根节点2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第1717页页Cutting Edges游戏v根据树结构的拓扑性根
8、据树结构的拓扑性v试着去对试着去对G G图进行拆分图进行拆分拆法一（一般树形结构拆法）拆法一（一般树形结构拆法）GG1 1GG2 2GGT TGG1 1GG2 2GGT T不够本质！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第1818页页Cutting Edges游戏v试着去对试着去对G G图进行拆分图进行拆分拆法二（很大胆的尝试）拆法二（很大胆的尝试）GG1 1GG2 2GGT TGG1 1GG2 2GGT T十分完美！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第2020页页Say Goodbye谢谢观看！Thanks for watching！欢迎提问欢迎提问！Qu
9、estion Time！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第2121页页Cutting Edges游戏v稍加拓展：稍加拓展：A和和B轮流从图中删边，删去一条边后，不与根轮流从图中删边，删去一条边后，不与根节点相连的部分将被移走。节点相连的部分将被移走。A A为先手。为先手。图图是通是通过过从基从基础树础树中加一些中加一些边边得到的。得到的。所有形成的所有形成的环环保保证证不共用不共用边边，且只与基，且只与基础树础树有一有一个公共点。个公共点。不要慌！不要慌！不要慌！不要慌！不要慌！不要慌！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第2323页页Cutting E
10、dges游戏v环的处理成为关键环的处理成为关键v惊人发现，惊人发现，任何奇环的任何奇环的SG值为值为1任何偶环的任何偶环的SG值为值为0根节点根节点偶环删边后，左右两个分偶环删边后，左右两个分支的边数异奇偶，异或值支的边数异奇偶，异或值不可能为不可能为1 12023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第2424页页Cutting Edges游戏v环的处理成为关键环的处理成为关键v惊人发现，惊人发现，任何奇环的任何奇环的SG值为值为1任何偶环的任何偶环的SG值为值为0v策略策略将偶环删去，将奇环替换成一条边！将偶环删去，将奇环替换成一条边！2023/3/29石家庄二中石家庄二中 贾志豪
11、贾志豪第第2626页页Cutting Edges游戏v环的处理成为关键环的处理成为关键v惊人发现，惊人发现，任何奇环的任何奇环的SG值为值为1任何偶环的任何偶环的SG值为值为0v策略策略将偶环删去，将奇环替换成一条边！将偶环删去，将奇环替换成一条边！转换成功！变成了树！变成了树！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第2727页页Say Goodbye谢谢观看！Thanks for watching！欢迎提问欢迎提问！Question Time！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第2828页页Cutting Edges游戏v再次拓展再次拓展一个无相联通图，有
12、一个点作为图的根。一个无相联通图，有一个点作为图的根。游戏者轮流从图中删去边，删去一条边后，不与游戏者轮流从图中删去边，删去一条边后，不与根节点相连的部分将被移走。根节点相连的部分将被移走。v怎么办？怎么办？好难！好难！好难！好难！好难！好难！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第3030页页Cutting Edges游戏v对于偶环对于偶环GG1 1GG2 2GG3 3GG4 4GG5 5GG6 6缩成一个点！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第3131页页Cutting Edges游戏v对于偶环对于偶环GG1 1GG2 2GG3 3GG4 4GG5 5GG6 6缩成一个点！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第3232页页Cutting Edges游戏v对于奇环对于奇环GG1 1GG2 2GG3 3GG4 4GG5 5缩成点加边！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第3333页页Cutting Edges游戏v对于奇环对于奇环GG1 1GG2 2GG3 3GG4 4GG5 5缩成点加边！2023/3/29石家庄二中石家庄二中 贾志豪贾志豪第第3434页页Say Goodbye谢谢观看！Thanks for watching！欢迎提问欢迎提问！Question Time！