組合游戲略述-淺談SG游戲的若干拓展及變形形式

組合游戲略述——淺談SG游戲的若干拓展及變形形式2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第2頁(yè)組合游戲的規(guī)則拓展走完最后一步者輸——Anti-SG游戲和SJ定理可以將一堆石子分成多堆——Multi-SG游戲每一個(gè)可移動(dòng)的棋子都要移動(dòng)——Every-SG游戲

組合游戲的模型變形翻硬幣游戲無(wú)向圖刪邊游戲每一個(gè)可移動(dòng)的棋子都要移動(dòng)——Every-SG游戲無(wú)向圖刪邊游戲2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第3頁(yè)何為Every-SG游戲？？？有N個(gè)單一游戲，游戲者輪流進(jìn)行決策；游戲者的決策必須滿(mǎn)足：對(duì)于所有還沒(méi)有結(jié)束的單一游戲，游戲者必須對(duì)該單一游戲進(jìn)行一步操作；無(wú)路可走者輸怎么辦？怎么辦？？怎么辦？？？2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第4頁(yè)貪心策略：對(duì)于某一個(gè)單一游戲，如果當(dāng)前是先手必勝局，那么先手不會(huì)放棄游戲的勝利?。。∧敲?，游戲者需要做的，就是讓自己可以取得勝利的游戲盡可能長(zhǎng)的玩下去，讓自己不能取得勝利的游戲盡可能短的玩下去?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第5頁(yè)解決方法：對(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)表示2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第6頁(yè)結(jié)論：先手必勝當(dāng)且僅當(dāng)step值最大的單一游戲?yàn)橄仁直貏儆螒蛩伎迹簊tep值最大的既有先手必勝游戲，又有先手必?cái)∮螒驎r(shí)，是否意味著平局？？？所有先手必勝的游戲的step值為奇數(shù)！所有先手必?cái)〉挠螒虻膕tep值為偶數(shù)！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第7頁(yè)發(fā)現(xiàn)寶藏（長(zhǎng)與短的博弈）一般的組合游戲只有輸與贏(yíng)的博弈；而Every-SG游戲又增加了長(zhǎng)與短的博弈，這使得Every-SG游戲更有嚼頭，更有味道

輸贏(yíng)長(zhǎng)短2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第8頁(yè)退化版：給出一個(gè)有N個(gè)點(diǎn)的樹(shù)，有一個(gè)點(diǎn)作為樹(shù)的根節(jié)點(diǎn)。

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

誰(shuí)無(wú)邊可刪誰(shuí)輸如何做？如何做？？如何做？？？2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第9頁(yè)從樹(shù)結(jié)構(gòu)入手??樹(shù)結(jié)構(gòu)是一種特殊的拓?fù)浣Y(jié)構(gòu)從最簡(jiǎn)單的例子入手??根節(jié)點(diǎn)只有一個(gè)分支2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第10頁(yè)考慮：已知左圖的SG值，如何求右圖的SG值根節(jié)點(diǎn)G’G’圖根節(jié)點(diǎn)中間節(jié)點(diǎn)G’G圖由特殊例子給出猜想：SG(

G

)=SG(

G’

)+12023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第11頁(yè)證明猜想（數(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圖2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第12頁(yè)情況一：若去掉與根節(jié)點(diǎn)相連的邊G’根節(jié)點(diǎn)中間節(jié)點(diǎn)G’根節(jié)點(diǎn)中間節(jié)點(diǎn)SG值為02023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第13頁(yè)證明猜想（數(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’中的邊2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第14頁(yè)情況二：若去掉G’中的邊G’根節(jié)點(diǎn)中間節(jié)點(diǎn)根節(jié)點(diǎn)中間節(jié)點(diǎn)G’SG值不確定2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第15頁(yè)根節(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’)+12023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第16頁(yè)更復(fù)雜的情況G’1………G’2G’T根節(jié)點(diǎn)2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第17頁(yè)根據(jù)樹(shù)結(jié)構(gòu)的拓?fù)湫栽囍?duì)G圖進(jìn)行拆分拆法一（一般樹(shù)形結(jié)構(gòu)拆法）G’1……G’2G’T…G’1G’2G’T不夠本質(zhì)?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第18頁(yè)試著去對(duì)G圖進(jìn)行拆分拆法二（很大膽的嘗試）G’1……G’2G’T…G’1G’2G’T十分完美?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第19頁(yè)完美在哪了？？？哦。。。對(duì)應(yīng)NIM取石子模型?。?！G’1……G’2G’T…G’1G’2G’T十分完美?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第20頁(yè)謝謝觀(guān)看！??！Thanksforwatching

?。?！歡迎提問(wèn)?。?！QuestionTime?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第21頁(yè)稍加拓展：A和B輪流從圖中刪邊，刪去一條邊后，不與根節(jié)點(diǎn)相連的部分將被移走。A為先手。圖是通過(guò)從基礎(chǔ)樹(shù)中加一些邊得到的。所有形成的環(huán)保證不共用邊，且只與基礎(chǔ)樹(shù)有一個(gè)公共點(diǎn)。

不要慌！不要慌??！不要慌?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第22頁(yè)環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1根節(jié)點(diǎn)根節(jié)點(diǎn)奇環(huán)刪邊后，左右兩個(gè)分支的邊數(shù)同奇偶，異或值不可能為12023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第23頁(yè)環(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ù)異奇偶，異或值不可能為12023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第24頁(yè)環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第25頁(yè)環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第26頁(yè)環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊?。?！轉(zhuǎn)換成功?。?！變成了樹(shù)！??！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第27頁(yè)謝謝觀(guān)看?。?！Thanksforwatching

?。?！歡迎提問(wèn)?。?！QuestionTime?。。?023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第28頁(yè)再次拓展一個(gè)無(wú)相聯(lián)通圖，有一個(gè)點(diǎn)作為圖的根。

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

怎么辦？好難！好難??！好難?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第29頁(yè)考慮上題給出的提示將環(huán)處理掉即可時(shí)間原因，直接給出方法。2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第30頁(yè)對(duì)于偶環(huán)G’1G’2G’3G’