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