ICG

給定一個(gè)有向無環(huán)圖和一個(gè)起始頂點(diǎn)上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行移動(dòng)，無法移動(dòng)者判負(fù)。

這個(gè)游戲可以認(rèn)為是所有 Impartial Combinatorial Games 的抽象模型。也就是說，任何一個(gè) ICG 都可以通過把每個(gè)局面看成一個(gè)頂點(diǎn)，對每個(gè)局面和它的子局面連一條有向邊來抽象成這個(gè)“有向圖游戲”。

滿足以下條件的游戲是ICG：

1、有兩名選手；

2、兩名選手交替對棋子進(jìn)行移動(dòng)(move)，每次一步，選手可以在有限的合法移動(dòng)集合中任選一種進(jìn)行移動(dòng)；
3、對于游戲的任何一種可能的局面，合法的移動(dòng)集合只取決于這個(gè)局面本身，不取決于輪到哪名選手操作、以前的任何操作、骰子的點(diǎn)數(shù)或者其它什么因素；?
4、如果輪到某名選手移動(dòng)，且這個(gè)局面的合法的移動(dòng)集合為空（也就是說此時(shí)無法進(jìn)行移動(dòng)），則這名選手負(fù)。

?

下 面我們就在有向無環(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。

對于一個(gè)給定的有向無環(huán)圖，定義關(guān)于圖的每個(gè)頂點(diǎn)的 Sprague-Grundy 函數(shù) g（x）如下：g(x)=mex{ g(y) | y 是 x 的后繼 }。

SG 函數(shù)的性質(zhì)：

1.首先，所有的 terminal position 所對應(yīng)的頂點(diǎn)，也就是沒有出邊的頂點(diǎn)，其 SG 值為 0，因?yàn)樗暮罄^集合是空集。

2.然后對于一個(gè) g(x)=0 的頂點(diǎn) x，它的所有后繼 y 都滿足 g(y)!=0。

3.對于一個(gè) g(x)!=0 的頂點(diǎn)，必定存在一個(gè)后繼 y 滿足 g(y)=0。

以上這三句話表明，頂點(diǎn) x 所代表的 postion 是 P-position 當(dāng)且僅當(dāng) g(x)=0。

我們通過計(jì)算有向無環(huán)圖的每個(gè)頂點(diǎn)的 SG 值，就可以對每種局面找到必勝策略了。

?

Nim 游戲的規(guī)則：

有K堆各N個(gè)石子，兩個(gè)人輪流從某一堆中取出任意多個(gè)石子，每次至少取一個(gè)，取走最后石子的人獲勝。

分析：

最后一個(gè)奇異局勢是(0,0...,0)，無論誰面對奇異局面，都是必?cái)〉摹Ａ硪粋€(gè)奇異局勢是(n,n,0...0)，只要對手總是和我拿走一樣多的物品，最后會(huì)面對(0,0...,0)。

奇異局勢的判定：

????對于一個(gè)普通的局勢，如何判斷其是不是奇異局勢？對于一個(gè)局勢(s1,s2,...sk)，對所有石子個(gè)數(shù)做位的異或運(yùn)算，s1^s2^s3^...^sk，如果結(jié)果為0，那么局勢(s1,s2,...sk)就是奇異局勢（平衡），否則就不是（非平衡）。

????從二進(jìn)制位的角度上說，奇異局勢時(shí)，每一個(gè)bit位上1的個(gè)數(shù)都是偶數(shù)。

玩家的策略：

????就是把面對的非奇異局勢變?yōu)槠娈惥謩萘艚o對方。也就是從某一堆取出若干石子之后，使得每一個(gè)bit位上1的個(gè)數(shù)都變?yōu)榕紨?shù)，這樣的取法一般不只有一種。可以將其中一堆的石子數(shù)變?yōu)槠渌咽訑?shù)的位異或運(yùn)算的值（如果這個(gè)值比原來的石子數(shù)小的話）。

每次選擇 一堆數(shù)量為 k 的石子，可以把它變成 0、變成 1、……、變成 k-1，但絕對不能保持 k不變。

變形

假設(shè)不是一枚棋子，而是n枚棋子，如何獲勝？

讓我們再來考慮一下頂點(diǎn)的 SG 值的意義。當(dāng) g(x)=k 時(shí)，表明對于任意一個(gè)0<=i<k，都存在 x 的一個(gè)后繼 y 滿足 g(y)=i。

也 就是說，當(dāng)某枚棋子的 SG 值是 k 時(shí)，我們可以把它變成 0、變成 1、……、變成 k-1，但絕對不能保持 k 不變。

這表明，如果將 n 枚棋子所在的頂 點(diǎn)的 SG 值看作 n 堆相應(yīng)數(shù)量的石子，那么這個(gè) Nim 游戲的每個(gè)必勝策略都對應(yīng)于原來這 n 枚棋子的必勝策略！

對于 n 個(gè)棋子，設(shè)它們對應(yīng)的頂點(diǎn)的 SG 值分別為(a1,a2,…,an)，再設(shè)局面(a1,a2,…,an)時(shí)的 Nim 游戲的一種必勝策略是把 ai 變成 k，那么原游戲的一種必勝策略就是把第 i 枚棋子移動(dòng)到一個(gè) SG 值為 k 的頂點(diǎn)。

其實(shí)我們還是只要證明這種多棋子的有向圖游戲的局面是 P-position 當(dāng)且僅當(dāng)所有棋子所在的位置的 SG 函數(shù)的異或?yàn)?0。

這個(gè)證明與上節(jié)的 Bouton’s Theorem 幾乎是完全相同的，只需要適當(dāng)?shù)母膸讉€(gè)名詞就行了。

剛才，為了使問題看上去更容易一些，認(rèn)為 n 枚棋子是在一個(gè)有向圖上移動(dòng)，但如果不是在一個(gè)有向圖上，而是每個(gè)棋子在一個(gè)有向圖上，每次可 以任選一個(gè)棋子（也就是任選一個(gè)有向圖）進(jìn)行移動(dòng)，這樣也不會(huì)給結(jié)論帶來任何變化。 所以我們可以定義有向圖游戲的和(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)。即游戲的和的 SG 函數(shù)值是它的所有子游戲的 SG 函數(shù)值的異或。

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

?

NIM游戲例題

有 n 堆石子，每次可以從第 1 堆石子里取 1 顆、2 顆或 3顆，可以從第 2 堆石子里取奇數(shù)顆，可以從第 3 堆及以后石子里取任意顆，先手必勝輸出Y，否則輸出N

分析：

我們可以把它看作 3 個(gè)子游戲：

第 1 個(gè)子游戲只有一堆石子，每次可以取 1、2、3顆，很容易看出 x 顆石子的局面的 SG 值是 x%4。

第 2 個(gè)子游戲也是只有一 堆 石子，每次可以取奇數(shù)顆，經(jīng)過簡單的畫圖可以知道這個(gè)游戲有 x 顆石子時(shí)的 SG值是 x%2。

第 3 個(gè)游戲有 n-2 堆石子，就是一個(gè) Nim 游戲。

對于原游戲的每 個(gè)局面，把三個(gè)子游戲的 SG 值異或一下，就得到了整個(gè)游戲的 SG 值，然后就可以根據(jù)這個(gè) SG 值判斷是否有必勝策略以及做出決策了。

其實(shí)看作 3 個(gè)子游戲還是保守了些，干脆看作 n 個(gè)子游戲，其中第 1、2 個(gè)子游戲如上所述，第 3 個(gè)及以后的子游戲都是“1 堆石子，每次取幾顆都可以”，稱為“任取石子游戲”，這個(gè)超簡 單的游戲有 x 顆石子的 SG 值顯然就是 x。其實(shí)，n 堆石子的 Nim 游戲本身不就是 n 個(gè)“任取石子游戲”的和嗎？

#include<bits/stdc++.h> using namespace std;int main() {ios::sync_with_stdio(false);int n,t;cin>>t;while(t--){cin>>n;int x,ans=0;int sg1=0,sg2=0,sg3=0;cin>>x;//第一堆sg1=x%4;cin>>x;//第二堆sg2=x%2;for(int i=0;i<n-2;i++){cin>>x;sg3^=x;}ans=sg1^sg2^sg3;if(ans==0)//必?cái)rintf("N\n");elseprintf("Y\n");}return 0;}

總結(jié)

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

尋找必?cái)B(tài)

必?cái)B(tài)就是“在對方使用最優(yōu)策略時(shí)，無論做出什么決策都會(huì)導(dǎo)致失敗的局面”。其他的局面稱為勝態(tài)，值得注意的是在 勝態(tài)下做出錯(cuò)誤的決策也有可能導(dǎo)致失敗。此類博弈問題的精髓就是讓對手永遠(yuǎn)面對必?cái)B(tài)。

必?cái)B(tài)和勝態(tài)有著如下性質(zhì)：

1、若面臨末狀態(tài)者為獲勝則末狀態(tài)為勝態(tài)否則末狀態(tài)為必?cái)B(tài)。

2、一個(gè)局面是勝態(tài)的充要條件是該局面進(jìn)行某種決策后會(huì)成為必?cái)B(tài)。

3、一個(gè)局面是必?cái)B(tài)的充要條件是該局面無論進(jìn)行何種決策均會(huì)成為勝態(tài)。

這三條性質(zhì)正是博弈樹的原理，但博弈樹是通過計(jì)算每一個(gè)局面是勝態(tài)還是必?cái)B(tài)來解題，這樣在局面數(shù)很多的情況下是很難做到的，此時(shí)，我們可以利用人腦的推演歸納能力找 到必?cái)B(tài)的共性，就可以比較好的解決此類問題了。

解題思路

分析初始局勢是屬于哪種形態(tài)，然后根據(jù)博弈中的些結(jié)論去推導(dǎo)當(dāng)前狀態(tài)是否是必?cái)B(tài)。

與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的NIM博弈+SG函数求解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。