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

組合游戲略述——淺談組合游戲的若干拓展及變形18班賈志豪2023/1/2石家莊二中賈志豪第2頁內(nèi)容概述contentintroduction組合游戲的規(guī)則拓展走完最后一步者輸——Anti-SG游戲和SJ定理可以將一堆石子分成多堆——Multi-SG游戲每一個(gè)可移動(dòng)的棋子都要移動(dòng)——Every-SG游戲

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

無向圖刪邊游戲

每一個(gè)可移動(dòng)的棋子都要移動(dòng)——Every-SG游戲無向圖刪邊游戲2023/1/2石家莊二中賈志豪第3頁Every-SG游戲何為Every-SG游戲？？？有N個(gè)單一游戲，游戲者輪流進(jìn)行決策；游戲者的決策必須滿足：對(duì)于所有還沒有結(jié)束的單一游戲，游戲者必須對(duì)該單一游戲進(jìn)行一步操作；無路可走者輸怎么辦？怎么辦？？怎么辦？？？2023/1/2石家莊二中賈志豪第5頁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來表示2023/1/2石家莊二中賈志豪第6頁Every-SG游戲結(jié)論：先手必勝當(dāng)且僅當(dāng)step值最大的單一游戲?yàn)橄仁直貏儆螒蛩伎迹簊tep值最大的既有先手必勝游戲，又有先手必?cái)∮螒驎r(shí)，是否意味著平局？？？所有先手必勝的游戲的step值為奇數(shù)！所有先手必?cái)〉挠螒虻膕tep值為偶數(shù)！2023/1/2石家莊二中賈志豪第7頁Every-SG游戲發(fā)現(xiàn)寶藏（長與短的博弈）一般的組合游戲只有輸與贏的博弈；而Every-SG游戲又增加了長與短的博弈，這使得Every-SG游戲更有嚼頭，更有味道

輸贏長短2023/1/2石家莊二中賈志豪第8頁CuttingEdges游戲退化版：給出一個(gè)有N個(gè)點(diǎn)的樹，有一個(gè)點(diǎn)作為樹的根節(jié)點(diǎn)。

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

誰無邊可刪誰輸如何做？如何做？？如何做？？？2023/1/2石家莊二中賈志豪第10頁考慮：已知左圖的SG值，如何求右圖的SG值CuttingEdges游戲根節(jié)點(diǎn)G’G’圖根節(jié)點(diǎn)中間節(jié)點(diǎn)G’G圖由特殊例子給出猜想：SG(

G

)=SG(

G’

)+12023/1/2石家莊二中賈志豪第12頁CuttingEdges游戲情況一：若去掉與根節(jié)點(diǎn)相連的邊G’根節(jié)點(diǎn)中間節(jié)點(diǎn)G’根節(jié)點(diǎn)中間節(jié)點(diǎn)SG值為02023/1/2石家莊二中賈志豪第14頁CuttingEdges游戲情況二：若去掉G’中的邊G’根節(jié)點(diǎn)中間節(jié)點(diǎn)根節(jié)點(diǎn)中間節(jié)點(diǎn)G’SG值不確定2023/1/2石家莊二中賈志豪第15頁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’)+12023/1/2石家莊二中賈志豪第16頁CuttingEdges游戲更復(fù)雜的情況G’1………G’2G’T根節(jié)點(diǎn)2023/1/2石家莊二中賈志豪第17頁CuttingEdges游戲根據(jù)樹結(jié)構(gòu)的拓?fù)湫栽囍?duì)G圖進(jìn)行拆分拆法一（一般樹形結(jié)構(gòu)拆法）G’1……G’2G’T…G’1G’2G’T不夠本質(zhì)！??！2023/1/2石家莊二中賈志豪第18頁CuttingEdges游戲試著去對(duì)G圖進(jìn)行拆分拆法二（很大膽的嘗試）G’1……G’2G’T…G’1G’2G’T十分完美！??！2023/1/2石家莊二中賈志豪第20頁SayGoodbye謝謝觀看！?。hanksforwatching

?。?！歡迎提問?。。uestionTime?。。?023/1/2石家莊二中賈志豪第21頁CuttingEdges游戲稍加拓展：A和B輪流從圖中刪邊，刪去一條邊后，不與根節(jié)點(diǎn)相連的部分將被移走。A為先手。圖是通過從基礎(chǔ)樹中加一些邊得到的。

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

不要慌！不要慌??！不要慌！??！2023/1/2石家莊二中賈志豪第23頁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ù)異奇偶，異或值不可能為12023/1/2石家莊二中賈志豪第24頁CuttingEdges游戲環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊！??！2023/1/2石家莊二中賈志豪第26頁CuttingEdges游戲環(huán)的處理成為關(guān)鍵驚人發(fā)現(xiàn)，任何奇環(huán)的SG值為1任何偶環(huán)的SG值為0策略將偶環(huán)刪去，將奇環(huán)替換成一條邊?。?！轉(zhuǎn)換成功?。?！變成了樹?。?！2023/1/2石家莊二中賈志豪第27頁SayGoodbye謝謝觀看?。?！Thanksforwatching

?。?！歡迎提問?。?！QuestionTime?。。?023/1/2石家莊二中賈志豪第28頁CuttingEdges游戲再次拓展一個(gè)無相聯(lián)通圖，有一個(gè)點(diǎn)作為圖的根。

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

怎么辦？好難！好難！！好難?。?！2023/1/2石家莊二中賈志豪第30頁CuttingEdges游戲?qū)τ谂辑h(huán)G’1G’2G’3G’4G’5G’6縮成一個(gè)點(diǎn)?。。?023/1/2石家莊二中賈志豪第31頁CuttingEdges游戲?qū)τ谂辑h(huán)G’1G’2G’3G’4G’5G’6縮成一個(gè)點(diǎn)?。。?023/1/2石家莊二中賈志豪第32頁CuttingEdges游戲?qū)τ谄姝h(huán)G’1G’2G’3G’4G’5縮成點(diǎn)加邊?。?！2023/1/2石家莊二中賈志豪第33頁Cut