什麼是威佐夫遊戲?
威佐夫遊戲用兩堆物品進行。輪到你時,你可以像尼姆一樣從一堆中取任意數量的物品,也可以同時從兩堆中取相同數量。取走最後一個物品的人獲勝:這個遊戲始終按正常規則進行,因此標準遊戲的反向規則開關和起始堆選項都不適用。
堆的大小來自棋桌設定中的規模選項:5 和 7(小)、9 和 12(中,預設)或 14 和 20(大)。一種常見的形象理解是一枚只能向左、向下或向左下斜走的西洋棋皇后:兩堆就是她到棋盤兩條邊的距離,誰把她走進角落誰就獲勝。
規則變化
| 規則 | 標準尼姆 | 威佐夫遊戲 |
|---|---|---|
| 堆 | 標準尼姆若干堆:預設為 1、3、5、7 個物品,也可在棋桌設定中選擇其他組合。 | 威佐夫遊戲兩堆:在棋桌設定中按規模選擇 5 和 7、9 和 12(預設)或 14 和 20。 |
| 走法 | 標準尼姆從一堆中取走一個或多個物品。 | 威佐夫遊戲要麼從一堆中取走一個或多個物品,要麼從兩堆中取走相同數量。 |
| 目標 | 標準尼姆預設採用反向規則:取走最後一個物品的人輸。設定中可切換為正常規則,即取走最後一個物品的人贏。 | 威佐夫遊戲始終採用正常規則:取走最後一個物品的人贏。 |
| 致勝方法 | 標準尼姆讓各堆數量的尼姆和(按位元互斥或)為零,反向規則的殘局另有變化。 | 威佐夫遊戲輪到走棋一方必輸的局面是 1 和 2、3 和 5、4 和 7、6 和 10、8 和 13 等數對:第 k 對是 k × φ 和 k × φ² 的整數部分,φ 為黃金比例。這裡的起始局面都不是這樣的數對,所以先手可以獲勝。 |
歷史
荷蘭數學家 Willem Abraham Wythoff 於 1907 年在《Nieuw Archief voor Wiskunde》上發表文章「A modification of the game of nim」,公布了這個遊戲及其解。他證明了必輸局面遵循黃金比例。必輸數對中的較小數和較大數構成兩個貝亞蒂數列,它們合起來恰好把每個正整數各列出一次,這也是這個遊戲既出現在賽局著作中、也出現在數論著作中的原因。
Martin Gardner 於 1977 年 3 月在《科學美國人》的「數學遊戲」專欄中介紹了這個遊戲,並稱它在中國以「撿石子」(jiǎn shízǐ)之名流傳。我們沒有找到這一說法的其他來源。