尼姆遊戲

尼姆遊戲中選擇一排，再由這一排中取走一個或者多個，依規則不同，拿走最後一個的可能是輸家，也有可能是贏家。當指定相應數量時，一堆這樣的棋子稱作一個尼姆堆。古代就有許多尼姆遊戲的變體。最早歐洲有關尼姆遊戲的在16世紀，目前使用的名稱是由哈佛大學的Charles L. Bouton命名，他也在1901年提出了此遊戲的完整理論，不過沒有說明名稱的由來。尼姆遊戲最常見的玩法是拿到最後一個棋子的人輸，下一個遊戲者可以輕易的獲勝。下一個遊戲者可以將數量最多的這排棋子全部拿走或只留一個。剩下的各排都只有一個棋子。若是misère版本，下一個遊戲者下完之後，只要留下奇數排就會勝利，若是normal版本，下一個遊戲者下完之後，只要留下偶數排就會勝利。normal版本的尼姆遊戲。三排棋子尼姆遊戲的演進圖和演進圖的三個分支相同。遊戲玩法以及說明.normal版本是由二位遊戲者一起玩，有三排棋子，各排的棋子為任意正整數。二位遊戲者輪流選一排棋子，拿走上面至少一個棋子，也可以拿同一排的多個棋子。normal版本的目的是要拿到最後一個棋子。misère版本的目的就是要讓對方被迫拿走最後一個棋子。以下是normal版本的遊戲，由愛麗絲與鮑伯二個人玩，三排棋子分別有三個、四個及五個棋子。必勝組態.尼姆遊戲的策略就是在拿完棋子後，使棋子個數符合以下任何一個組態，接下來再輪到時，一定可以再拿走適當數量的棋子，使棋子個數仍符合以下任何一個組態。normal版本和misere版本的差別只在最後一兩步，前面都相同：其中有出現"n"和"m"，是任何正整數，"n"和"m"可以相同。數學理論.尼姆遊戲在數學上是已解遊戲，針對任意排數及個數的初始狀態都已有解法，而且有簡單的方式可以判斷哪一個遊戲者會勝利，並且此遊戲者要如何取子才會勝利。這遊戲理論的關鍵是在各排個數在二進位制下XOR位操作的結果，此操作也稱為是在GF(2)中的向量加法，以下也使用此一名稱。"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版本。前面的策略都一樣，只到只剩一排的棋子超過一個。以下是棋子數分別是3, 4, 5個，在misère版本的玩法：實現尼姆遊戲策略的程式範例.上述的策略可以寫成程式，以下就是Python的範例：import functoolsMISERE = '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»&gt; print(nim([1, 2, 3], MISERE))misere [1, 2, 3] You will lose :(»&gt; print(nim([1, 2, 3], NORMAL))normal [1, 2, 3] You will lose :(»&gt; print(nim([1, 2, 4], MISERE))misere [1, 2, 4] (2, 1)»&gt; print(nim([1, 2, 4], NORMAL))normal [1, 2, 4] (2, 1)- endgame scenarios change depending upon game type»&gt; print(nim([1], MISERE))misere [1] You will lose :(»&gt; print(nim([1], NORMAL))normal [1] (0, 1)»&gt; print(nim([1, 1], MISERE))misere [1, 1] (0, 1)»&gt; print(nim([1, 1], NORMAL))normal [1, 1] You will lose :(»&gt; print(nim([1, 5], MISERE))misere [1, 5] (1, 5)»&gt; print(nim([1, 5], NORMAL))normal [1, 5] (1, 4)print(game_type, heaps, end=' ')is_misere = game_type == MISEREis_near_endgame = Falsecount_non_0_1 = sum(1 for x in heaps if x &gt; 1)is_near_endgame = (count_non_0_1  "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"位元也不是零。令"yk" = "s" ⊕ "xk"，可以聲稱 "yk" &lt; "xk"："xk"和"yk"所有d左邊的位元都相同，"d"位元從1變為0，剩下位元的變化最多是2"d"−1。因此接下來的遊戲者可以在第"k'排拿走"xk"− "yk"個棋子，則"t" = "s" ⊕ "xk" ⊕ "yk" (by (*))= "s" ⊕ "xk" ⊕ ("s" ⊕ "xk")= 0.misère版本的策略剛剛已經看過，只有在只剩一排的棋子是二個或二個以上時才不同。在這種情形"s" ≠ 0，接下來玩的人有必勝策略，若是normal版本，就是設法留下偶數排的棋子，每排都只有一個棋子，misère版本則反過來，設法留下奇數排的棋子，每排都只有一個棋子。社會文化.在1939年紐約世界博覽會中，西屋電氣有展示一個機器，會玩尼姆遊戲的。自1940年的5月11日到10月27日為止，在六週的週期內只有少數的人可以打敗Nimatron：若他們勝了，會得到一個稱為Nim Champ的硬幣。尼姆遊戲也是最早電腦化的遊戲。曾製作可以玩尼姆遊戲的Nimrod電腦，在1951年的上展示。1952年時，W. L. Maxon公司的工程師Herbert Koppel、 Eugene Grant和Howard Bailer開發了重達的機器，可以和人玩尼姆遊戲，而且多半會贏。也可以製作尼姆遊戲機。尼姆遊戲是馬丁·加德納在《科學美國人》雜誌中，1958年2月〈〉的主題。在1961年法國新浪潮電影《去年在馬倫巴》中，有玩過特定版本的尼姆遊戲，而且有象徵的重要性。類似遊戲.subtraction game.另一個有點類似的遊戲稱為，會先列出總數，以及每一次可以拿走的最大數量。可能每一次只能拿走1個、2個...至k個。例如在《》節目中的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 12 41 5, 6 或 72 81 9, 10 或 112 121 13, 14 或 152 161 17, 18 或 192 201 21100遊戲.另一個類似的遊戲是100遊戲：從0開始加，每一次可以加1到10之間的任一個整數，數到100的人勝利。必勝的策略是搶到類似01、12、23、34……、89的數字，接下來另一遊戲者不論加多少，都設法搶到下一個01、12、23、34……、89的數字。只要到89之後，接下來不論對方加多少，都可以再加數字使結果為100，因此必勝。多排尼姆的規則.另一個版本的尼姆，是允許在每一排中取走相同數量的棋子。迴圈尼姆.另一種尼姆的變體是，將一定數量的棋子擺成圓形，二個遊戲者輪流取棋子，可以取相鄰的一個、二個或三個棋子。以下是一個例子：一開始取走三個棋子_ . . . . . . . _ _接下來又取走三個棋子_ . _ _ _ . . . _ _又拿走一個棋子_ . _ _ _ . . _ _ _最後剩下三個棋子，但是不相鄰，無法一次取走。Grundy遊戲.也是尼姆遊戲的變體，一開始有一排特定數量的棋子，遊戲者要輪流將某一排棋子分為二排數量不同，且都不為0的棋子。例如6個棋子可以分為5+1、4+2，但不能分為3+3。此遊戲可以讓最後一個人贏或是輸。