国家集训队2013论文集组合游戏略述-浅谈.ppt

《国家集训队2013论文集组合游戏略述-浅谈.ppt》由会员分享，可在线阅读，更多相关《国家集训队2013论文集组合游戏略述-浅谈.ppt（34页珍藏版）》请在三一办公上搜索。

1、组合游戏略述,浅谈组合游戏的若干拓展及变形,石家庄二中 北校区高三18班 贾志豪,世爵平台 wenku1,2023/6/4,石家庄二中 贾志豪,第2页,内容概述content introduction,组合游戏的规则拓展走完最后一步者输Anti-SG游戏和SJ定理可以将一堆石子分成多堆Multi-SG游戏 每一个可移动的棋子都要移动Every-SG游戏 组合游戏的模型变形翻硬币游戏 无向图删边游戏,每一个可移动的棋子都要移动Every-SG游戏,无向图删边游戏,2023/6/4,石家庄二中 贾志豪,第3页,Every-SG游戏,何为Every-SG游戏？有N个单一游戏，游戏者轮流进行决策；游戏

2、者的决策必须满足：对于所有还没有结束的单一游戏，游戏者必须对该单一游戏进行一步操作；无路可走者输,怎么办？,怎么办？,怎么办？,2023/6/4,石家庄二中 贾志豪,第4页,Every-SG游戏,贪心策略：对于某一个单一游戏，如果当前是先手必胜局，那么先手不会放弃游戏的胜利！那么，游戏者需要做的，就是让自己可以取得胜利的游戏尽可能长的玩下去，让自己不能取得胜利的游戏尽可能短的玩下去！,2023/6/4,石家庄二中 贾志豪,第5页,Every-SG游戏,解决方法：对于SG值为0的点，我们需要知道最少几步能将游戏带入终止状态；对于SG值不为0的点，我们需要知道最多几步游戏会被带入终止状态；以上两个

3、值，我们都用step来表示,2023/6/4,石家庄二中 贾志豪,第6页,Every-SG游戏,结论：先手必胜当且仅当step值最大的单一游戏为先手必胜游戏思考：step值最大的既有先手必胜游戏，又有先手必败游戏时，是否意味着平局？,所有先手必胜的游戏的step值为奇数！所有先手必败的游戏的step值为偶数！,2023/6/4,石家庄二中 贾志豪,第7页,Every-SG游戏,发现宝藏（长与短的博弈）一般的组合游戏只有输与赢的博弈；而Every-SG游戏又增加了长与短的博弈，这使得Every-SG游戏更有嚼头，更有味道,输,赢,长,短,2023/6/4,石家庄二中 贾志豪,第8页,Cuttin

4、g Edges游戏,退化版：给出一个有N个点的树，有一个点作为树的根节点。游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。谁无边可删谁输,如何做？,如何做？,如何做？,2023/6/4,石家庄二中 贾志豪,第9页,Cutting Edges游戏,从树结构入手?树结构是一种特殊的拓扑结构从最简单的例子入手?根节点只有一个分支,2023/6/4,石家庄二中 贾志豪,第10页,考虑：已知左图的SG值，如何求右图的SG值,Cutting Edges游戏,由特殊例子给出猜想：SG(G)=SG(G)+1,2023/6/4,石家庄二中 贾志豪,第11页,Cutting Edges游戏,证

5、明猜想（数学归纳法）即证：它的后继状态的SG值为0到SG(G)的所有值；以树中节点个数作为阶段；一个节点和两个节点显然成立；假设N个节点时成立，情况一：若去掉与根节点相连的边,2023/6/4,石家庄二中 贾志豪,第12页,Cutting Edges游戏,情况一：若去掉与根节点相连的边,SG值为0,2023/6/4,石家庄二中 贾志豪,第13页,Cutting Edges游戏,证明猜想（数学归纳法）以树中节点个数作为阶段；一个节点和两个节点显然成立；假设N个节点时成立，情况一：若去掉与根节点相连的边情况二：若去掉G中的边,2023/6/4,石家庄二中 贾志豪,第14页,Cutting Edge

6、s游戏,情况二：若去掉G中的边,SG值不确定,2023/6/4,石家庄二中 贾志豪,第15页,Cutting Edges游戏,SG值为0到SG(G)-1，取不到SG(G),至多有N-1个点,至多有N个点,SG值为1到SG(G)，取不到SG(G)+1,考虑左图的SG值意味着什么？,由归纳假设,定理：SG(G)=SG(G)+1,2023/6/4,石家庄二中 贾志豪,第16页,Cutting Edges游戏,更复杂的情况,G1,G2,GT,根节点,2023/6/4,石家庄二中 贾志豪,第17页,Cutting Edges游戏,根据树结构的拓扑性试着去对G图进行拆分拆法一（一般树形结构拆法）,不够本质

7、！,2023/6/4,石家庄二中 贾志豪,第18页,Cutting Edges游戏,试着去对G图进行拆分拆法二（很大胆的尝试）,十分完美！,2023/6/4,石家庄二中 贾志豪,第19页,Cutting Edges游戏,完美在哪了？哦。对应NIM取石子模型！,十分完美！,2023/6/4,石家庄二中 贾志豪,第20页,Say Goodbye,谢谢观看！,Thanks for watching！,欢迎提问！,Question Time！,2023/6/4,石家庄二中 贾志豪,第21页,Cutting Edges游戏,稍加拓展：A和B轮流从图中删边，删去一条边后，不与根节点相连的部分将被移走。A为

8、先手。图是通过从基础树中加一些边得到的。所有形成的环保证不共用边，且只与基础树有一个公共点。,不要慌！,不要慌！,不要慌！,2023/6/4,石家庄二中 贾志豪,第22页,Cutting Edges游戏,环的处理成为关键惊人发现，任何奇环的SG值为1,奇环删边后，左右两个分支的边数同奇偶，异或值不可能为1,2023/6/4,石家庄二中 贾志豪,第23页,Cutting Edges游戏,环的处理成为关键惊人发现，任何奇环的SG值为1任何偶环的SG值为0,偶环删边后，左右两个分支的边数异奇偶，异或值不可能为1,2023/6/4,石家庄二中 贾志豪,第24页,Cutting Edges游戏,环的处理

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

10、ching！,欢迎提问！,Question Time！,2023/6/4,石家庄二中 贾志豪,第28页,Cutting Edges游戏,再次拓展一个无相联通图，有一个点作为图的根。游戏者轮流从图中删去边，删去一条边后，不与根节点相连的部分将被移走。怎么办？,好难！,好难！,好难！,2023/6/4,石家庄二中 贾志豪,第29页,Cutting Edges游戏,考虑上题给出的提示将环处理掉即可时间原因，直接给出方法。,2023/6/4,石家庄二中 贾志豪,第30页,Cutting Edges游戏,对于偶环,G1,G2,G3,G4,G5,G6,缩成一个点！,2023/6/4,石家庄二中 贾志豪,第31页,Cutting Edges游戏,对于偶环,缩成一个点！,2023/6/4,石家庄二中 贾志豪,第32页,Cutting Edges游戏,对于奇环,G1,G2,G3,G4,G5,缩成点加边！,2023/6/4,石家庄二中 贾志豪,第33页,Cutting Edges游戏,对于奇环,缩成点加边！,2023/6/4,石家庄二中 贾志豪,第34页,Say Goodbye,谢谢观看！,Thanks for watching！,欢迎提问！,Question Time！,