Nim遊戲

**尼姆遊戲**（英語：**Nim**），又譯為**拈**，是一種兩個人玩的回合制數學戰略遊戲。遊戲者輪流從幾排棋子（或者任何道具）中選擇一排，再由這一排中取走一個或者多個，依規則不同，拿走最後一個的可能是輸家，也有可能是贏家。當指定相應數量時，一堆這樣的棋子稱作一個**尼姆堆**。古代就有許多尼姆遊戲的變體。最早歐洲有關尼姆遊戲的參考資料是在 16 世紀，目前使用的名稱是由哈佛大學的 Charles L. Bouton 命名，他也在 1901 年提出了此遊戲的完整理論，不過沒有說明名稱的由來。

尼姆遊戲最常見的玩法是拿到最後一個棋子的人輸（misère game）。尼姆遊戲也可以改為拿到最後一個棋子的人贏（normal play）。大部份類似的遊戲都是最後一個棋子的人贏，不過這不是尼姆遊戲最常見的玩法。不論哪一種玩法，只要剛好剩下一排的棋子是二個或二個以上（其他排可能沒有棋子，或是只有一個），下一個遊戲者可以輕易的獲勝。下一個遊戲者可以將數量最多的這排棋子全部拿走或只留一個。剩下的各排都只有一個棋子。
若是 misère 版本，下一個遊戲者下完之後，只要留下奇數排就會勝利，若是 normal 版本，下一個遊戲者下完之後，只要留下偶數排就會勝利。

normal 版本的尼姆遊戲（也就是尼姆數系統）是斯普萊格–格隆第定理的基礎，其中提到在 normal 版本中，每一個 normal 版本的無偏博弈（從任何一個局勢出發，雙方可以採取完全相同的行動，也就是說棋盤上沒有顏色的區分）都等價於一個特定大小的尼姆堆。所有的 normal 版本的無偏博弈都可以給與尼姆值，但 misère 版本的就不一定。只有溫馴遊戲才能用 misère 版本尼姆的策略來進行。尼姆遊戲是一種特殊的偏序遊戲，其中的偏序關係包括了不交集的全序關係（堆）。三排棋子尼姆遊戲的演進圖和 Ulam-Warburton 自動機演進圖的三個分支相同。

## 遊戲玩法以及說明

normal 版本是由二位遊戲者一起玩，有三排棋子，各排的棋子為任意正整數。二位遊戲者輪流選一排棋子，拿走上面至少一個棋子，也可以拿同一排的多個棋子。normal 版本的目的是要拿到最後一個棋子。misère 版本的目的就是要讓對方被迫拿走最後一個棋子（拿到最後一個棋子的人輸）。

以下是 normal 版本的遊戲，由愛麗絲與鮑伯二個人玩，三排棋子分別有三個、四個及五個棋子。

## 必勝組態

尼姆遊戲的策略就是在拿完棋子後，使棋子個數符合以下任何一個組態，接下來再輪到時，一定可以再拿走適當數量的棋子，使棋子個數仍符合以下任何一個組態。normal 版本和 misere 版本的差別只在最後一兩步，前面都相同：

\* 只在 normal 版本有效

\*\* 只在 misere 版本有效

其中有出現 _n_ 和 _m_，是任何正整數，_n_ 和 _m_ 可以相同。

## 數學理論

尼姆遊戲在數學上是已解遊戲，針對任意排數及個數的初始狀態都已有解法，而且有簡單的方式可以判斷哪一個遊戲者會勝利，並且此遊戲者要如何取子才會勝利。

這遊戲理論的關鍵是在各排個數在二進位下 XOR 位操作的結果，此操作也稱為是在 **GF**(2) 中的向量加法（在模數 2 以下的位元加法）。在組合博弈論中常稱為是「尼姆和」（nim-sum），以下也使用此一名稱。_x_ 和 _y_ 的尼姆和會寫成 _x_ ⊕ _y_，以和一般的和區別 _x_ + _y_。像 3, 4, 5 的尼姆和計算如下：

另一個等效，比較容易心算的作法，是將三排的個數分別表示為相異二次冪的和，再設法消除成對的次冪，再將最後留下的數字相加即可：

```
3 = 0 + 2 + 1 =     2   1      A排
4 = 4 + 0 + 0 = 4              B排
5 = 4 + 0 + 1 = 4       1      C排
--------------------------------------------------------------------
2 =                 2          1和4都消去了, 剩下的是2
```

在 normal 版本（拿到最後一個棋子的贏）中，勝利的策略就是在取走棋子後，使尼姆和為 0。只要取走棋子前，尼姆和不為 0，一定有辦法取走部份棋子使尼姆和為 0。另一個遊戲者無論怎麼拿，取走棋子後尼姆和都不會為 0。以此策略，只要在取棋子時照策略進行，一定會勝利。要找到要拿走的棋子，可以令 X 是原來各排棋子數的尼姆和，遊戲策略是要分別計算各排棋子數和 X 的尼姆和，找到尼姆和比該排棋子數少的那一排，接下來就要取走這一排的棋子，使該排棋子數等於尼姆和。以上例中，原來各排棋子數的尼姆和是 _X_ = 3 ⊕ 4 ⊕ 5 = 2。A=3、B=4、C=5 且 X=2，因此得到

　
: _A_ ⊕ _X_ = 3 ⊕ 2 = 1 [因為 (011) ⊕ (010) = 001 ]

　
: _B_ ⊕ _X_ = 4 ⊕ 2 = 6

　
: _C_ ⊕ _X_ = 5 ⊕ 2 = 7

因此下一步是取走 A 排的棋子，使其數量變 1（拿走二個棋子）。

有一個特別簡單的例子，是只剩二排的情形，其策略是在個數較多的那牌拿走部份棋子，使兩者數量相同。接下來對手不論怎麼下，都繼續使二排的數量相同，最後即可勝利。

若是玩 misère 版本。前面的策略都一樣，只到只剩一排的棋子超過一個（二個或二個以上）時才有不同。此時的策略都是針對超過一個棋子的那排棋子取子，使留下來的每一排都只有一個棋子。接下來玩的人只能從這幾排中選一排拿走。取子可能是那排全部取完，或是只剩一個，視遊戲版本而定，在玩 misère 版本（拿到最後一個棋子的輸）時，要使留下來的排數是單數（因此對方會拿到最後一個棋子），在玩 normal 版本遊戲時，要使留下來的排數是偶數。（因此自己會拿到最後一個棋子）。

以下是棋子數分別是 3, 4, 5 個，在 misère 版本的玩法：

### 實現尼姆遊戲策略的程式範例

上述的策略可以寫成程式，以下就是 Python 的範例：

## 必勝策略的證明

以下是必勝策略的證明，由 C. Bouton 所提出。

**定理**：在 normal 版本的尼姆遊戲中，第一個玩家有必勝的策略，若且唯若各排棋子數的尼姆和不為零。否則，第二個玩家有必勝的策略。

_證明_：注意尼姆和（⊕）遵守一般加法的結合律及交換律，還有另外一個性質 _x_ ⊕ _x_ = 0。

令 _x_1, ..., _xn_ 是移動前的各排棋子數，_y_1, ..., _yn_ 是移動後的各排棋子數。令 _s_ = _x_1 ⊕ ... ⊕ _xn_ 且 _t_ = _y_1 ⊕ ... ⊕ _yn_。若這次是移動第 _k_ 排的棋子，可得 _xi_ = _yi_ 針對所有 _i_ ≠ _k_，且 _xk_ > _yk_。依照⊕的性質，可得

```
    _t_ = 0 ⊕ _t_
      = _s_ ⊕ _s_ ⊕ _t_
      = _s_ ⊕ (_x_1 ⊕ ... ⊕ _xn_) ⊕ (_y_1 ⊕ ... ⊕ _yn_)
      = _s_ ⊕ (_x_1 ⊕ _y_1) ⊕ ... ⊕ (_xn_ ⊕ _yn_)
      = _s_ ⊕ 0 ⊕ ... ⊕ 0 ⊕ (_xk_ ⊕ _yk_) ⊕ 0 ⊕ ... ⊕ 0
      = _s_ ⊕ _xk_ ⊕ _yk_
 
(*) _t_ = _s_ ⊕ _xk_ ⊕ _yk_.
```

此定理會由以下二個引理推導而來。

**引理 1**：若 _s_ = 0，則無論如何移動，接下來 _t_ ≠ 0。

_證明_：若沒有任何可以移動的棋子，此引理空虛的真（依定義，接下來要玩的遊戲者輸，因為在他前一手的遊戲者拿了最後一個棋子）。否則，任何 _k_ 排的移動都會因為 (\*)，造成 _t_ = _xk_ ⊕ _yk_。因為 _xk_ ≠ _yk_，上述數字不為 0。

**引理 2**：若 _s_ ≠ 0，有可能讓 _t_ = 0.

_證明_：令 _d_ 是 _s_ 二進位表示法中最左邊１的位置，選擇 _k_ 使 _xk_ 的第 _d_ 位元也不是零。（這個 _k_ 一定存在，不然 _s_ 的第 _d_ 位元都是零了）
令 _yk_ = _s_ ⊕ _xk_，可以聲稱 _yk_ < _xk_：_xk_ 和 _yk_ 所有 d 左邊的位元都相同，_d_ 位元從 1 變為 0（數值減少 2d），剩下位元的變化最多是 2d−1。因此接下來的遊戲者可以在第 _k' 排拿走_ xk_−_yk _個棋子，則_

```
_t_ = _s_ ⊕ _xk_ ⊕ _yk_           (by (*))
  = _s_ ⊕ _xk_ ⊕ (_s_ ⊕ _xk_)
  = 0.
```

misère 版本的策略剛剛已經看過，只有在只剩一排的棋子是二個或二個以上時才不同。在這種情形 _s_ ≠ 0，接下來玩的人有必勝策略，若是 normal 版本，就是設法留下偶數排的棋子，每排都只有一個棋子，misère 版本則反過來，設法留下奇數排的棋子，每排都只有一個棋子。

## 社會文化

在 1939 年紐約世界博覽會中，西屋電氣有展示一個機器，會玩尼姆遊戲的 Nimatron。自 1940 年的 5 月 11 日到 10 月 27 日為止，在六週的週期內只有少數的人可以打敗 Nimatron：若他們勝了，會得到一個稱為 Nim Champ 的硬幣。尼姆遊戲也是最早電腦化的游戲。Ferranti 曾製作可以玩尼姆遊戲的 Nimrod 電腦，在 1951 年的英國節上展示。1952 年時，W. L. Maxon 公司的工程師 Herbert Koppel、 Eugene Grant 和 Howard Bailer 開發了重達 23 公斤（50 英磅）的機器，可以和人玩尼姆遊戲，而且多半會贏。Tinkertoy 也可以製作尼姆遊戲機。

尼姆遊戲是馬丁・加德納在《科學美國人》（Scientific American）雜誌中，1958 年 2 月〈數學遊戲專欄〉的主題。在 1961 年法國新浪潮電影《去年在馬倫巴》中，有玩過特定版本的尼姆遊戲，而且有象徵的重要性。

## 類似遊戲

### subtraction game

另一個有點類似的遊戲稱為 subtraction game，會先列出總數，以及每一次可以拿走的最大數量。可能每一次只能拿走 1 個、2 個... 至 k 個。例如在《Survivor: Thailand》節目中的 Thai 21，就是 _k_= 3 的版本。

若棋子只有一排，共有 _n_ 個棋子，其必勝策略若且唯若

　
: _n_ ≡ 0 (mod _k_+ 1)（拿到最後一個棋子的人贏的玩法）或

　
: _n_ ≡ 1 (mod _k_+ 1)（拿到最後一個棋子的人輸的玩法）

### 21 遊戲

21 遊戲一般會用拿到最後一個棋子的人輸的玩法。可以有數個遊戲者參與。第一個遊戲者說 1，其他的遊戲者可以在前一個人的數字加 1,2 或是 3。數到 21 的遊戲者輸。若是二個遊戲者玩，有必勝的策略，就是讓加完的數字維持是 4 的倍數。這可以使另一方最後一定會數到 21。

21 遊戲的數字也可以修改，例如改為「最多加 5，數到 34 的人輸」。

以下是一個 21 遊戲的例子，第二個遊戲者使用必勝的策略：

```
遊戲者     數字
  1           1
  2           4
  1        5, 6 或 7
  2           8
  1       9, 10 或 11
  2          12
  1      13, 14 或 15
  2          16
  1      17, 18 或 19
  2          20
  1          21
```

### 100 遊戲

另一個類似的遊戲是 100 遊戲：從 0 開始加，每一次可以加 1 到 10 之間的任一個整數，數到 100 的人勝利。必勝的策略是搶到類似 01、12、23、34……、89 的數字，接下來另一遊戲者不論加多少，都設法搶到下一個 01、12、23、34……、89 的數字（因為這些數字之間的差是 11，不論對方加 1 到 10 之間的哪一個數字，都可以可以再加數字，使二人加的數字總計為 11）。只要到 89 之後，接下來不論對方加多少，都可以再加數字使結果為 100，因此必勝。

### 多排尼姆的規則

另一個版本的尼姆，是允許在每一排中取走相同數量的棋子。

### 循環尼姆

另一種尼姆的變體是循環尼姆，將一定數量的棋子擺成圓形，二個遊戲者輪流取棋子，可以取相鄰的一個、二個或三個棋子。以下是一個例子：

```
. . . . . . . . . .
```

一開始取走三個棋子

```
_ . . . . . . . _ _
```

接下來又取走三個棋子

 

```
_ . _ _ _ . . . _ _
```

又拿走一個棋子

```
_ . _ _ _ . . _ _ _
```

最後剩下三個棋子，但是不相鄰，無法一次取走。

### Grundy 遊戲

Grundy 遊戲也是尼姆遊戲的變體，一開始有一排特定數量的棋子，遊戲者要輪流將某一排棋子分為二排數量不同，且都不為 0 的棋子。例如 6 個棋子可以分為 5+1、4+2，但不能分為 3+3。此遊戲可以讓最後一個人贏或是輸。

## 相關條目

* 尼姆數
* 博弈論
* Dr. NIM
* 費氏尼姆
* 威佐夫遊戲
* 三角棋
* 模糊遊戲
* 零遊戲
* 減平方數
* \* (遊戲理論)
* Android 尼姆
* 雷蒙德・雷德赫弗
* Notakto
* Chomp
* 圖靈落下

## 參考資料

## 外部連結

* 50-pound computer plays Nim- The New Yorker magazine "Talk of the Town" August, 1952 （頁面存檔備份，存於網際網路檔案館）