尼姆博弈

尼姆博弈是一個兩人博弈，2名玩家輪流從數堆物品中拿取一定數量的物品，每次拿取時先選擇某一堆，再從中拿取任意數量個物品，至少拿1個，至多將這一堆物品全部拿走，不能不拿。拿到最後一個物品的玩家獲勝。

基本介紹

• 中文名：尼姆博弈
• 外文名：Nim
• 所屬學科：博弈論

簡介

尼姆博弈中涉及到n堆不同的物品，這些堆中各自物品的數量是任意的。兩名玩家在輪流行動時，可以選擇將某一堆中任意數量的物品拿走，至少1個，至多全部拿走，但不能不拿或跨堆拿取物品。根據規則拿到最後一個物品，使得對手無物品可拿的玩家獲勝。

尼姆博弈的變體在有正式文獻記載之前就已經存在，現在使用的這一名稱是由哈佛大學的CharlesL. Bouton命名，他也在1901年提出了此博弈的完整理論，不過沒有說明名稱的由來。

由於物品的數量總在嚴格減小，此博弈是有限的；且玩家可以知曉對手的行動，雙方均具有完全信息；且博弈中不含運氣成分；那么由策梅洛定理可知，先手方或後手方有必勝策略。

必勝策略

兩堆的情形

我們從最簡單的兩堆物品的情形開始分析，並使用二元組（n，m）來表示這兩堆物品當前的數量。當（n，m）情形下先手方\後手方有必勝策略時，我們稱（n，m）為制勝位置。

我們將說明：當n=m時，後手有必勝策略，否則先手有必勝策略。

• 當n=m=1時，先手方僅能夠將其中一堆完全取走，故後手方只需要將另一堆的1個物品取走即可獲勝。即（1，1）是後手方的制勝位置。
• 當n=m=k>1時，無論先手方選擇哪一堆，取走多少數量的物品，後手方只需要選擇另一堆，並取走相同數量的物品，就可以將物品堆的狀態從（k，k）轉換到（j，j），其中j<k。如此操作下去，由於兩堆物品的數量保持相等且嚴格遞減，故後手方玩家總能將物品堆的數量轉換為（1，1）或（0，0）。由上面的討論與遊戲規則知，後手方必勝。即（n，m），n=m是後手方的制勝位置。
• 當時，先手方只需要從較多的一堆物品中拿取適量的物品，使得兩物品堆物品數量一致，就將情形轉換為了上述兩種情況之一，且自身處於後手方。由上面的討論知，先手方必勝。即（n，m），是先手方的制勝位置。

尼姆和

為了將兩堆物品的簡單情形推廣到多堆物品的一般情形，我們需要引入物品堆的尼姆和這一概念。利用此概念我們會發現：多堆物品情形中，所有物品堆的尼姆和為0這一條件，與兩堆物品情形中n-m=0這一條件具有完全相同的地位。

定義：物品堆的尼姆和是一個二進制數，它是由所有物品堆中物品的數量轉換為二進制後，進行異或運算得到的。設有k個物品堆，分別有個物品，那么物品堆的尼姆和為：

其中為異或運算（即，）

例子：假設有3堆物品，數量分別為3，4，5。物品堆的尼姆和可以如下計算：

• 將數量轉換為二進制

3 = (011)₂

4 = (100)₂

5 = (101)₂

• 進行異或運算

2這一位是

2這一位是

2這一位是

最終結果為(010)₂

一般情形

一般情形下的必勝策略與兩堆的情形基本一致：若物品堆的尼姆和為0，則後手方有必勝策略，否則先手方有必勝策略。必勝策略的構造基於下面的定理：

1. 在尼姆和為0時，無論如何拿取物品，拿取之後物品堆的尼姆和一定不為0；
2. 在尼姆和不為0時，總存在一種拿取物品的方式，使得拿取之後物品堆的尼姆和為0。

此必勝策略及定理的證明正是由C. Bouton首先提出。

我們先說明必勝策略的構造方式，再證明這兩個定理。

• 若物品堆的尼姆和為0，則無論先手方如何拿取，操作之後物品堆的尼姆和一定不為0，先手方總是不能將物品拿完。後手方總是可以選擇拿取方式使得物品堆的尼姆和再次為0，同時物品的數量嚴格減小，這樣操作下去，有限多輪之後即可使得後手方拿取物品後所有物品均被拿取，即後手方有必勝策略。
• 若物品堆的尼姆和不為0，則先手方總可以選擇拿取方式使得拿取之後物品堆的尼姆和為0，且處於後手方的位置。由上述討論可知，先手方有必勝策略。

下面我們證明本節開始時的兩個定理，為此我們先約定一些記號：

我們設共有k堆物品，並對第i堆進行了一次拿取操作。在拿取之前各物品堆的數量記為，其尼姆和記為s，在拿取之後各物品堆的數量記為，其尼姆和記為t

根據異或的性質，下面的等式成立：

也即

定理1：若s=0，則無論如何拿取物品，都有

證明：已知s=0且拿取物品使得，故直接計算知

定理2：若，則存在一種拿取方式，使得t=0

證明：注意到如果拿取第i堆中適量物品後使得，那么立刻有，故我們只需說明此時，也即確實可以通過拿取物品的方式使得第i堆的物品數量減少為即可。下面我們就尋找滿足這一條件的i。

由於，那么s的二進制表示中至少有一位不是0，不妨設其二進制表示中最左的1在2這一位上。我們選擇這樣的i：的2這一位上恰好也是1。這樣的i一定存在，否則若所有的2這一位上都是0，那么s的這一位上也應該是0。

下面說明這樣選擇的i使得。這是因為：

1. 考慮2左側的數位，這些位置上s均為0。故與的2左側的數位均相同；
2. 考慮2這一位，這一位上與均為1，故的這一位為0；其值相比減小了2；
3. 考慮2右側的數位，無論這些位置上如何變，其值至多改變;

綜合以上討論，這一選擇的i確實使得。這就證明了定理2。

策略實現

結合上述分析，玩家在尼姆博弈中應當按照下面的策略拿取物品：

1. 計算尼姆和s；
2. 若，則計算s與每一個物品堆數量的異或值，直到找到一個的物品堆，從這一堆中拿取個物品；
3. 若s=0，則隨意選擇拿取物品，此時已經處於必敗位置，只能希望對方犯錯。

變體

如果將規則改為拿到最後一個物品者敗，可得到尼姆博弈的一種變體。此時我們有下面的結論：

1. 若尼姆和為0且所有堆中僅有1個物品，則先手方有必勝策略；
2. 若尼姆和不為0且至少有一堆物品數量大於1，則先手方有必勝策略；
3. 否則後手方有必勝策略。

具體策略分析如下：

A.假定尼姆和為0且所有堆中僅有1個物品，那么一定有偶數堆物品，否則尼姆和不為0。實際上此時雙方均沒有選擇，只能每次拿走一堆物品，最終先手方拿走倒數第二堆物品，迫使後手方拿走最後一堆物品，輸掉博弈。故先手方必勝。

經過相似的分析我們可以得出，若所有堆中僅有1個物品，且共有奇數堆物品，那么後手方必勝。

B.假定尼姆和不為0且至少有一堆物品數量大於1，此時分為兩種情況討論：

B.1 只有一堆物品的數量大於1：

B.1.1此時若共有偶數個物品堆，則先手方只需要將物品數量大於1的這一堆全部拿走，就將情況轉換為A中所有堆中僅有1個物品，且共有奇數堆物品並處於後手方；

B.1.2此時若共有奇數個物品堆，則先手方只需要使得物品數量大於1的這一堆物品拿取之後只剩1個物品，就將情況轉換為A中所有堆中僅有1個物品，且共有奇數堆物品並處於後手方；

綜合以上兩點，此時先手方必勝。

B.2 至少有2堆物品的數量大於1：

此時先手方只需要將尼姆和變為0即可，由上面的討論我們知道這樣的拿取方式一定是存在的。並且拿完之後一定還至少有2堆物品的數量大於1，這是因為假設拿完之後只有第i堆物品數量大於1，不妨設其二進制表示的中最左側的1在2這一位上，那么物品堆的尼姆和中2這一位上一定是1，因為只有的二進制表示中這一位是1，其他物品堆數量的二進制表示這一位上都是0，而，從而尼姆和不為0，但這與尼姆和為0矛盾。故拿完之後一定還至少有2堆物品的數量大於1。由於物品數量嚴格減少，如此操作下去，在有限輪之後一定會遇到B.1中的情形，從而先手方必勝。

拓展

尼姆博弈是組合博弈理論(Combinatorial game theory)中的重要模型，是斯普萊格–格隆第定理（Sprague–Grundy theorem）的基礎，此定理指出每一個無偏博弈的的特定局勢都可以轉換成某種狀態的尼姆博弈。利用此定理與構造特定的SG函式(Sprague–Grundy function)，我們可以解決很多類似的問題。