[教學] Nim Game （典型玩法）

amoshuangyc

你必須先搞懂二進位制與 xor 才能理解這篇文章的內容。

文章節錄、翻譯、改寫自 http://web.mit.edu/sp.268/www/nim.pdf 。

這裡先介紹 Nim Game 的典型玩法：

• 共有三堆石頭，分別有 3, 4, 5 顆。
• 只有兩個玩家。兩個玩家輪流拿石頭，每次拿石頭可以從三堆中任意一堆拿走不限數量的石頭，但不可以一顆石頭都不拿。
• 贏家為拿走最後一個石頭的人。
  
  
  

舉例：

第一堆	第二堆	第三堆	A 先拿；B 後拿。
3	4	5	A 從第一堆拿走 2 顆石頭。
1	4	5	B 從第三堆拿走 3 顆石頭。
1	4	2	A 從第二堆拿走 1 顆石頭。
1	3	2	B 從第一堆拿走 3 顆石頭。
1	0	2	A 從第三堆拿走 1 顆石頭。
1	0	1	B 從第一堆拿走 1 顆石頭。
0	0	1	A 從第三堆拿走 1 顆石頭。
0	0	0	A 贏了。

有時為了增加複雜度與可玩性，石頭可能不只三堆，石頭數也可能不是 3, 4, 5。

但不管石頭有幾堆，事實上，存在著必勝策略：

每次拿完石頭時，讓 Nim-sum 保持 0。

所謂的 Nim-sum 指的是「第一堆的石頭數 xor 第二堆的石頭數 xor 第三堆的石頭數 xor … xor 第 n 堆的石頭數」。

關於 xor 是什麼請自行查閱，有幾個性質必需注意：

N xor N = 0

N xor 0 = N

xor 滿足交換律與結合律。

以下給出證明：

引理 1：

當前一個玩家拿完石頭後，Nim-sum = 0，那麼下一個玩家拿完石頭後，Nim-sum 必不為 0。

x[1], x[2], …, x[n] 代表前一個玩家拿完後，各堆的石頭數，此時 Nim-sum s = x[1] xor x[2] xor x[3] xor … xor x[n] = 0。

y[1], y[2], …, y[n] 代表下一個玩家拿完後，各堆的石頭數，此時 Nim-sum t = y[1] xor y[2] xor y[3] xor … xor y[n]。

因為玩家只能從其中一堆拿石頭，所以 x 陣列跟 y 陣列只差在第 k 項：y[k] ≠ x[k]，

除了這一項，其它項都是一樣的： x[j] = y[j] for j ≠ k。我們要證明 t ≠ 0。

t

= 0 xor t

= s xor s xor t

= s xor (x[1] xor x[2] xor … xor x[n]) xor (y[1] xor y[x] xor … y[n])

= s xor (x[1] xor y[1]) xor (x[2] xor y[2]) xor … xor (x[n] xor y[n])

= s xor x[k] xor y[k]

= 0 xor x[k] xor y[k]

= x[k] xor y[k]

因為 x[k] ≠ y[k]，所以 t = x[k] xor y[k] ≠ 0。至此得證。

引理 2：

當換你拿石頭時，Nim-sum ≠ 0，一定存在著某種拿法，可以使 Nim-sum = 0。

x[1], x[2], … x[n] 代表拿石頭前，各堆的石頭數，Nim-sum s ≠ 0。

y[1], y[2], … y[n] 代表拿石頭後，各堆的石頭數，Nim-sum t。

因為 s ≠ 0，所以存在最高有效位（Most Significant Bit）（可以想像成 s 在二進位中，最左邊的 1），我們假設這個位置是 d。

而 x 陣列中必存在至少一個 x[k]，x[k] 有著與 s 相同的最高有效位，也就是說，x[k] 在二進位中，最左邊的 1 的位置也是 d。

（如果 x[k] 不存在，那麼在計算 xor 時，s 怎麼可能在位置 d 上產生 1 呢？注意只有 1 xor 0 或 0 xor 1 才會是 1。0 xor 0, 1 xor 1 都 = 0）

於是，我們可以假設 y[k] = x[k] xor s，因為 x[k], s 有著相同的最高有效位，所以 y[k] = x[k] xor s 必 < x[k]（在最高有效位上，1 xor 1 = 0）。這樣假設的結果就是從第 k 堆中拿走 x[k] - y[k] 的石頭。

Nim-sum t

= s xor x[k] xor y[k]（引理1中的式子）

= s xor x[k] xor x[k] xor s

= 0

得證。

證明：

如果遊戲一開始時 Nim-sum 是 0，那麼先拿者拿完後必會使 Nim-sum ≠ 0（引理 1），而根據引理2，後拿者拿完後，必可以使 Nim-sum = 0。之後重覆這個過程，最後要使每一堆石頭數都變為 0 （Nim-sum = 0 xor 0 xor … xor 0 = 0）的那一步必定是後拿者走的。也就是說，後拿者贏了。

如果遊戲一開始時 Nim-sum 不是 0，那麼先拿者必可以使 Nim-sum = 0（引理 2），而後拿著不管怎麼拿，拿完後 Nim-sum 必 ≠ 0（引理1），之後重覆這個過程，最後那一步必定是先拿者走的。

如果你看不懂上面的解釋，這裡有個比較形象化的說明：

在遊戲過程中的任何時候，Nim-sum 要麼 = 0，要麼 ≠ 0。Nim-sum = 0 的時候，下一個玩家拿完後必使 Nim-sum ≠ 0（引理1），但另一個玩家必可以使 Nim-sum 重新變回 0（引理2），之後這個過程會一直重覆，所以玩家一個是使 Nim-sum 變為 0 的人，一個是使 Nim-sum ≠ 0 的人。

而遊戲的終止狀態為每堆的石頭數都是 0，此時 Nim-sum = 0。所以誰使 Nim-sum 變為 0，誰就是贏家。

如果遊戲一開始的 Nim-sum ≠ 0，那麼先拿者就是這個人，如果一開始 Nim-sum = 0，後拿者就是這個人。

順帶一提，如果那個該使 Nim-sum 變為 0 的玩家不這麼做，反而使 Nim-sum ≠ 0 呢？那麼對方就可以使 Nim-sum = 0，這個「不乖」的玩家只能繼續使 Nim-sum ≠ 0，而對方如果繼續執行使 Nim-sum = 0 的策略，那麼贏家必定是對方。

結論：

若二個玩家都使用「最佳策略」，則我們可以在不模擬遊戲的情況下，直接得出誰是贏家。

若遊戲一開始時，Nim-sum ≠ 0，則先拿者是贏家。

若遊戲一開始時，Nim-sum = 0，則後拿者是贏家。