算法合集之《组合游戏略述-浅谈SG游戏的若干拓展及变形》课件.ppt

1、组合游戏略述组合游戏略述浅谈组合游戏的若干拓展及变形浅谈组合游戏的若干拓展及变形石家庄二中石家庄二中 北校区北校区高三高三18班班 贾志豪贾志豪2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2 2页页内容概述content introductionv组合游戏的规则组合游戏的规则拓展拓展走完最后一步者输走完最后一步者输Anti-SG游戏和游戏和SJ定理定理可以将一堆石子分成多堆可以将一堆石子分成多堆Multi-SG游戏游戏 每一个可移动的棋子都要移动每一个可移动的棋子都要移动Every-SG游戏游戏 v组合游戏的模型组合游戏的模型变形变形翻硬币游戏翻硬币游戏 无向图删边游戏无向图删边游戏

2、 每一个可移动的棋子都要移动每一个可移动的棋子都要移动Every-SG游戏游戏无向图删边游戏无向图删边游戏2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第3 3页页Every-SG游戏游戏v何为何为Every-SG游戏？游戏？有有N个单一游戏，游戏者轮流进行决策；个单一游戏，游戏者轮流进行决策；游戏者的决策必须满足：对于所有还没有结束的游戏者的决策必须满足：对于所有还没有结束的单一游戏，游戏者必须对该单一游戏进行一步操单一游戏，游戏者必须对该单一游戏进行一步操作；作；无路可走者输无路可走者输怎么办？怎么办？怎么办？怎么办？怎么办？怎么办？2023-2-4石家庄二中石家庄二中 贾志豪贾志豪

3、第第4 4页页Every-SG游戏游戏v贪心策略：贪心策略：对于某一个单一游戏，如果当前是先对于某一个单一游戏，如果当前是先手必胜局，那么先手不会放弃游戏的手必胜局，那么先手不会放弃游戏的胜利！胜利！那么，游戏者需要做的，就是让自己那么，游戏者需要做的，就是让自己可以取得胜利的游戏尽可能可以取得胜利的游戏尽可能长长的玩下的玩下去，让自己不能取得胜利的游戏尽可去，让自己不能取得胜利的游戏尽可能能短短的玩下去！的玩下去！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第5 5页页Every-SG游戏游戏v解决方法：解决方法：对于对于SGSG值为值为0 0的点，我们需要知道最少几步能将的点，我们

4、需要知道最少几步能将游戏带入终止状态游戏带入终止状态；对于对于SGSG值不为值不为0 0的点，我们需要知道最多几步游的点，我们需要知道最多几步游戏会被带入终止状态戏会被带入终止状态；以上两个值，我们都用以上两个值，我们都用step来表示来表示的后继状态为的后继状态为为终止状态vuvSGustepuSGvuvSGustepvvstep0)(1)(min0)(0)(1)(max0)(2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第6 6页页Every-SG游戏游戏v结论：结论：先手必胜当且仅当先手必胜当且仅当step值最大的单一游戏为先手值最大的单一游戏为先手必胜游戏必胜游戏v思考：思考：s

5、tep值最大的既有先手必胜游戏，又有先手必败值最大的既有先手必胜游戏，又有先手必败游戏时，是否意味着游戏时，是否意味着平局？平局？所有先手必胜的游戏的所有先手必胜的游戏的step值为奇数！值为奇数！所有先手必败的游戏的所有先手必败的游戏的step值为偶数！值为偶数！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第7 7页页Every-SG游戏游戏v发现宝藏发现宝藏（长与短的博弈）（长与短的博弈）一般的组合游戏只有输与赢的博弈；一般的组合游戏只有输与赢的博弈；而而Every-SG游戏又增加了游戏又增加了长与短的博弈，长与短的博弈，这使得这使得Every-SG游戏游戏更有嚼头，更有味道更有嚼

6、头，更有味道 输 赢 长 短2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第8 8页页Cutting Edges游戏v退化版：退化版：给出一个有给出一个有N个点的树，有一个点作为树的根节个点的树，有一个点作为树的根节点。点。游戏者轮流从树中删去边，删去一条边后，不与游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。根节点相连的部分将被移走。谁无边可删谁输谁无边可删谁输如何做？如何做？如何做？如何做？如何做？如何做？2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第9 9页页Cutting Edges游戏v从树结构入手从树结构入手?树结构是一种特殊的拓扑结构树结构是一

7、种特殊的拓扑结构v从最简单的例子入手从最简单的例子入手?根节点只有一个分支根节点只有一个分支2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1010页页考虑：已知左图的考虑：已知左图的SG值，如何求右图的值，如何求右图的SG值值Cutting Edges游戏根节点GGG G图图根节点中间节点GGG G图图由特殊例子给出猜想：由特殊例子给出猜想：SG(G)=SG(G)+12023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1111页页Cutting Edges游戏v证明猜想证明猜想（数学归纳法）（数学归纳法）即证：它的后继状态的即证：它的后继状态的SG值为值为0到到SG(G)的所有值；的

8、所有值；以树中以树中节点个数节点个数作为阶段；作为阶段；一个节点和两个节点显然成立；一个节点和两个节点显然成立；假设假设N个节点时成立，个节点时成立，v情况一：若去掉与根节点相连的边情况一：若去掉与根节点相连的边根节点中间节点GGG G图图2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1212页页Cutting Edges游戏情况一：若去掉与根节点相连的边情况一：若去掉与根节点相连的边GG根节点中间节点GG根节点中间节点SG值为值为02023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1313页页Cutting Edges游戏v证明猜想证明猜想（数学归纳法）（数学归纳法）以树中节点个

9、数作为阶段；以树中节点个数作为阶段；一个节点和两个节点显然成立；一个节点和两个节点显然成立；假设假设N个节点时成立，个节点时成立，v情况一：若去掉与根节点相连的边情况一：若去掉与根节点相连的边v情况二：若去掉情况二：若去掉G G中中的边的边2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1414页页Cutting Edges游戏情况二：若去掉情况二：若去掉G G中中的边的边GG根节点中间节点根节点中间节点GGSG值不确定值不确定2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1515页页Cutting Edges游戏根节点GGSG值为值为0到到SG(G G)-1，取不到取不到SG(

10、G G)至多有至多有N-1N-1个点个点根节点中间节点GG至多有至多有N N个点个点SG值为值为1到到SG(G G)，取不取不到到SG(G G)+1考虑左图的考虑左图的SG值意味着什么？值意味着什么？由归纳假设由归纳假设定理：定理：SG(G)=SG(G)+12023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1616页页Cutting Edges游戏更复杂的情况更复杂的情况GG1 1GG2 2GGT T根节点2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1717页页Cutting Edges游戏v根据树结构的拓扑性根据树结构的拓扑性v试着去对试着去对G G图进行拆分图进行拆分拆法一（

11、一般树形结构拆法）拆法一（一般树形结构拆法）GG1 1GG2 2GGT TGG1 1GG2 2GGT T不够本质！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1818页页Cutting Edges游戏v试着去对试着去对G G图进行拆分图进行拆分拆法二（很大胆的尝试）拆法二（很大胆的尝试）GG1 1GG2 2GGT TGG1 1GG2 2GGT T十分完美！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第1919页页Cutting Edges游戏v完美在哪了？完美在哪了？v哦。哦。v对应对应NIM取石子模型！取石子模型！GG1 1GG2 2GGT TGG1 1GG2 2GGT T

12、十分完美！)1)(.)1)()(1TGSGGSGGSG2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2020页页Say Goodbye谢谢观看！Thanks for watching！欢迎提问欢迎提问！Question Time！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2121页页Cutting Edges游戏v稍加拓展：稍加拓展：A和和B轮流从图中删边，删去一条边后，不与根轮流从图中删边，删去一条边后，不与根节点相连的部分将被移走。节点相连的部分将被移走。A A为先手。为先手。图是通过从基础树中加一些边得到的。图是通过从基础树中加一些边得到的。所有形成的环保证不共用边，

13、且只与基础树有一所有形成的环保证不共用边，且只与基础树有一个公共点。个公共点。不要慌！不要慌！不要慌！不要慌！不要慌！不要慌！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2222页页Cutting Edges游戏v环的处理成为关键环的处理成为关键v惊人发现，惊人发现，任何奇环的任何奇环的SG值为值为1根节点根节点奇环删边后，左右两个分奇环删边后，左右两个分支的边数同奇偶，异或值支的边数同奇偶，异或值不可能为不可能为1 12023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2323页页Cutting Edges游戏v环的处理成为关键环的处理成为关键v惊人发现，惊人发现，任何奇环的任何

14、奇环的SG值为值为1任何偶环的任何偶环的SG值为值为0根节点根节点偶环删边后，左右两个分偶环删边后，左右两个分支的边数异奇偶，异或值支的边数异奇偶，异或值不可能为不可能为1 12023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2424页页Cutting Edges游戏v环的处理成为关键环的处理成为关键v惊人发现，惊人发现，任何奇环的任何奇环的SG值为值为1任何偶环的任何偶环的SG值为值为0v策略策略将偶环删去，将奇环替换成一条边！将偶环删去，将奇环替换成一条边！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2525页页Cutting Edges游戏v环的处理成为关键环的处理成为关键

15、v惊人发现，惊人发现，任何奇环的任何奇环的SG值为值为1任何偶环的任何偶环的SG值为值为0v策略策略将偶环删去，将奇环替换成一条边！将偶环删去，将奇环替换成一条边！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2626页页Cutting Edges游戏v环的处理成为关键环的处理成为关键v惊人发现，惊人发现，任何奇环的任何奇环的SG值为值为1任何偶环的任何偶环的SG值为值为0v策略策略将偶环删去，将奇环替换成一条边！将偶环删去，将奇环替换成一条边！转换成功！变成了树！变成了树！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2727页页Say Goodbye谢谢观看！Thanks

16、for watching！欢迎提问欢迎提问！Question Time！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2828页页Cutting Edges游戏v再次拓展再次拓展一个无相联通图，有一个点作为图的根。一个无相联通图，有一个点作为图的根。游戏者轮流从图中删去边，删去一条边后，不与游戏者轮流从图中删去边，删去一条边后，不与根节点相连的部分将被移走。根节点相连的部分将被移走。v怎么办？怎么办？好难！好难！好难！好难！好难！好难！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第2929页页Cutting Edges游戏v考虑上题给出的提示考虑上题给出的提示将环处理掉即可将环

17、处理掉即可v时间原因，直接给出方法。时间原因，直接给出方法。2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第3030页页Cutting Edges游戏v对于偶环对于偶环GG1 1GG2 2GG3 3GG4 4GG5 5GG6 6缩成一个点！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第3131页页Cutting Edges游戏v对于偶环对于偶环GG1 1GG2 2GG3 3GG4 4GG5 5GG6 6缩成一个点！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第3232页页Cutting Edges游戏v对于奇环对于奇环GG1 1GG2 2GG3 3GG4 4GG5 5缩成点加边！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第3333页页Cutting Edges游戏v对于奇环对于奇环GG1 1GG2 2GG3 3GG4 4GG5 5缩成点加边！2023-2-4石家庄二中石家庄二中 贾志豪贾志豪第第3434页页Say Goodbye谢谢观看！Thanks for watching！欢迎提问欢迎提问！Question Time！