跳至內容

威佐夫遊戲

維基百科,自由的百科全書

威佐夫遊戲是一個尼姆遊戲(雙人數學博弈遊戲),規則是兩人輪流取兩堆籌碼,其中取法有兩種:取走一堆中任意個籌碼,或從兩堆中取走相同數目的籌碼。取完所有籌碼的一方獲勝。

馬丁·加德納認為威佐夫遊戲在中國稱為「撿石子」[1]荷蘭數學家威佐夫英語Willem Abraham Wythoff於1907年發表過一篇論文,從數學角度分析了該遊戲。

威佐夫遊戲中的後手必勝狀態。以左下角為原點向右、上為正方向建立坐標系,以紅色標出的小正方形右上角的頂點坐標即為後手必勝狀態

最佳策略

遊戲過程中的任何狀態都可用一對正整數(n,m)來表示,其中nm,分別表示兩堆籌碼的數目。所有狀態分為兩種:先手必勝和後手必勝。在雙方均採取最佳策略的情況下,前者表示下一個行動的玩家將取勝,後者表示下一個行動的玩家將落敗。可見,遊戲的最佳策略是從一個先手必勝狀態移動到任一後手必勝狀態。

對於任一狀態(n,m),可用以下法則遞歸地判斷此狀態是先手必勝還是後手必勝:

  1. (0,0)為後手必勝狀態。
  2. 若一個狀態的後續中存在後手必勝狀態,則該狀態為先手必勝。
  3. 若一個狀態的全部後續均為先手必勝,則該狀態為後手必勝。

例如,由上述第一條、第二條可推出對所有的正整數m,(0,m)和(m,m)均為先手必勝狀態。而(1,2)是後手必勝狀態,因為它的後續(0,1)、(0,2)和(1,1)均為先手必勝狀態。前幾個後手必勝狀態為(0, 0)、(1, 2)、(3, 5)、(4, 7)、(6,10)和(8, 13)。

後手必勝狀態的通式

威佐夫發現後手必勝狀態與黃金分割率有關。具體而言,若k為任意自然數且

其中φ為黃金分割率,中括號表示高斯符號,則(nk,mk)即為第k個後手必勝狀態。這兩個數列在整數數列線上大全中的編號分別為A000201A001950

{nk}和{mk}是貝亞蒂列,也即滿足方程

根據貝亞蒂定理,這兩個數列互為補集:所有正整數均僅存在於其中的一個數列並只出現一次。

參見

參考文獻

  1. ^ Wythoff's game at Cut-the-knot頁面存檔備份,存於網際網路檔案館), quoting Martin Gardner's book Penrose Tiles to Trapdoor Ciphers

外部連結