尼姆游戏

尼姆游戏（英语：Nim），又译为拈，是一种两个人玩的回合制数学战略游戏。游戏者轮流从几排棋子（或者任何道具）中选择一排，再由这一排中取走一个或者多个，依规则不同，拿走最后一个的可能是输家，也有可能是赢家。当指定相应数量时，一堆这样的棋子称作一个尼姆堆。古代就有许多尼姆游戏的变体^[1]。最早欧洲有关尼姆游戏的参考资料是在16世纪，目前使用的名称是由哈佛大学的Charles L. Bouton命名，他也在1901年提出了此游戏的完整理论^[2]，不过没有说明名称的由来。

尼姆游戏最常见的玩法是拿到最后一个棋子的人输（misère game）。尼姆游戏也可以改为拿到最后一个棋子的人赢（normal play）。大部分类似的游戏都是最后一个棋子的人赢，不过这不是尼姆游戏最常见的玩法。不论哪一种玩法，只要刚好剩下一排的棋子是二个或二个以上（其他排可能没有棋子，或是只有一个），下一个游戏者可以轻易的获胜。下一个游戏者可以将数量最多的这排棋子全部拿走或只留一个。剩下的各排都只有一个棋子。若是misère版本，下一个游戏者下完之后，只要留下奇数排就会胜利，若是normal版本，下一个游戏者下完之后，只要留下偶数排就会胜利。

normal版本的尼姆游戏（也就是尼姆数系统）是斯普莱格–格隆第定理的基础，其中提到在normal版本中，每一个normal版本的无偏博弈（从任何一个局势出发，双方可以采取完全相同的行动，也就是说棋盘上没有颜色的区分）都等价于一个特定大小的尼姆堆。所有的normal版本的无偏博弈都可以给与尼姆值，但misère版本的就不一定。只有温驯游戏（英语：Genus theory）才能用misère版本尼姆的策略来进行。尼姆游戏是一种特殊的偏序游戏（英语：poset game），其中的偏序关系包括了不交集的全序关系（堆）。三排棋子尼姆游戏的演进图和Ulam-Warburton自动机（英语：Ulam-Warburton automaton）演进图的三个分支相同^[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 \oplus y$ ，以和一般的和区别 $x + y$ 。像3, 4, 5的尼姆和计算如下：

二进制	十进制	备注
011₂	3₁₀	A排
100₂	4₁₀	B排
101₂	5₁₀	C排
010₂	2₁₀	三排数字的尼姆和，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的尼姆和(Y_i)，找到尼姆和(Y_i)比该排棋子数少的那一排，接下来就要取走这一排的棋子，使该排棋子数等于该行的尼姆和(Y_i)。以上例中，原来各排棋子数的尼姆和是 $X = 3 \oplus 4 \oplus 5 = 2$ 。A=3、B=4、C=5且X=2，因此得到

Y_A = A ⊕ X = 3 ⊕ 2 = 1 [因为 (011) ⊕ (010) = 001 ]

Y_B = B ⊕ X = 4 ⊕ 2 = 6

Y_C = C ⊕ X = 5 ⊕ 2 = 7

因此下一步是取走A排的棋子，使其数量变1（拿走二个棋子）。

有一个特别简单的例子，是只剩二排的情形，其策略是在个数较多的那牌拿走部分棋子，使两者数量相同。接下来对手不论怎么下，都继续使二排的数量相同，最后即可胜利。

若是玩misère版本。前面的策略都一样，只到只剩一排的棋子超过一个（二个或二个以上）时才有不同。此时的策略都是针对超过一个棋子的那排棋子取子，使留下来的每一排都只有一个棋子。接下来玩的人只能从这几排中选一排拿走。取子可能是那排全部取完，或是只剩一个，视游戏版本而定，在玩misère版本（拿到最后一个棋子的输）时，要使留下来的排数是单数（因此对方会拿到最后一个棋子），在玩normal版本游戏时，要使留下来的排数是偶数。（因此自己会拿到最后一个棋子）。

以下是棋子数分别是3, 4, 5个，在misère版本的玩法：

A	B	C	尼姆和	下法
3	4	5	010₂=2₁₀	我从A排拿走2个，使剩下的尼姆和为0
1	4	5	000₂=0₁₀	你从C排拿走2个
1	4	3	110₂=6₁₀	我从B排拿走2个
1	2	3	000₂=0₁₀	你从C排拿走1个
1	2	2	001₂=1₁₀	我从A排拿走1个
0	2	2	000₂=0₁₀	你从C排拿走1个
0	2	1	011₂=3₁₀	我将B排的都拿走，只留下C排（使剩下的排数是奇数）（若是normal版本，我会从C排拿走1个，使剩下的排数是偶数）
0	0	1	001₂=1₁₀	你从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。

令x₁, ..., x_n是移动前的各排棋子数，y₁, ..., y_n是移动后的各排棋子数。令 s = x₁ ⊕ ... ⊕ x_n且 t = y₁ ⊕ ... ⊕ y_n。若这次是移动第k排的棋子，可得x_i = y_i针对所有 i ≠ k，且x_k > y_k。依照⊕的性质，可得

    t = 0 ⊕ t
      = s ⊕ s ⊕ t
      = s ⊕ (x₁ ⊕ ... ⊕ x_n) ⊕ (y₁ ⊕ ... ⊕ y_n)
      = s ⊕ (x₁ ⊕ y₁) ⊕ ... ⊕ (x_n ⊕ y_n)
      = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (x_k ⊕ y_k) ⊕ 0 ⊕ ... ⊕ 0
      = s ⊕ x_k ⊕ y_k
 
(*) t = s ⊕ x_k ⊕ y_k.

此定理会由以下二个引理推导而来。

引理1：若s = 0，则无论如何移动，接下来t ≠ 0。

证明：若没有任何可以移动的棋子，此引理空虚的真（英语：vacuous truth）（依定义，接下来要玩的游戏者输，因为在他前一手的游戏者拿了最后一个棋子）。否则，任何k排的移动都会因为(*)，造成 t = x_k ⊕ y_k。因为x_k ≠ y_k，上述数字不为0。

引理2：若s ≠ 0，有可能让t = 0.

证明：令d是s二进制表示法中最左边１的位置，选择k使x_k的第d位元也不是零。（这个k一定存在，不然s的第d位元都是零了）令y_k = s ⊕ x_k，可以声称 y_k < x_k：x_k和y_k所有d左边的位元都相同，d位元从1变为0（数值减少2^d），剩下位元的变化最多是2^d−1。因此接下来的游戏者可以在第k'排拿走x_k− y_k个棋子，则

t = s ⊕ x_k ⊕ y_k           (by (*))
  = s ⊕ x_k ⊕ (s ⊕ x_k)
  = 0.

misère版本的策略刚刚已经看过，只有在只剩一排的棋子是二个或二个以上时才不同。在这种情形s ≠ 0，接下来玩的人有必胜策略，若是normal版本，就是设法留下偶数排的棋子，每排都只有一个棋子，misère版本则反过来，设法留下奇数排的棋子，每排都只有一个棋子。

社会文化

在1939年纽约世界博览会中，西屋电气有展示一个机器，会玩尼姆游戏的Nimatron（英语：Nimatron）^[4]。自1940年的5月11日到10月27日为止，在六周的周期内只有少数的人可以打败Nimatron：若他们胜了，会得到一个称为Nim Champ的硬币^[5]^[6]。尼姆游戏也是最早电脑化的游戏。Ferranti（英语：Ferranti）曾制作可以玩尼姆游戏的Nimrod电脑，在1951年的英国节（英语：Festival of Britain）上展示。1952年时，W. L. Maxon公司的工程师Herbert Koppel、 Eugene Grant和Howard Bailer开发了重达23千克（50英磅）的机器，可以和人玩尼姆游戏，而且多半会赢^[7]。Tinkertoy（英语：Tinkertoy）也可以制作尼姆游戏机^[8]。

尼姆游戏是马丁·加德纳在《科学美国人》（Scientific American）杂志中，1958年2月〈数学游戏专栏（英语：Mathematical Games column）〉的主题。在1961年法国新浪潮电影《去年在马伦巴》中，有玩过特定版本的尼姆游戏，而且有象征的重要性^[9]。

类似游戏

subtraction game

另一个有点类似的游戏称为subtraction game（英语：subtraction game），会先列出总数，以及每一次可以拿走的最大数量。可能每一次只能拿走1个、2个...至k个。例如在《Survivor: Thailand（英语：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，因此必胜。

多排尼姆的规则

另一个版本的尼姆，是允许在每一排中取走相同数量的棋子。

循环尼姆

另一种尼姆的变体是循环尼姆（英语：Kayles），将一定数量的棋子摆成圆形，二个游戏者轮流取棋子，可以取相邻的一个、二个或三个棋子。以下是一个例子：

. . . . . . . . . .

一开始取走三个棋子

_ . . . . . . . _ _

接下来又取走三个棋子

_ . _ _ _ . . . _ _

又拿走一个棋子

_ . _ _ _ . . _ _ _

最后剩下三个棋子，但是不相邻，无法一次取走。

Grundy游戏

Grundy游戏（英语：Grundy's game）也是尼姆游戏的变体，一开始有一排特定数量的棋子，游戏者要轮流将某一排棋子分为二排数量不同，且都不为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.

外部链接

50-pound computer plays Nim- The New Yorker magazine "Talk of the Town" August, 1952 （页面存档备份，存于互联网档案馆）

[1] 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.

[2] Bouton, C. L., Nim, a game with a complete mathematical theory, 数学年刊, 1901–1902, 3 (14): 35–39, JSTOR 1967631, doi:10.2307/1967631

[3] Khovanova, Tanya; Xiong, Joshua. Nim Fractals. 2014. arXiv:1405.5942  [math.CO].

[4] Flesch, Rudolf. The Art of Clear Thinking. New York: Harper and Brothers Publishers. 1951: 3.

[5] ExpoMuseum / New York World's Fair, 1939-'40. www.expomuseum.com. [20 April 2018]. （原始内容存档于2021-02-24）.

[6] 1940: Nimatron. platinumpiotr.blogspot.com. [20 April 2018]. （原始内容存档于2018-12-25）.

[7] Grant, Eugene F.; Lardner, Rex. The Talk of the Town – It. The New Yorker. August 2, 1952 [2020-10-13]. （原始内容存档于2014-01-01）.

[8] Cohen, Harvey A. How to Construct NIM Playing Machine (PDF). [2020-10-13]. （原始内容存档 (PDF)于2021-02-25）.

[9] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]