?

1、Nim游戲：有3堆火柴，分別為a,b,c根，記為狀態(tài)(a,b,c)。每次一個游戲者可以從任意一堆中拿走至少一根火柴，也可以整堆拿走，但不能從多堆火柴中同時拿走。無法拿火柴的游戲者輸。

?

2、組合游戲：Nim游戲其實就是組合游戲的一種，它滿足：

? a\兩個游戲者輪流操作

? b\游戲狀態(tài)有限。并且不管雙方怎么走，都不會出現(xiàn)以前出現(xiàn)過的狀態(tài)。

? c\誰不能操作誰輸，另一個獲勝。

?

3、狀態(tài)圖：為了方便分析，我們可以把游戲中的狀態(tài)畫成圖。每個節(jié)點是一個狀態(tài)，每條邊代表從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)的操作（我們只討論公平游戲，即：一個游戲者可以把狀態(tài)A變?yōu)闋顟B(tài)B，另一個游戲者也可以。）

?

4、兩條規(guī)則：

? a\一個狀態(tài)必敗當(dāng)且僅當(dāng)它所有的后繼都是必勝狀態(tài)。

? b\一個狀態(tài)必勝當(dāng)且僅當(dāng)它的后繼有一個是必敗狀態(tài)。

? *\特別的：沒有后繼的狀態(tài)是必敗狀態(tài)。

? 有了這兩條規(guī)則，就可以用遞推的方法判斷整個圖的每一個結(jié)點是必勝態(tài)還是必敗態(tài)。（注意到狀態(tài)圖都是無環(huán)的，所以如果按照拓?fù)渑判虻哪嫘蜻M(jìn)行判斷，在判斷每個節(jié)點的時候，他的所有后繼都已經(jīng)判斷過啦。）

?

5、舉個例子：

? a\Ferguson游戲：有2個盒子，一開始其中一個有m顆糖而另一個有n顆糖，即狀態(tài)（m,n）。每次操作是將一個盒子清空而把另一個盒子的一些糖拿到被清空的盒子中，使得2個盒子至少各有1顆糖。顯然唯一的終止態(tài)為（1,1）。如果最后移動的游戲者獲勝，那么狀態(tài)為（m,n）的先手勝還是敗？||-><-||根據(jù)第四點的規(guī)律我們按照k=m+n從小到大的順序判斷即可。下面代碼輸出所有k<20的必敗態(tài)，由于(m,n)和（n,m）等價，這里只輸出了n<=m的必敗態(tài)。

?

1 #include<iostream> 2 using namespace std; 3 4 const int maxn = 100; 5 int winning[maxn][maxn]; 6 int main(){ 7 winning[1][1]=false; 8 for(int k=3;k<20;k++){//k由小到大枚舉 9 for(int n=1;n<k;n++){//對于每個k枚舉n 10 int m=k-n;//計算出狀態(tài)k時的對應(yīng)m 11 winning[n][m]=false;//先默認(rèn)為輸 12 for(int i=1;i<n;i++)//分析winning[n][m]后繼之m倒掉 13 if(!winning[i][n-i]){winning[n][m]=true;break;} 14 for(int i=1;i<m;i++)//分析winning[n][m]后繼之n倒掉 15 if(!winning[i][m-i]){winning[n][m]=true;break;} 16 if(n<=m && !winning[n][m])cout<<n<<' '<<m<<'\n'; 17 } 18 }return 0; 19 } View Code

?

6、Nim sum：如果用上面相同的方法逆向判斷所有節(jié)點，當(dāng)a,b,c很大時，計算復(fù)雜度將會很高。其實早在1902年L.Bouton就提出了這樣一個定理：狀態(tài)（a,b,c）為必敗態(tài)當(dāng)且僅當(dāng)a^b^c=0,這里的操作是二進(jìn)制逐位異或操作（相同為0，不同為1），也成為Nim和（Nim sum）。

?

7、組合游戲的和：

　a\定義：假設(shè)有k個組合游戲G1,G2,……,Gk,可以定義一個新游戲，在每個回合中，當(dāng)前游戲者可以任選一個子游戲Gi進(jìn)行一次合法操作，讓其他游戲的局面保持不變，不能操作的游戲者輸。這個新游戲稱為G1,G2，……，Gk的和。

? b\Nim:這樣Nim游戲其實就是3個組合游戲G(從一堆火柴中拿走至少一根也可整堆拿走，無法拿的輸)的和。為什么呢？因為每個回合里，當(dāng)前游戲者可以選擇一個子游戲（即選一堆火柴），然后進(jìn)行一次合法操作（從該堆中拿火柴），但其他子游戲的局面保持不變（不能從多堆火柴中同時拿）。

? c\SG定理和SG函數(shù)：組合游戲的和通常是很復(fù)雜滴，但是可以利用SG函數(shù)和SG定理來解決問題。||-><-||對于任意狀態(tài)x,定義SG(x)=mes(S),其中S={SG(y)|y是x的后繼狀態(tài)}，mex(S)表示不在S內(nèi)的最小自然數(shù)。這樣終態(tài)的SG值顯然為0（S為空），而其他值可以遞推出來，不難發(fā)現(xiàn)SG(x)=0當(dāng)且僅當(dāng)x為必敗態(tài)。

?

8、類似Nim的游戲:

? a\翻棋子游戲：一個棋盤上每個格子有一個棋子，每次操作可以隨便選一個朝上的棋子（x,y）(代表x行y列)，選一個形如（x,b）或者（a,y）(其中b<y,a<x)的棋子，然后把它和（x,y）一起旋轉(zhuǎn)，無法操作的人輸。||-><-||把坐標(biāo)為（x,y）的棋子看做是大小分別為x,y的2堆火柴，每次操作是把其中一堆的數(shù)量減少或刪除。

? b\除法游戲：有一個n x m (1<=n,m<=50)矩陣，每個元素均為2-10000之間的正整數(shù)。兩個游戲者輪流操作。每次可以選中一行中的1個或者多個大于1的整數(shù)，把他們中的每個數(shù)都變?yōu)樗哪硞€素因子，比如：12可以變?yōu)?,2,3,4,6，不能操作的輸（即：在操作之前矩陣全是1則輸）。||-><-||考慮每個數(shù)的素因子個數(shù)，則讓一個數(shù)“變?yōu)樗恼嬉蜃印钡葍r于拿掉它的一個或多個素因子。這樣，每行對應(yīng)一個火柴堆，每個數(shù)的每個素因子看成一根火柴，則本題和Nim完全等價啦。?

?

總結(jié)

以上是生活随笔為你收集整理的[算法] 2-4 组合游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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