Nim游戲和SG函數(shù)是什么

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)Nim游戲和SG函數(shù)是什么，文章內(nèi)容豐富且以專(zhuān)業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

一、Nim游戲

重點(diǎn)結(jié)論：對(duì)于一個(gè)Nim游戲的局面(a1,a2,...,an)，它是P-position當(dāng)且僅當(dāng)a1^a2^...^an=0，其中^表示位異或(xor)運(yùn)算。

Nim游戲是博弈論中最經(jīng)典的模型（之一？），它又有著十分簡(jiǎn)單的規(guī)則和無(wú)比優(yōu)美的結(jié)論，由這個(gè)游戲開(kāi)始了解博弈論恐怕是最合適不過(guò)了。

Nim 游戲是組合游戲(Combinatorial Games)的一種，準(zhǔn)確來(lái)說(shuō)，屬于“Impartial Combinatorial Games”（以下簡(jiǎn)稱(chēng)ICG）。滿(mǎn)足以下條件的游戲是ICG（可能不太嚴(yán)謹(jǐn)）：1、有兩名選手；2、兩名選手交替對(duì)游戲進(jìn)行移動(dòng)(move)，每次一 步，選手可以在（一般而言）有限的合法移動(dòng)集合中任選一種進(jìn)行移動(dòng)；3、對(duì)于游戲的任何一種可能的局面，合法的移動(dòng)集合只取決于這個(gè)局面本身，不取決于輪 到哪名選手操作、以前的任何操作、骰子的點(diǎn)數(shù)或者其它什么因素； 4、如果輪到某名選手移動(dòng)，且這個(gè)局面的合法的移動(dòng)集合為空（也就是說(shuō)此時(shí)無(wú)法進(jìn)行移動(dòng)），則這名選手負(fù)。根據(jù)這個(gè)定義，很多日常的游戲并非ICG。例如 象棋就不滿(mǎn)足條件3，因?yàn)榧t方只能移動(dòng)紅子，黑方只能移動(dòng)黑子，合法的移動(dòng)集合取決于輪到哪名選手操作。

通常的Nim游戲的定義是這樣的：有若干堆石子，每堆石子的數(shù)量都是有限的，合法的移動(dòng)是“選擇一堆石子并拿走若干顆（不能不拿）”，如果輪到某個(gè)人時(shí)所有的石子堆都已經(jīng)被拿空了，則判負(fù)（因?yàn)樗丝虥](méi)有任何合法的移動(dòng)）。

這 游戲看上去有點(diǎn)復(fù)雜，先從簡(jiǎn)單情況開(kāi)始研究吧。如果輪到你的時(shí)候，只剩下一堆石子，那么此時(shí)的必勝策略肯定是把這堆石子全部拿完一顆也不給對(duì)手剩，然后對(duì) 手就輸了。如果剩下兩堆不相等的石子，必勝策略是通過(guò)取多的一堆的石子將兩堆石子變得相等，以后如果對(duì)手在某一堆里拿若干顆，你就可以在另一堆中拿同樣多 的顆數(shù)，直至勝利。如果你面對(duì)的是兩堆相等的石子，那么此時(shí)你是沒(méi)有任何必勝策略的，反而對(duì)手可以遵循上面的策略保證必勝。如果是三堆石子……好像已經(jīng)很 難分析了，看來(lái)我們必須要借助一些其它好用的（最好是程式化的）分析方法了，或者說(shuō)，我們最好能夠設(shè)計(jì)出一種在有必勝策略時(shí)就能找到必勝策略的算法。

定 義P-position和N-position，其中P代表Previous，N代表Next。直觀(guān)的說(shuō)，上一次move的人有必勝策略的局面是P- position，也就是“后手可保證必勝”或者“先手必?cái)　保F(xiàn)在輪到move的人有必勝策略的局面是N-position，也就是“先手可保證必勝 ”。更嚴(yán)謹(jǐn)?shù)亩x是：1.無(wú)法進(jìn)行任何移動(dòng)的局面（也就是terminal position）是P-position；2.可以移動(dòng)到P-position的局面是N-position；3.所有移動(dòng)都導(dǎo)致N-position 的局面是P-position。

按照這個(gè)定義，如果局面不可能重現(xiàn)，或者說(shuō)positions的集合可以進(jìn)行拓?fù)渑判?，那么每個(gè)position或者是P-position或者是N-position，而且可以通過(guò)定義計(jì)算出來(lái)。

以 Nim游戲?yàn)槔齺?lái)進(jìn)行一下計(jì)算。比如說(shuō)我剛才說(shuō)當(dāng)只有兩堆石子且兩堆石子數(shù)量相等時(shí)后手有必勝策略，也就是這是一個(gè)P-position，下面我們依靠定 義證明一下(3,3)是一個(gè)P是一個(gè)P是一個(gè)P-position。首先(3,3)的子局面（也就是通過(guò)合法移動(dòng)可以導(dǎo)致的局面）有(0,3)(1,3) (2,3)（顯然交換石子堆的位置不影響其性質(zhì)，所以把(x,y)和(y,x)看成同一種局面），只需要計(jì)算出這三種局面的性質(zhì)就可以了。 (0,3)的子局面有(0,0)、(0,1)、(0,2)，其中(0,0)顯然是P-position，所以(0,3)是N-position（只要找到 一個(gè)是P-position的子局面就能說(shuō)明是N-position）。(1,3)的后繼中(1,1)是P-position（因?yàn)?1,1)的唯一子局 面(0,1)是N-position），所以(1,3)也是N-position。同樣可以證明(2,3)是N-position。所以(3,3)的所有 子局面都是N-position，它就是P-position。通過(guò)一點(diǎn)簡(jiǎn)單的數(shù)學(xué)歸納，可以嚴(yán)格的證明“有兩堆石子時(shí)的局面是P-position當(dāng)且 僅當(dāng)這兩堆石子的數(shù)目相等”。

根據(jù)上面這個(gè)過(guò)程，可以得到一個(gè)遞歸的算法——對(duì)于當(dāng)前的局面，遞歸計(jì)算它的所有子局面的性質(zhì)，如果存在某 個(gè)子局面是P-position，那么向這個(gè)子局面的移動(dòng)就是必勝策略。當(dāng)然，可能你已經(jīng)敏銳地看出有大量的重疊子問(wèn)題，所以可以用DP或者記憶化搜索的 方法以提高效率（簡(jiǎn)單的博弈問(wèn)題想到這一步就可以了）。但問(wèn)題是，利用這個(gè)算法，對(duì)于某個(gè)Nim游戲的局面(a1,a2,...,an)來(lái)說(shuō)，要想判斷它 的性質(zhì)以及找出必勝策略，需要計(jì)算O(a1*a2*...*an)個(gè)局面的性質(zhì)，不管怎樣記憶化都無(wú)法降低這個(gè)時(shí)間復(fù)雜度。所以我們需要更高效的判斷 Nim游戲的局面的性質(zhì)的方法。

直接說(shuō)結(jié)論好了。(Bouton's Theorem)對(duì)于一個(gè)Nim游戲的局面(a1,a2,...,an)，它是P-position當(dāng)且僅當(dāng)a1^a2^...^an=0，其中^表示異 或(xor)運(yùn)算。怎么樣，是不是很神奇？我看到它的時(shí)候也覺(jué)得很神奇，完全沒(méi)有道理的和異或運(yùn)算扯上了關(guān)系。但這個(gè)定理的證明卻也不復(fù)雜，基本上就是按 照兩種position的證明來(lái)的。

根據(jù)定義，證明一種判斷position的性質(zhì)的方法的正確性，只需證明三個(gè)命題： 1、這個(gè)判斷將所有terminal position判為P-position；2、根據(jù)這個(gè)判斷被判為N-position的局面一定可以移動(dòng)到某個(gè)P-position；3、根據(jù)這個(gè)判 斷被判為P-position的局面無(wú)法移動(dòng)到某個(gè)P-position。

第一個(gè)命題顯然，terminal position只有一個(gè)，就是全0，異或仍然是0。

第 二個(gè)命題，對(duì)于某個(gè)局面(a1,a2,...,an)，若a1^a2^...^an!=0，一定存在某個(gè)合法的移動(dòng)，將ai改變成ai'后滿(mǎn)足 a1^a2^...^ai'^...^an=0。不妨設(shè)a1^a2^...^an=k，則一定存在某個(gè)ai，它的二進(jìn)制表示在k的最高位上是1（否則k的 最高位那個(gè)1是怎么得到的）。這時(shí)ai^k<ai一定成立。則我們可以將ai改變成ai'=ai^k，此時(shí) a1^a2^...^ai'^...^an=a1^a2^...^an^k=0。

第三個(gè)命題，對(duì)于某個(gè)局面 (a1,a2,...,an)，若a1^a2^...^an=0，一定不存在某個(gè)合法的移動(dòng)，將ai改變成ai'后滿(mǎn)足 a1^a2^...^ai'^...^an=0。因?yàn)楫惢蜻\(yùn)算滿(mǎn)足消去率，由a1^a2^...^an=a1^a2^...^ai'^...^an可以得 到ai=ai'。所以將ai改變成ai'不是一個(gè)合法的移動(dòng)。證畢。

根據(jù)這個(gè)定理，我們可以在O(n)的時(shí)間內(nèi)判斷一個(gè)Nim的局面的性質(zhì)，且如果它是N-position，也可以在O(n)的時(shí)間內(nèi)找到所有的必勝策略。Nim問(wèn)題就這樣基本上完美的解決了。

二、Sprague-Grundy 函數(shù)

上一期的文章里我們仔細(xì)研究了Nim游戲，并且了解了找出必勝策略的方法。但如果把Nim的規(guī)則略加改變，你還能很快找出必勝策略嗎？比如說(shuō)：有n堆石子， 每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數(shù)顆，可以從第3堆及以后石子里取任意顆……這時(shí)看上去問(wèn)題復(fù)雜了很多，但相信你如果 掌握了本節(jié)的內(nèi)容，類(lèi)似的千變?nèi)f化的問(wèn)題都是不成問(wèn)題的。

現(xiàn)在我們來(lái)研究一個(gè)看上去似乎更為一般的游戲：給定一個(gè)有向無(wú)環(huán)圖和一個(gè)起始頂 點(diǎn)上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行移動(dòng)，無(wú)法移動(dòng)者判負(fù)。事實(shí)上，這個(gè)游戲可以認(rèn)為是所有Impartial Combinatorial Games的抽象模型。也就是說(shuō)，任何一個(gè)ICG都可以通過(guò)把每個(gè)局面看成一個(gè)頂點(diǎn)，對(duì)每個(gè)局面和它的子局面連一條有向邊來(lái)抽象成這個(gè)“有向圖游戲”。下 面我們就在有向無(wú)環(huán)圖的頂點(diǎn)上定義Sprague-Garundy函數(shù)。

首先定義mex(minimal excludant)運(yùn)算，這是施加于一個(gè)集合的運(yùn)算，表示最小的不屬于這個(gè)集合的非負(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的后繼 }。

來(lái) 看一下SG函數(shù)的性質(zhì)。首先，所有的terminal position所對(duì)應(yīng)的頂點(diǎn)，也就是沒(méi)有出邊的頂點(diǎn)，其SG值為0，因?yàn)樗暮罄^集合是空集。然后對(duì)于一個(gè)g(x)=0的頂點(diǎn)x，它的所有后繼y都滿(mǎn)足 g(y)!=0。對(duì)于一個(gè)g(x)!=0的頂點(diǎn)，必定存在一個(gè)后繼y滿(mǎn)足g(y)=0。

以上這三句話(huà)表明，頂點(diǎn)x所代表的postion 是P-position當(dāng)且僅當(dāng)g(x)=0（跟P-positioin/N-position的定義的那三句話(huà)是完全對(duì)應(yīng)的）。我們通過(guò)計(jì)算有向無(wú)環(huán)圖 的每個(gè)頂點(diǎn)的SG值，就可以對(duì)每種局面找到必勝策略了。但SG函數(shù)的用途遠(yuǎn)沒(méi)有這樣簡(jiǎn)單。如果將有向圖游戲變復(fù)雜一點(diǎn)，比如說(shuō)，有向圖上并不是只有一枚棋 子，而是有n枚棋子，每次可以任選一顆進(jìn)行移動(dòng)，這時(shí)，怎樣找到必勝策略呢？

讓我們?cè)賮?lái)考慮一下頂點(diǎn)的SG值的意義。當(dāng)g(x)=k時(shí)， 表明對(duì)于任意一個(gè)0<=i<k，都存在x的一個(gè)后繼y滿(mǎn)足g(y)=i。也就是說(shuō)，當(dāng)某枚棋子的SG值是k時(shí)，我們可以把它變成0、變成 1、……、變成k-1，但絕對(duì)不能保持k不變。不知道你能不能根據(jù)這個(gè)聯(lián)想到Nim游戲，Nim游戲的規(guī)則就是：每次選擇一堆數(shù)量為k的石子，可以把它變 成0、變成1、……、變成k-1，但絕對(duì)不能保持k不變。這表明，如果將n枚棋子所在的頂點(diǎn)的SG值看作n堆相應(yīng)數(shù)量的石子，那么這個(gè)Nim游戲的每個(gè)必 勝策略都對(duì)應(yīng)于原來(lái)這n枚棋子的必勝策略。

對(duì)于n個(gè)棋子，設(shè)它們對(duì)應(yīng)的頂點(diǎn)的SG值分別為(a1,a2,…,an)，再設(shè)局面 (a1,a2,…,an)時(shí)的Nim游戲的一種必勝策略是把a(bǔ)i變成k，那么原游戲的一種必勝策略就是把第i枚棋子移動(dòng)到一個(gè)SG值為k的頂點(diǎn)。這聽(tīng)上去 有點(diǎn)過(guò)于神奇——怎么繞了一圈又回到Nim游戲上了。

其實(shí)我們還是只要證明這種多棋子的有向圖游戲的局面是P-position當(dāng)且僅當(dāng)所有棋子所在的位置的SG函數(shù)的異或?yàn)?。這個(gè)證明與上節(jié)的Bouton’s Theorem幾乎是完全相同的，只需要適當(dāng)?shù)母膸讉€(gè)名詞就行了。

剛才，我為了使問(wèn)題看上去更容易一些，認(rèn)為n枚棋子是在一個(gè)有向圖上移動(dòng)。但如果不是在一個(gè)有向圖上，而是每個(gè)棋子在一個(gè)有向圖上，每次可以任選一個(gè)棋子（也就是任選一個(gè)有向圖）進(jìn)行移動(dòng)，這樣也不會(huì)給結(jié)論帶來(lái)任何變化。

所 以我們可以定義有向圖游戲的和(Sum of Graph Games)：設(shè)G1、G2、……、Gn是n個(gè)有向圖游戲，定義游戲G是G1、G2、……、Gn的和(Sum)，游戲G的移動(dòng)規(guī)則是：任選一個(gè)子游戲Gi 并移動(dòng)上面的棋子。Sprague-Grundy Theorem就是：g(G)=g(G1)^g(G2)^…^g(Gn)。也就是說(shuō)，游戲的和的SG函數(shù)值是它的所有子游戲的SG函數(shù)值的異或。

再考慮在本文一開(kāi)頭的一句話(huà)：任何一個(gè)ICG都可以抽象成一個(gè)有向圖游戲。所以“SG函數(shù)”和“游戲的和”的概念就不是局限于有向圖游戲。我們給每個(gè)ICG 的每個(gè)position定義SG值，也可以定義n個(gè)ICG的和。所以說(shuō)當(dāng)我們面對(duì)由n個(gè)游戲組合成的一個(gè)游戲時(shí)，只需對(duì)于每個(gè)游戲找出求它的每個(gè)局面的 SG值的方法，就可以把這些SG值全部看成Nim的石子堆，然后依照找Nim的必勝策略的方法來(lái)找這個(gè)游戲的必勝策略了！

回到本文開(kāi)頭的 問(wèn)題。有n堆石子，每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數(shù)顆，可以從第3堆及以后石子里取任意顆……我們可以把它看作3個(gè) 子游戲，第1個(gè)子游戲只有一堆石子，每次可以取1、2、3顆，很容易看出x顆石子的局面的SG值是x%4。第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值判斷是否有必勝策略以及做出決策了。其實(shí)看作3個(gè)子游戲還是保守了些，干脆看作n個(gè) 子游戲，其中第1、2個(gè)子游戲如上所述，第3個(gè)及以后的子游戲都是“1堆石子，每次取幾顆都可以”，稱(chēng)為“任取石子游戲”，這個(gè)超簡(jiǎn)單的游戲有x顆石子的 SG值顯然就是x。其實(shí)，n堆石子的Nim游戲本身不就是n個(gè)“任取石子游戲”的和嗎？

所以，對(duì)于我們來(lái)說(shuō)，SG函數(shù)與“游戲的和”的概念不是讓我們?nèi)ソM合、制造稀奇古怪的游戲，而是把遇到的看上去有些復(fù)雜的游戲試圖分成若干個(gè)子游戲，對(duì)于每個(gè)比原游戲簡(jiǎn)化很多的子游戲找出它的SG函數(shù)，然后全部異或起來(lái)就得到了原游戲的SG函數(shù)，就可以解決原游戲了。

上述就是小編為大家分享的Nim游戲和SG函數(shù)是什么了，如果剛好有類(lèi)似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。