尼姆游戏
維基百科,自由的 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]。