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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,石家庄二中 贾志豪,第,*,页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,石家庄二中 贾志豪,第,*,页,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,石家庄二中 贾志豪,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,石家庄二中 贾志豪,*,组合游戏略述,浅谈组合游戏的若干拓展及变形,石家庄二中 北校区,高三,18,班,贾志豪,2026/5/28 周四,石家庄二中 贾志豪,第2,页,内容概述,content introduction,组合游戏的规则,拓展,走完最后一步者输,Anti-SG,游戏和,SJ,定理,可以将一堆石子分成多堆,Multi-SG,游戏,每一个可移动的棋子都要移动,Every-SG,游戏,组合游戏的模型,变形,翻硬币游戏,无向图删边游戏,每一个可移动的棋子都要移动,Every-SG,游戏,无向图删边游戏,2026/5/28 周四,石家庄二中 贾志豪,第,3,页,Every-SG,游戏,何为,Every-SG,游戏？,有,N,个单一游戏，游戏者轮流进行决策；,游戏者的决策必须满足：对于所有还没有结束的单一游戏，游戏者必须对该单一游戏进行一步操作；无路可走者输,怎么办？,怎么办？,怎么办？,2026/5/28 周四,石家庄二中 贾志豪,第,4,页,Every-SG,游戏,贪心策略：,对于某一个单一游戏，如果当前是先手必胜局，那么先手不会放弃游戏的胜利！,那么，游戏者需要做的，就是让自己可以取得胜利的游戏尽可能,长,的玩下去，让自己不能取得胜利的游戏尽可能,短,的玩下去！,2026/5/28 周四,石家庄二中 贾志豪,第,5,页,Every-SG,游戏,解决方法：,对于,SG,值为,0,的点，我们需要知道最少几步能将游戏带入终止状态,；,对于,SG,值不为,0,的点，我们需要知道最多几步游戏会被带入终止状态,；,以上两个值，我们都用,step,来表示,2026/5/28 周四,石家庄二中 贾志豪,第,6,页,Every-SG,游戏,结论：,先手必胜当且仅当,step,值最大的单一游戏为先手必胜游戏,思考：,step,值最大的既有先手必胜游戏，又有先手必败游戏时，是否意味着,平局？,所有先手必胜的游戏的,step,值为奇数！所有先手必败的游戏的,step,值为偶数！,2026/5/28 周四,石家庄二中 贾志豪,第,7,页,Every-SG,游戏,发现宝藏,（长与短的博弈）,一般的组合游戏只有输与赢的博弈；,而,Every-SG,游戏又增加了,长与短的博弈，,这使得,Every-SG,游戏,更有嚼头，更有味道,输,赢,长,短,2026/5/28 周四,石家庄二中 贾志豪,第,8,页,Cutting Edges,游戏,退化版：,给出一个有,N,个点的树，有一个点作为树的根节点。,游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。,谁无边可删谁输,如何做？,如何做？,如何做？,2026/5/28 周四,石家庄二中 贾志豪,第,9,页,Cutting Edges,游戏,从树结构入手,?,树结构是一种特殊的拓扑结构,从最简单的例子入手,?,根节点只有一个分支,2026/5/28 周四,石家庄二中 贾志豪,第,10,页,考虑：已知左图的,SG,值，如何求右图的,SG,值,Cutting Edges,游戏,根节点,G,G,图,根节点,中间节点,G,G,图,由特殊例子给出猜想：,SG,(,G,),=SG,(,G,),+1,2026/5/28 周四,石家庄二中 贾志豪,第,11,页,Cutting Edges,游戏,证明猜想,（数学归纳法）,即证：它的后继状态的,SG,值为,0,到,SG(G),的所有值；,以树中,节点个数,作为阶段；,一个节点和两个节点显然成立；,假设,N,个节点时成立，,情况一：若去掉与根节点相连的边,根节点,中间节点,G,G,图,2026/5/28 周四,石家庄二中 贾志豪,第,12,页,Cutting Edges,游戏,情况一：若去掉与根节点相连的边,G,根节点,中间节点,G,根节点,中间节点,SG,值为,0,2026/5/28 周四,石家庄二中 贾志豪,第,13,页,Cutting Edges,游戏,证明猜想,（数学归纳法）,以树中节点个数作为阶段；,一个节点和两个节点显然成立；,假设,N,个节点时成立，,情况一：若去掉与根节点相连的边,情况二：若去掉,G,中,的边,2026/5/28 周四,石家庄二中 贾志豪,第,14,页,Cutting Edges,游戏,情况二：若去掉,G,中,的边,G,根节点,中间节点,根节点,中间节点,G,SG,值不确定,2026/5/28 周四,石家庄二中 贾志豪,第,15,页,Cutting Edges,游戏,根节点,G,SG,值为,0,到,SG,(,G,),-1,，,取不到,SG,(,G,),至多有,N-1,个点,根节点,中间节点,G,至多有,N,个点,SG,值为,1,到,SG,(,G,),，,取不到,SG,(,G,),+1,考虑左图的,SG,值意味着什么？,由归纳假设,定理：,SG,(,G,),=SG,(,G,),+1,2026/5/28 周四,石家庄二中 贾志豪,第,16,页,Cutting Edges,游戏,更复杂的情况,G,1,G,2,G,T,根节点,2026/5/28 周四,石家庄二中 贾志豪,第,17,页,Cutting Edges,游戏,根据树结构的拓扑性,试着去对,G,图进行拆分,拆法一（一般树形结构拆法G,1,G,2,G,T,G,1,G,2,G,T,不够本质！,2026/5/28 周四,石家庄二中 贾志豪,第,18,页,Cutting Edges,游戏,试着去对,G,图进行拆分,拆法二（很大胆的尝试）,G,1,G,2,G,T,G,1,G,2,G,T,十分完美！,2026/5/28 周四,石家庄二中 贾志豪,第,19,页,Cutting Edges,游戏,完美在哪了？,哦。,对应,NIM,取石子模型！,G,1,G,2,G,T,G,1,G,2,G,T,十分完美！,2026/5/28 周四,石家庄二中 贾志豪,第,20,页,Say Goodbye,谢谢观看！,Thanks for watching,！,欢迎提问,！,Question Time,！,2026/5/28 周四,石家庄二中 贾志豪,第,21,页,Cutting Edges,游戏,稍加拓展：,A,和,B,轮流从图中删边，删去一条边后，不与根节点相连的部分将被移走。,A,为先手。,图是通过从基础树中加一些边得到的。,所有形成的环保证不共用边，且只与基础树有一个公共点。,不要慌！,不要慌！,不要慌！,2026/5/28 周四,石家庄二中 贾志豪,第,22,页,Cutting Edges,游戏,环的处理成为关键,惊人发现，,任何奇环的,SG,值为,1,根节点,根节点,奇环删边后，左右两个分支的边数同奇偶，异或值不可能为,1,2026/5/28 周四,石家庄二中 贾志豪,第,23,页,Cutting Edges,游戏,环的处理成为关键,惊人发现，,任何奇环的,SG,值为,1,任何偶环的,SG,值为,0,根节点,根节点,偶环删边后，左右两个分支的边数异奇偶，异或值不可能为,1,2026/5/28 周四,石家庄二中 贾志豪,第,24,页,Cutting Edges,游戏,环的处理成为关键,惊人发现，,任何奇环的,SG,值为,1,任何偶环的,SG,值为,0,策略,将偶环删去，将奇环替换成一条边！,2026/5/28 周四,石家庄二中 贾志豪,第,25,页,Cutting Edges,游戏,环的处理成为关键,惊人发现，,任何奇环的,SG,值为,1,任何偶环的,SG,值为,0,策略,将偶环删去，将奇环替换成一条边！,2026/5/28 周四,石家庄二中 贾志豪,第,26,页,Cutting Edges,游戏,环的处理成为关键,惊人发现，,任何奇环的,SG,值为,1,任何偶环的,SG,值为,0,策略,将偶环删去，将奇环替换成一条边！,转换成功！,变成了树！,2026/5/28 周四,石家庄二中 贾志豪,第,27,页,Say Goodbye,谢谢观看！,Thanks for watching,！,欢迎提问,！,Question Time,！,2026/5/28 周四,石家庄二中 贾志豪,第,28,页,Cutting Edges,游戏,再次拓展,一个无相联通图，有一个点作为图的根。,游戏者轮流从图中删去边，删去一条边后，不与根节点相连的部分将被移走。,怎么办？,好难！,好难！,好难！,2026/5/28 周四,石家庄二中 贾志豪,第,29,页,Cutting Edges,游戏,考虑上题给出的提示,将环处理掉即可,时间原因，直接给出方法。,2026/5/28 周四,石家庄二中 贾志豪,第,30,页,Cutting Edges,游戏,对于偶环,G,1,G,2,G,3,G,4,G,5,G,6,缩成一个点！,2026/5/28 周四,石家庄二中 贾志豪,第,31,页,Cutting Edges,游戏,对于偶环,G,1,G,2,G,3,G,4,G,5,G,6,缩成一个点！,2026/5/28 周四,石家庄二中 贾志豪,第,32,页,Cutting Edges,游戏,对于奇环,G,1,G,2,G,3,G,4,G,5,缩成点加边！,2026/5/28 周四,石家庄二中 贾志豪,第,33,页,Cutting Edges,游戏,对于奇环,G,1,G,2,G,3,G,4,G,5,缩成点加边！,2026/5/28 周四,石家庄二中 贾志豪,第,34,页,Say Goodbye,谢谢观看！,Thanks for watching,！,欢迎提问,！,Question Time,！,