尼姆遊戲
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f6/NimGame.svg/220px-NimGame.svg.png)
尼姆遊戲(英語:Nim),又譯為拈,是一種兩個人玩的回合制數學戰略遊戲。遊戲者輪流從幾排棋子(或者任何道具)中選擇一排,再由這一排中取走一個或者多個,依規則不同,拿走最後一個的可能是輸家,也有可能是贏家。當指定相應數量時,一堆這樣的棋子稱作一個尼姆堆。古代就有許多尼姆遊戲的變體[1]。最早歐洲有關尼姆遊戲的參考資料是在16世紀,目前使用的名稱是由哈佛大學的Charles L. Bouton命名,他也在1901年提出了此遊戲的完整理論[2],不過沒有說明名稱的由來。
尼姆遊戲最常見的玩法是拿到最後一個棋子的人輸(misère game)。尼姆遊戲也可以改為拿到最後一個棋子的人贏(normal play)。大部份類似的遊戲都是最後一個棋子的人贏,不過這不是尼姆遊戲最常見的玩法。不論哪一種玩法,只要剛好剩下一排的棋子是二個或二個以上(其他排可能沒有棋子,或是只有一個),下一個遊戲者可以輕易的獲勝。下一個遊戲者可以將數量最多的這排棋子全部拿走或只留一個。剩下的各排都只有一個棋子。 若是misère版本,下一個遊戲者下完之後,只要留下奇數排就會勝利,若是normal版本,下一個遊戲者下完之後,只要留下偶數排就會勝利。
normal版本的尼姆遊戲(也就是尼姆數系統)是斯普萊格–格隆第定理的基礎,其中提到在normal版本中,每一個normal版本的無偏博弈(從任何一個局勢出發,雙方可以採取完全相同的行動,也就是說棋盤上沒有顏色的區分)都等價於一個特定大小的尼姆堆。所有的normal版本的無偏博弈都可以給與尼姆值,但misère版本的就不一定。只有溫馴遊戲才能用misère版本尼姆的策略來進行。尼姆遊戲是一種特殊的偏序遊戲,其中的偏序關係包括了不交集的全序關係(堆)。三排棋子尼姆遊戲的演進圖和Ulam-Warburton自動機演進圖的三個分支相同[3]。
遊戲玩法以及說明
normal版本是由二位遊戲者一起玩,有三排棋子,各排的棋子為任意正整數。二位遊戲者輪流選一排棋子,拿走上面至少一個棋子,也可以拿同一排的多個棋子。normal版本的目的是要拿到最後一個棋子。misère版本的目的就是要讓對方被迫拿走最後一個棋子(拿到最後一個棋子的人輸)。
以下是normal版本的遊戲,由愛麗絲與鮑伯二個人玩,三排棋子分別有三個、四個及五個棋子。
各排數量 A B C |
走法 |
3 4 5 | 鮑伯從A排拿走2個棋子 |
1 4 5 | 愛麗絲從C排拿走3個棋子 |
1 4 2 | 鮑伯從B排拿走1個棋子 |
1 3 2 | 愛麗絲從B排拿走1個棋子 |
1 2 2 | 鮑伯拿走所有A排的棋子,只剩下二排,各有2個 |
0 2 2 | 愛麗絲從B排拿走1個棋子 |
0 1 2 | 鮑伯從C排拿走1個棋子,只剩下二排,各有1個 (若是misère版本,會從C排拿走2個棋子,留下(0, 1, 0)) |
0 1 1 | 愛麗絲拿走B排的1個棋子 |
0 0 1 | 鮑伯拿走所有C排的棋子,鮑伯勝利。 |
必勝組態
尼姆遊戲的策略就是在拿完棋子後,使棋子個數符合以下任何一個組態,接下來再輪到時,一定可以再拿走適當數量的棋子,使棋子個數仍符合以下任何一個組態。normal版本和misere版本的差別只在最後一兩步,前面都相同:
2排 | 3排 | 4排 |
---|---|---|
1 1 * | 1 1 1 ** | 1 1 1 1 * |
2 2 | 1 2 3 | 1 1 n n |
3 3 | 1 4 5 | 1 2 4 7 |
4 4 | 1 6 7 | 1 2 5 6 |
5 5 | 1 8 9 | 1 3 4 6 |
6 6 | 2 4 6 | 1 3 5 7 |
7 7 | 2 5 7 | 2 3 4 5 |
8 8 | 3 4 7 | 2 3 6 7 |
9 9 | 3 5 6 | 2 3 8 9 |
n n | 4 8 12 | 4 5 6 7 |
4 9 13 | 4 5 8 9 | |
5 8 13 | n n m m | |
5 9 12 | n n n n |
*只在normal版本有效
**只在misere版本有效
其中有出現n和m,是任何正整數,n和m可以相同。
數學理論
尼姆遊戲在數學上是已解遊戲,針對任意排數及個數的初始狀態都已有解法,而且有簡單的方式可以判斷哪一個遊戲者會勝利,並且此遊戲者要如何取子才會勝利。
這遊戲理論的關鍵是在各排個數在二進位下XOR位操作的結果,此操作也稱為是在GF(2)中的向量加法(在模數2以下的位元加法)。在組合博弈論中常稱為是「尼姆和」(nim-sum),以下也使用此一名稱。x和y的尼姆和會寫成x ⊕ y,以和一般的和區別x + y。像3, 4, 5的尼姆和計算如下:
二進位 | 十進位 | 備註 |
0112 | 310 | A排 |
1002 | 410 | B排 |
1012 | 510 | C排 |
0102 | 210 | 三排數字的尼姆和,3 ⊕ 4 ⊕ 5 = 2 |
另一個等效,比較容易心算的作法,是將三排的個數分別表示為相異二次冪的和,再設法消除成對的次冪,再將最後留下的數字相加即可:
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的尼姆和(Yi),找到尼姆和(Yi)比該排棋子數少的那一排,接下來就要取走這一排的棋子,使該排棋子數等於該行的尼姆和(Yi)。以上例中,原來各排棋子數的尼姆和是X = 3 ⊕ 4 ⊕ 5 = 2。A=3、B=4、C=5且X=2,因此得到
- YA = A ⊕ X = 3 ⊕ 2 = 1 [因為 (011) ⊕ (010) = 001 ]
- YB = B ⊕ X = 4 ⊕ 2 = 6
- YC = C ⊕ X = 5 ⊕ 2 = 7
因此下一步是取走A排的棋子,使其數量變1(拿走二個棋子)。
有一個特別簡單的例子,是只剩二排的情形,其策略是在個數較多的那牌拿走部份棋子,使兩者數量相同。接下來對手不論怎麼下,都繼續使二排的數量相同,最後即可勝利。
若是玩misère版本。前面的策略都一樣,只到只剩一排的棋子超過一個(二個或二個以上)時才有不同。此時的策略都是針對超過一個棋子的那排棋子取子,使留下來的每一排都只有一個棋子。接下來玩的人只能從這幾排中選一排拿走。取子可能是那排全部取完,或是只剩一個,視遊戲版本而定,在玩misère版本(拿到最後一個棋子的輸)時,要使留下來的排數是單數(因此對方會拿到最後一個棋子),在玩normal版本遊戲時,要使留下來的排數是偶數。(因此自己會拿到最後一個棋子)。
以下是棋子數分別是3, 4, 5個,在misère版本的玩法:
A | B | C | 尼姆和 | 下法 |
3 | 4 | 5 | 0102=210 | 我從A排拿走2個,使剩下的尼姆和為0 |
1 | 4 | 5 | 0002=010 | 你從C排拿走2個 |
1 | 4 | 3 | 1102=610 | 我從B排拿走2個 |
1 | 2 | 3 | 0002=010 | 你從C排拿走1個 |
1 | 2 | 2 | 0012=110 | 我從A排拿走1個 |
0 | 2 | 2 | 0002=010 | 你從C排拿走1個 |
0 | 2 | 1 | 0112=310 | 我將B排的都拿走,只留下C排(使剩下的排數是奇數) (若是normal版本,我會從C排拿走1個,使剩下的排數是偶數) |
0 | 0 | 1 | 0012=110 | 你從C排拿走1個,也是最後一個,你輸 |
實現尼姆遊戲策略的程式範例
上述的策略可以寫成程式,以下就是Python的範例:
import functools
MISERE = 'misere'
NORMAL = 'normal'
def nim(heaps, game_type):
"""Computes next move for Nim, for both game types normal and misere.
if there is a winning move:
return tuple(heap_index, amount_to_remove)
else:
return "You will lose :("
- mid-game scenarios are the same for both game types
>>> print(nim([1, 2, 3], MISERE))
misere [1, 2, 3] You will lose :(
>>> print(nim([1, 2, 3], NORMAL))
normal [1, 2, 3] You will lose :(
>>> print(nim([1, 2, 4], MISERE))
misere [1, 2, 4] (2, 1)
>>> print(nim([1, 2, 4], NORMAL))
normal [1, 2, 4] (2, 1)
- endgame scenarios change depending upon game type
>>> print(nim([1], MISERE))
misere [1] You will lose :(
>>> print(nim([1], NORMAL))
normal [1] (0, 1)
>>> print(nim([1, 1], MISERE))
misere [1, 1] (0, 1)
>>> print(nim([1, 1], NORMAL))
normal [1, 1] You will lose :(
>>> print(nim([1, 5], MISERE))
misere [1, 5] (1, 5)
>>> print(nim([1, 5], NORMAL))
normal [1, 5] (1, 4)
"""
print(game_type, heaps, end=' ')
is_misere = game_type == MISERE
is_near_endgame = False
count_non_0_1 = sum(1 for x in heaps if x > 1)
is_near_endgame = (count_non_0_1 <= 1)
# nim sum will give the correct end-game move for normal play but
# misere requires the last move be forced onto the opponent
if is_misere and is_near_endgame:
moves_left = sum(1 for x in heaps if x > 0)
is_odd = (moves_left % 2 == 1)
sizeof_max = max(heaps)
index_of_max = heaps.index(sizeof_max)
if sizeof_max == 1 and is_odd:
return "You will lose :("
# reduce the game to an odd number of 1's
return index_of_max, sizeof_max - int(is_odd)
nim_sum = functools.reduce(lambda x, y: x ^ y, heaps)
if nim_sum == 0:
return "You will lose :("
# Calc which move to make
for index, heap in enumerate(heaps):
target_size = heap ^ nim_sum
if target_size < heap:
amount_to_remove = heap - target_size
return index, amount_to_remove
if __name__ == "__main__":
import doctest
doctest.testmod()
必勝策略的證明
以下是必勝策略的證明,由C. Bouton所提出。
定理:在normal版本的尼姆遊戲中,第一個玩家有必勝的策略,若且唯若各排棋子數的尼姆和不為零。否則,第二個玩家有必勝的策略。
證明:注意尼姆和(⊕)遵守一般加法的結合律及交換律,還有另外一個性質x ⊕ x = 0。
令x1, ..., xn是移動前的各排棋子數,y1, ..., yn是移動後的各排棋子數。令 s = x1 ⊕ ... ⊕ xn且 t = y1 ⊕ ... ⊕ yn。若這次是移動第k排的棋子,可得xi = yi針對所有 i ≠ k,且xk > yk。依照⊕的性質,可得
t = 0 ⊕ t = s ⊕ s ⊕ t = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn) = s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (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二進位表示法中最左邊1的位置,選擇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[4]。自1940年的5月11日到10月27日為止,在六週的週期內只有少數的人可以打敗Nimatron:若他們勝了,會得到一個稱為Nim Champ的硬幣[5][6]。尼姆遊戲也是最早電腦化的游戲。Ferranti曾製作可以玩尼姆遊戲的Nimrod電腦,在1951年的英國節上展示。1952年時,W. L. Maxon公司的工程師Herbert Koppel、 Eugene Grant和Howard Bailer開發了重達23公斤(50英磅)的機器,可以和人玩尼姆遊戲,而且多半會贏[7]。Tinkertoy也可以製作尼姆遊戲機[8]。
尼姆遊戲是馬丁·加德納在《科學美國人》(Scientific American)雜誌中,1958年2月〈數學遊戲專欄〉的主題。在1961年法國新浪潮電影《去年在馬倫巴》中,有玩過特定版本的尼姆遊戲,而且有象徵的重要性[9]。
類似遊戲
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。此遊戲可以讓最後一個人贏或是輸。
相關條目
參考資料
- ^ Jorgensen, Anker Helms, Context and driving forces in the development of the early computer game Nimbi, IEEE Annals of the History of Computing, 2009, 31 (3): 44–53, MR 2767447, doi:10.1109/MAHC.2009.41,
The two-person mathematical game Nim, which many believe originated in China, is probably one of the oldest games in the world.
- ^ Bouton, C. L., Nim, a game with a complete mathematical theory, 數學年刊, 1901–1902, 3 (14): 35–39, JSTOR 1967631, doi:10.2307/1967631
- ^ Khovanova, Tanya; Xiong, Joshua. Nim Fractals. 2014. arXiv:1405.5942
[math.CO].
- ^ Flesch, Rudolf. The Art of Clear Thinking. New York: Harper and Brothers Publishers. 1951: 3.
- ^ ExpoMuseum / New York World's Fair, 1939-'40. www.expomuseum.com. [20 April 2018]. (原始內容存檔於2021-02-24).
- ^ 1940: Nimatron. platinumpiotr.blogspot.com. [20 April 2018]. (原始內容存檔於2018-12-25).
- ^ Grant, Eugene F.; Lardner, Rex. The Talk of the Town – It. The New Yorker. August 2, 1952 [2020-10-13]. (原始內容存檔於2014-01-01).
- ^ Cohen, Harvey A. How to Construct NIM Playing Machine (PDF). [2020-10-13]. (原始內容存檔 (PDF)於2021-02-25).
- ^ Morrissette, Bruce, Games and game structures in Robbe-Grillet, Yale French Studies, 1968, 41 (41): 159–167, JSTOR 2929672, doi:10.2307/2929672. Morrissette writes that Alain Robbe-Grillet, one of the screenwriters for the film, "thought he had invented" the game.