威佐夫游戏

威佐夫游戏是一个尼姆游戏(双人数学博弈游戏),规则是两人轮流取两堆筹码,其中取法有两种:取走一堆中任意个筹码,或从两堆中取走相同数目的筹码。取完所有筹码的一方获胜。

马丁·加德纳认为威佐夫游戏在中国称为“捡石子”[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

外部链接