算法合集之組合游戲略述-淺談SG游戲的若干拓展及

組合游戲略述——淺談組合游戲的若干拓展及變形石家莊二中北校區(qū)高三18班

賈志豪算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第1頁(yè)!2022/12/19石家莊二中賈志豪第2頁(yè)內(nèi)容概述contentintroduction組合游戲的規(guī)則拓展走完最后一步者輸——Anti-SG游戲和SJ定理可以將一堆石子分成多堆——Multi-SG游戲每一個(gè)可移動(dòng)的棋子都要移動(dòng)——Every-SG游戲

組合游戲的模型變形翻硬幣游戲

無(wú)向圖刪邊游戲

每一個(gè)可移動(dòng)的棋子都要移動(dòng)——Every-SG游戲無(wú)向圖刪邊游戲算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第2頁(yè)!2022/12/19石家莊二中賈志豪第3頁(yè)Every-SG游戲何為Every-SG游戲？？？有N個(gè)單一游戲，游戲者輪流進(jìn)行決策；游戲者的決策必須滿足：對(duì)于所有還沒(méi)有結(jié)束的單一游戲，游戲者必須對(duì)該單一游戲進(jìn)行一步操作；無(wú)路可走者輸怎么辦？怎么辦？？怎么辦？？？算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第3頁(yè)!2022/12/19石家莊二中賈志豪第4頁(yè)Every-SG游戲解決方法：對(duì)于SG值為0的點(diǎn)，我們需要知道最少幾步能將游戲帶入終止?fàn)顟B(tài)；對(duì)于SG值不為0的點(diǎn)，我們需要知道最多幾步游戲會(huì)被帶入終止?fàn)顟B(tài)；以上兩個(gè)值，我們都用step來(lái)表示算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第4頁(yè)!2022/12/19石家莊二中賈志豪第5頁(yè)Every-SG游戲發(fā)現(xiàn)寶藏（長(zhǎng)與短的博弈）一般的組合游戲只有輸與贏的博弈；而Every-SG游戲又增加了長(zhǎng)與短的博弈，這使得Every-SG游戲更有嚼頭，更有味道

輸贏長(zhǎng)短算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第5頁(yè)!2022/12/19石家莊二中賈志豪第6頁(yè)CuttingEdges游戲從樹(shù)結(jié)構(gòu)入手??樹(shù)結(jié)構(gòu)是一種特殊的拓?fù)浣Y(jié)構(gòu)從最簡(jiǎn)單的例子入手??根節(jié)點(diǎn)只有一個(gè)分支算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第6頁(yè)!2022/12/19石家莊二中賈志豪第7頁(yè)CuttingEdges游戲證明猜想（數(shù)學(xué)歸納法）即證：它的后繼狀態(tài)的SG值為0到SG(G')的所有值；以樹(shù)中節(jié)點(diǎn)個(gè)數(shù)作為階段；一個(gè)節(jié)點(diǎn)和兩個(gè)節(jié)點(diǎn)顯然成立；假設(shè)N個(gè)節(jié)點(diǎn)時(shí)成立，情況一：若去掉與根節(jié)點(diǎn)相連的邊根節(jié)點(diǎn)中間節(jié)點(diǎn)G’G圖算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第7頁(yè)!2022/12/19石家莊二中賈志豪第8頁(yè)CuttingEdges游戲證明猜想（數(shù)學(xué)歸納法）以樹(shù)中節(jié)點(diǎn)個(gè)數(shù)作為階段；一個(gè)節(jié)點(diǎn)和兩個(gè)節(jié)點(diǎn)顯然成立；假設(shè)N個(gè)節(jié)點(diǎn)時(shí)成立，情況一：若去掉與根節(jié)點(diǎn)相連的邊情況二：若去掉G’中的邊算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第8頁(yè)!2022/12/19石家莊二中賈志豪第9頁(yè)CuttingEdges游戲根節(jié)點(diǎn)G’SG值為0到SG(

G’

)-1，取不到SG(

G’

)至多有N-1個(gè)點(diǎn)根節(jié)點(diǎn)中間節(jié)點(diǎn)G’至多有N個(gè)點(diǎn)SG值為1到SG(G’

)，取不到SG(G’

)+1考慮左圖的SG值意味著什么？？

由歸納假設(shè)定理：SG(G)=SG(G’)+1算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第9頁(yè)!2022/12/19石家莊二中賈志豪第10頁(yè)CuttingEdges游戲根據(jù)樹(shù)結(jié)構(gòu)的拓?fù)湫栽囍?duì)G圖進(jìn)行拆分拆法一（一般樹(shù)形結(jié)構(gòu)拆法）G’1……G’2G’T…G’1G’2G’T不夠本質(zhì)?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第10頁(yè)!2022/12/19石家莊二中賈志豪第11頁(yè)CuttingEdges游戲

完美在哪了？？？哦。。。對(duì)應(yīng)NIM取石子模型?。?！G’1……G’2G’T…G’1G’2G’T十分完美?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第11頁(yè)!2022/12/19石家莊二中賈志豪第12頁(yè)CuttingEdges游戲稍加拓展：A和B輪流從圖中刪邊，刪去一條邊后，不與根節(jié)點(diǎn)相連的部分將被移走。A為先手。圖是通過(guò)從基礎(chǔ)樹(shù)中加一些邊得到的。

所有形成的環(huán)保證不共用邊，且只與基礎(chǔ)樹(shù)有一個(gè)公共點(diǎn)。

不要慌！不要慌??！不要慌?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第12頁(yè)!2022/12/19石家莊二中賈志豪第13頁(yè)CuttingEdges游戲環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0根節(jié)點(diǎn)根節(jié)點(diǎn)偶環(huán)刪邊后，左右兩個(gè)分支的邊數(shù)異奇偶，異或值不可能為1算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第13頁(yè)!2022/12/19石家莊二中賈志豪第14頁(yè)CuttingEdges游戲環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第14頁(yè)!2022/12/19石家莊二中賈志豪第15頁(yè)SayGoodbye謝謝觀看?。?！Thanksforwatching?。?！歡迎提問(wèn)?。?！QuestionTime?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第15頁(yè)!2022/12/19石家莊二中賈志豪第16頁(yè)CuttingEdges游戲考慮上題給出的提示將環(huán)處理掉即可時(shí)間原因，直接給出方法。算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第16頁(yè)!2022/12/19石家莊二中賈志豪第17頁(yè)CuttingEdges游戲?qū)τ谂辑h(huán)G’1G’2G’3G’4G’5G’6縮成一個(gè)點(diǎn)?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第17頁(yè)!2022/12/19石家莊二中賈志豪第18頁(yè)CuttingEdges游戲?qū)τ谄姝h(huán)G’1G’2G’3G’4G’5縮成點(diǎn)加邊！??！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第18頁(yè)!2022/12/19石家莊二中賈志豪第19頁(yè)Every-SG游戲貪心策略：對(duì)于某一個(gè)單一游戲，如果當(dāng)前是先手必勝局，那么先手不會(huì)放棄游戲的勝利?。?！那么，游戲者需要做的，就是讓自己可以取得勝利的游戲盡可能長(zhǎng)的玩下去，讓自己不能取得勝利的游戲盡可能短的玩下去?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第19頁(yè)!2022/12/19石家莊二中賈志豪第20頁(yè)Every-SG游戲結(jié)論：先手必勝當(dāng)且僅當(dāng)step值最大的單一游戲?yàn)橄仁直貏儆螒蛩伎迹簊tep值最大的既有先手必勝游戲，又有先手必?cái)∮螒驎r(shí)，是否意味著平局？？？所有先手必勝的游戲的step值為奇數(shù)！所有先手必?cái)〉挠螒虻膕tep值為偶數(shù)！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第20頁(yè)!2022/12/19石家莊二中賈志豪第21頁(yè)CuttingEdges游戲退化版：給出一個(gè)有N個(gè)點(diǎn)的樹(shù)，有一個(gè)點(diǎn)作為樹(shù)的根節(jié)點(diǎn)。

游戲者輪流從樹(shù)中刪去邊，刪去一條邊后，不與根節(jié)點(diǎn)相連的部分將被移走。

誰(shuí)無(wú)邊可刪誰(shuí)輸如何做？如何做？？如何做？？？算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第21頁(yè)!2022/12/19石家莊二中賈志豪第22頁(yè)考慮：已知左圖的SG值，如何求右圖的SG值CuttingEdges游戲根節(jié)點(diǎn)G’G’圖根節(jié)點(diǎn)中間節(jié)點(diǎn)G’G圖由特殊例子給出猜想：SG(

G

)=SG(

G’

)+1算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第22頁(yè)!2022/12/19石家莊二中賈志豪第23頁(yè)CuttingEdges游戲情況一：若去掉與根節(jié)點(diǎn)相連的邊G’根節(jié)點(diǎn)中間節(jié)點(diǎn)G’根節(jié)點(diǎn)中間節(jié)點(diǎn)SG值為0算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第23頁(yè)!2022/12/19石家莊二中賈志豪第24頁(yè)CuttingEdges游戲情況二：若去掉G’中的邊G’根節(jié)點(diǎn)中間節(jié)點(diǎn)根節(jié)點(diǎn)中間節(jié)點(diǎn)G’SG值不確定算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第24頁(yè)!2022/12/19石家莊二中賈志豪第25頁(yè)CuttingEdges游戲更復(fù)雜的情況G’1………G’2G’T根節(jié)點(diǎn)算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第25頁(yè)!2022/12/19石家莊二中賈志豪第26頁(yè)CuttingEdges游戲試著去對(duì)G圖進(jìn)行拆分拆法二（很大膽的嘗試）G’1……G’2G’T…G’1G’2G’T十分完美?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第26頁(yè)!2022/12/19石家莊二中賈志豪第27頁(yè)SayGoodbye謝謝觀看?。?！Thanksforwatching?。?！歡迎提問(wèn)?。?！QuestionTime！??！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第27頁(yè)!2022/12/19石家莊二中賈志豪第28頁(yè)CuttingEdges游戲環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1根節(jié)點(diǎn)根節(jié)點(diǎn)奇環(huán)刪邊后，左右兩個(gè)分支的邊數(shù)同奇偶，異或值不可能為1算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第28頁(yè)!2022/12/19石家莊二中賈志豪第29頁(yè)CuttingEdges游戲環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第29頁(yè)!2022/12/19石家莊二中賈志豪第30頁(yè)CuttingEdges游戲環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊?。?！轉(zhuǎn)換成功?。?！變成了樹(shù)?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第30頁(yè)!2022/12/19石家莊二中賈志豪第31頁(yè)CuttingEdges游戲再次拓展一個(gè)無(wú)相聯(lián)通圖，有一個(gè)點(diǎn)作為圖的根。

游戲者輪流從圖中刪去邊，刪去一條邊后，不與根節(jié)點(diǎn)相連的部分將被移走。

怎么辦？好難！好難??！好難?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第31頁(yè)!2022/12/19石家莊二中賈志豪第32頁(yè)CuttingEdges游戲?qū)τ谂辑h(huán)G’1G’2G’3G’4G’5G’6縮成一個(gè)點(diǎn)?。?！算法合集之《組合游戲略述——淺談SG游戲的若干拓展及共34頁(yè)，您現(xiàn)在瀏覽的是第3