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

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

組合游戲的模型變形翻硬幣游戲無向圖刪邊游戲每一個可移動的棋子都要移動——Every-SG游戲無向圖刪邊游戲2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第3頁何為Every-SG游戲？？？有N個單一游戲，游戲者輪流進行決策；游戲者的決策必須滿足：對于所有還沒有結(jié)束的單一游戲，游戲者必須對該單一游戲進行一步操作；無路可走者輸怎么辦？怎么辦？？怎么辦？？？2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第4頁貪心策略：對于某一個單一游戲，如果當(dāng)前是先手必勝局，那么先手不會放棄游戲的勝利?。。∧敲?，游戲者需要做的，就是讓自己可以取得勝利的游戲盡可能長的玩下去，讓自己不能取得勝利的游戲盡可能短的玩下去?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第5頁解決方法：對于SG值為0的點，我們需要知道最少幾步能將游戲帶入終止?fàn)顟B(tài)；對于SG值不為0的點，我們需要知道最多幾步游戲會被帶入終止?fàn)顟B(tài)；以上兩個值，我們都用step來表示2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第6頁結(jié)論：先手必勝當(dāng)且僅當(dāng)step值最大的單一游戲為先手必勝游戲思考：step值最大的既有先手必勝游戲，又有先手必敗游戲時，是否意味著平局？？？所有先手必勝的游戲的step值為奇數(shù)！所有先手必敗的游戲的step值為偶數(shù)！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第7頁發(fā)現(xiàn)寶藏（長與短的博弈）一般的組合游戲只有輸與贏的博弈；而Every-SG游戲又增加了長與短的博弈，這使得Every-SG游戲更有嚼頭，更有味道

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

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

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

G

)=SG(

G’

)+12023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第11頁證明猜想（數(shù)學(xué)歸納法）即證：它的后繼狀態(tài)的SG值為0到SG(G')的所有值；以樹中節(jié)點個數(shù)作為階段；一個節(jié)點和兩個節(jié)點顯然成立；假設(shè)N個節(jié)點時成立，情況一：若去掉與根節(jié)點相連的邊根節(jié)點中間節(jié)點G’G圖2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第12頁情況一：若去掉與根節(jié)點相連的邊G’根節(jié)點中間節(jié)點G’根節(jié)點中間節(jié)點SG值為02023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第13頁證明猜想（數(shù)學(xué)歸納法）以樹中節(jié)點個數(shù)作為階段；一個節(jié)點和兩個節(jié)點顯然成立；假設(shè)N個節(jié)點時成立，情況一：若去掉與根節(jié)點相連的邊情況二：若去掉G’中的邊2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第14頁情況二：若去掉G’中的邊G’根節(jié)點中間節(jié)點根節(jié)點中間節(jié)點G’SG值不確定2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第15頁根節(jié)點G’SG值為0到SG(

G’

)-1，取不到SG(

G’

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

)，取不到SG(G’

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

由歸納假設(shè)定理：SG(G)=SG(G’)+12023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第16頁更復(fù)雜的情況G’1………G’2G’T根節(jié)點2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第17頁根據(jù)樹結(jié)構(gòu)的拓撲性試著去對G圖進行拆分拆法一（一般樹形結(jié)構(gòu)拆法）G’1……G’2G’T…G’1G’2G’T不夠本質(zhì)！?。?023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第18頁試著去對G圖進行拆分拆法二（很大膽的嘗試）G’1……G’2G’T…G’1G’2G’T十分完美?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第19頁完美在哪了？？？哦。。。對應(yīng)NIM取石子模型?。?！G’1……G’2G’T…G’1G’2G’T十分完美?。?！2023/6/27組合游戲略述——淺談SG游戲的若干拓展及變形形式第20頁謝謝觀看！??！Thanksforwatching

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

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

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

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

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