尼姆游戏
维基百科,自由的 encyclopedia
尼姆游戏(英语: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]。