博弈论之Nim游戏
? ? ? ?OI里，博弈論就是兩個(gè)聰明絕頂?shù)娜送娌还降挠螒颉?/strong>
? ? ? ? Nim游戲是組合游戲(Combinatorial Games)的一種，屬于“Impartial Combinatorial Games”（以下簡(jiǎn)稱(chēng)ICG）。
? ? ? ? 通常的Nim游戲的定義是這樣的：有若干堆石子，每堆石子的數(shù)量都是有限的，合法的移動(dòng)是“選擇一堆石子并拿走若干顆（不能不拿）”，如果輪到某個(gè)人時(shí)所有的石子堆都已經(jīng)被拿空了，則判負(fù)（因?yàn)樗丝虥](méi)有任何合法的移動(dòng)）。
? ? ? ? 我們都知道，對(duì)于N堆石子，判斷第一個(gè)人是否贏是將每個(gè)石子進(jìn)行異或運(yùn)算，如果結(jié)果為0則第一個(gè)人取得必輸，否則必贏。
? ? ? ? 但主要是為什么用異或？為什么等于零則是先者必輸？
? ? ? ??首先先說(shuō)一下大家都知道的定義吧：P-position和N-position。
? ? ? ??P-position：P即Previous，該局面為P-position，則代表著這個(gè)局面先行者必輸，后行者必贏。
? ? ? ? N-position：N即Next，該局面為N-position，則代表著這個(gè)局面的后行者必輸，先行者必贏。
? ? ? ? 很顯然，對(duì)于無(wú)法移動(dòng)的局面（Terminal position）為P-position；可以移動(dòng)到P-position局面的必為N-position局面（就是這個(gè)局面是先行者必輸?shù)脑?#xff0c;它的上一個(gè)局面一定是后行者必輸）；所有移動(dòng)都導(dǎo)致N-position局面的是P-position。
? ? ? ? 也就是說(shuō)，對(duì)于一個(gè)局面A是?P-position還是N-position，如果它的子局面（所謂子局面就是這個(gè)局面的能夠發(fā)展成的后續(xù)局面，比如兩個(gè)石子堆個(gè)數(shù)為（3,3），那么它的子局面為(0,3)(1,3)(2,3)）存在先者必輸P-position的局面，那么局面A就是后者必輸N-position的局面，如果它的子局面全部是后者必輸N-position的局面，那么局面A就是先者必輸P-position的局面（子局面的后者就是局面A的操作者）。
? ? ? ? 為此我們要判斷的就是一開(kāi)始是屬于什么局面，根據(jù)上述定義可知這個(gè)局面的判定取決于它的子局面，而它的子局面又取決于它的子子局面……直到這個(gè)局面能夠獨(dú)立判斷是P-position還是N-position，然后再回溯判斷，對(duì)于這個(gè)遞歸的算法你可能已經(jīng)敏銳地看到有大量重復(fù)的子問(wèn)題了，需要記憶化搜索或DP，這實(shí)際上也就是博弈論的本質(zhì)而已，只是我們存在一種比搜索更優(yōu)的方法——異或。
? ? ? ? 為什么用異或呢？因?yàn)楫惢蛴幸环N我們需要的神奇的性質(zhì)——消去律。
? ? ? ?1.對(duì)于Terminal?position只有一個(gè)，也就是全為0，結(jié)果也為0，故先行者必輸。
? ? ? ?2.某個(gè)局面(a1,a2,...,an)，若a1^a2^......^an=k(k不等于0)，則必有一種局面ai能夠通過(guò)合法的步驟轉(zhuǎn)換為ai'，使結(jié)果變?yōu)?（k二進(jìn)制中的某一位中的1必定是某個(gè)ai貢獻(xiàn)過(guò)來(lái)的），其中ai^k=ai'<ai（ai在k的二進(jìn)制下最高位是1），所以是后行者必輸。
? ? ? 3.某個(gè)局面(a1,a2,...,an)，若a1^a2^......^an=0，若ai能夠通過(guò)合法的步驟轉(zhuǎn)換成另一個(gè)局面ai'使結(jié)果也為0，那么a1^a2^..^ai^...^an=a1^a2^..^ai'^...^an，根據(jù)消去律，得到ai=ai'，這是不合法的移動(dòng)（因?yàn)檫€是它本身），所以是先行者必輸。
? ? ? 而這樣，我們就可以在O（n）內(nèi)知道應(yīng)該是先行還是后行了。
? ? ? 關(guān)于SG函數(shù)，我們先定義一種作用在集合的運(yùn)算mex，定義結(jié)果為該集合中未出現(xiàn)的最小非負(fù)整數(shù)，如mex{0,1,2,4}=3、 mex{2,3,5}=0、mex{}=0。
? ? ??對(duì)于一個(gè)給定的有向無(wú)環(huán)圖，定義關(guān)于圖的每個(gè)頂點(diǎn)的Sprague-Garundy函數(shù)g如下：g(x)=mex{ g(y) | y是x的后繼（就是子局面） }。
? ? ? 實(shí)際上，所以Nim游戲都可以抽象成一個(gè)模型：一個(gè)有向圖中，一個(gè)棋子代表著當(dāng)前局面，每個(gè)頂點(diǎn)代表著每個(gè)局面，而每位選手則負(fù)責(zé)移動(dòng)棋子，直到某個(gè)選手無(wú)法移動(dòng)棋子則為負(fù)。
? ? ?所以對(duì)于SG函數(shù)的性質(zhì)，跟上面所講的1,2,3是一樣的：
? ? ? 1.對(duì)于Terminal?position對(duì)應(yīng)的頂點(diǎn)，就是沒(méi)有出邊，其g（x）=0;
? ? ? 2.若該點(diǎn)ai的g（ai）不為0，則它的后繼里存在一個(gè)頂點(diǎn)ai'它的g（ai'）=0；
? ? ? 3.若該點(diǎn)ai的g（ai）=0；則它的后繼里沒(méi)有一個(gè)頂點(diǎn)ai'它的g（ai'）=0。
? ? ? 事實(shí)上，如果有多堆石子，我們可以把每堆石子都抽象成一個(gè)棋子在圖中移動(dòng)，那么我們所要做的就是講每個(gè)棋子所在頂點(diǎn)的SG值算出來(lái)，異或一下即可。
? ? ? 稍微變一下，有n堆石子，每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數(shù)顆，可以從第3堆及以后石子里取任意顆， 我們可以把它看作3個(gè)子游戲，第1個(gè)子游戲只有一堆x顆石子，每次可以取1、2、3顆，很容易看出x顆石子的局面的SG值是x%4（數(shù)學(xué)歸納法可以證明）。第2個(gè)子游戲也是只有一堆 石子，每次可以取奇數(shù)顆，經(jīng)過(guò)簡(jiǎn)單的畫(huà)圖可以知道這個(gè)游戲有x顆石子時(shí)的SG值是x%2。第3個(gè)游戲有n-2堆石子，就是一個(gè)Nim游戲。對(duì)于原游戲的每 個(gè)局面，把三個(gè)子游戲的SG值異或一下就得到了整個(gè)游戲的SG值，然后就可以根據(jù)這個(gè)SG值判斷是否有必勝策略以及做出決策了。
? ? ?g（x）=b，說(shuō)明當(dāng)前局面可以移動(dòng)到g（a）=b-1，b-2，b-3.......1,0上。
? ? ? 所以，對(duì)于我們來(lái)說(shuō)，我們是將一個(gè)復(fù)雜的游戲分成許許多多若干個(gè)簡(jiǎn)單的小游戲，再分別求出SG值，再全部異或起來(lái)就是原游戲的SG值了。
? ? ? 關(guān)于題目所說(shuō)的完美操作，雙方足夠聰明，指的就是當(dāng)前這個(gè)局面如果能夠贏得這場(chǎng)游戲的話，這個(gè)人就會(huì)順著這個(gè)能夠贏的這條路徑進(jìn)行下去，就是N-position。
轉(zhuǎn)載于:https://www.cnblogs.com/Lanly/p/7262998.html
總結(jié)
- 上一篇： 肽键肽链内部分的计算机术语大全,生化资料
- 下一篇： 计算机无法使用光驱启动,电脑BIOS怎么