尼姆游戏
![](http://images.weserv.nl/?url=//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.