浅谈威佐夫游戏

概述

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

后手必胜的通式

威佐夫发现后手必胜状态与黄金分割率有关。具体而言,若k为任意自然数且
{\displaystyle n_{k}=\lfloor k\phi \rfloor =\lfloor m_{k}\phi \rfloor -m_{k}\,}
{\displaystyle m_{k}=\lfloor k\phi ^{2}\rfloor =\lceil n_{k}\phi \rceil =n_{k}+k\,}
其中\phi为黄金分割率,中括号表示高斯符号,则(n_k,m_k)即为第k个后手必胜状态。
\lbrace n_k\rbrace\lbrace m_k\rbrace是贝亚蒂列,也即满足方程
{\displaystyle {\frac {1}{\phi }}+{\frac {1}{\phi ^{2}}}=1\,.}
根据贝亚蒂定理,这两个数列互为补集:所有正整数均仅存在于其中的一个数列并只出现一次。

理解

设筹码数为(a, b),这个数对的顺序与游戏的结果并无关系,因此不妨设a\ge b.
我们发现(a, b)可以转移到(a-x, b), (a, b-x), (a-x, b-x)这三类状态,反过来,如果(x, y)是必败态的话,则(x, y+d), (x+d, y), (x+d, y+d) (d\ge 0)均为必胜态,由于(0, 0)是必败态,我们不妨将这些状态以平面坐标系上的点来代替,可以得到另一些必败态。我们将必胜态的点在坐标系用一条射线(这个射线是怎么来的后面会讲到)来将它覆盖,对于一个点(x,y),若它没有被端点在它左下方的射线覆盖,则它代表一个必败态;并且,以(x,y+1)为端点的平行y轴向上的射线、以(x+1,y+1)为端点与x轴夹角为\frac {\pi} {4}的向右上射线和以(x+1,y)为端点的平行于x轴向右的射线又覆盖了一些新的必胜点。如下图:

Wythoff

我们发现这些必败点似乎都满足一些优美的规律,我们将前几个列出来:
(2,1), (5,3), (7, 4), …
是的,后来就有个荷兰的数学家威佐夫从数学角度得到了结论,胜负状态和黄金分割有关。由于证明过于硬核,我们直接来看结论:

对于当前的状态(a, b),设a\ge b,若\lfloor (a-b)\ast \frac {1+\sqrt 5} {2}\rfloor=b,那么这个状态是必败态,否则都是必胜态。

参考资料

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注