查看“︁威佐夫游戏”︁的源代码

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

[[马丁·加德纳]]认为威佐夫游戏在中国称为“捡石子”<ref>[http://www.cut-the-knot.org/pythagoras/withoff.shtml Wythoff's game at Cut-the-knot] {{Wayback|url=http://www.cut-the-knot.org/pythagoras/withoff.shtml |date=20210209023143 }}, quoting [[马丁·加德纳|Martin Gardner]]'s book ''Penrose Tiles to Trapdoor Ciphers''</ref>。[[荷兰]]数学家{{link-en|威佐夫|Willem Abraham Wythoff}}于1907年发表过一篇论文，从数学角度分析了该游戏。
[[File:Wythoff's_Nim.svg|thumb|right|500x500像素|威佐夫游戏中的后手必胜状态。以左下角为原点向右、上为正方向建立坐标系，以红色标出的小正方形右上角的顶点坐标即为后手必胜状态]]

== 最佳策略 ==
游戏过程中的任何状态都可用一对[[正整数]](<span>n</span>,<span>m</span>)来表示，其中<span>n</span>≤<span>m</span>，分别表示两堆筹码的数目。所有状态分为两种：先手必胜和后手必胜。在双方均采取最佳策略的情况下，前者表示下一个行动的玩家将取胜，后者表示下一个行动的玩家将落败。可见，游戏的最佳策略是从一个先手必胜状态移动到任一后手必胜状态。

对于任一状态(n,m)，可用以下法则[[递归|递归地]]判断此状态是先手必胜还是后手必胜：
# (0,0)为后手必胜状态。
# 若一个状态的后续中存在后手必胜状态，则该状态为先手必胜。
# 若一个状态的全部后续均为先手必胜，则该状态为后手必胜。
例如，由上述第一条、第二条可推出对所有的正整数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为任意自然数且
: <math>n_k = \lfloor k \phi \rfloor = \lfloor m_k \phi \rfloor -m_k \,</math>
: <math>m_k = \lfloor k \phi^2 \rfloor = \lceil n_k \phi \rceil = n_k + k \,</math>
其中φ为黄金分割率，中括号表示[[高斯符號|高斯符号]]，则(<span>n</span><sub><span>k</span></sub>,<span>m</span><sub><span>k</span></sub>)即为第<span>''k''</span>个后手必胜状态。这两个数列在[[整數數列線上大全|整数数列线上大全]]中的编号分别为{{OEIS2C|id=A000201}}和{{OEIS2C|id=A001950}}。

<span>{</span>n<sub>k</sub><span>}和{</span>m<sub>k</sub>}是[[贝亚蒂定理|贝亚蒂列]]，也即满足方程
: <math>\frac{1}{\phi} + \frac{1}{\phi^2} = 1 \,.</math>
根据贝亚蒂定理，这两个数列互为[[补集]]：所有正整数均仅存在于其中的一个数列并只出现一次。

== 参见 ==
* [[尼姆游戏]]
* {{Link-en|Grundy游戏|Grundy's game}}
* {{Link-en|取平方数|Subtract a square}}
* {{Link-en|威佐夫矩阵|Wythoff array}}

== 参考文献 ==
{{Reflist}}

== 外部链接 ==
*{{MathWorld|urlname=WythoffsGame|title=Wythoff's Game}}

[[Category:數學遊戲]]