【专题】Wythoff博弈

Wythoff博弈

基本的威佐夫博弈（Wythoff Game）描述如下：

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，每次至少取一个，多者不限，最后取光者得胜。

我们使用(a, b)来描述一个局面，可以发现(a, b)和(b, a)其实是一样的，所以在此定义a $ $ b。显然(0, 0)是第一个必败态（先手必败局面、奇异局面、P-position），使用P/N-状态或者SG函数可以更容易地分析局面，简单讲就是：“移动可以导致必败态的，此时先手必胜；移动只能导致必胜态的，此时先手必败”。打表可得必败态为(0, 0)、(1, 2)、(3, 5)、(4, 7)、(6, 10)、(8, 13)、(9, 15)、 $ $ 仔细观察，大胆假设，自行求证，对于 $ (a_n, b_n) $ 有以下性质：

1. $ a_n $ 是前面必败态中未出现过的最小自然数

2. $ b_n = a_n + n $

---

博弈过程如下：

• 由 $ a_n $ 是未在前面出现过的最小自然数，所以 $ a_n > a_{n-1} $ ，而 $ (b_n = a_n + n) > (a_{n-1} + n) > (a_{n-1} + n - 1 = b_{n-1}) > a_{n-1} $ ，得出任何自然数都包含于有且仅有一个必败态中。
• 当局面处于必败态时，如果只改变其中一个分量，那么与另一个分量就不在同一个必败态中。如果使两个分量同时减少，那么由于a和b的差值不变，改变后也不会是其它的必败态。得出必败态只能转移到必胜态。
• 当局面处于必胜态(x, y)时，如果与x出现在必败态时的另一个分量 $ a_x $ 或者 $ b_x $ 小于y，那么将y取成 $ a_x $ 或者 $ b_x $ ，局面变为必败态 $ (a_x, x) $ 或者 $ (x, b_x) $ ；否则在两堆同时取走 $ x-a_{y-x} $ ，局面变为必败态 $ (a_{y-x}, b_{y-x}) $。得出必胜态可以转移到必败态。

SG函数打表找出规律，就可以开始推导了，实际上 $ a_n $ 和 $ b_n $ 是Betty序列并满足Betty定理，令 $ A = a_{n}, B = a_{n}+n $ 解方程 $ + = 1 $ 得 $ a = $ 。即对于Wythoff博弈局面(a, b)，当 $ a == (int)((b-a) ) $ 时先手必败，反之先手必胜。

---

Betty定理

Betty定理：

如果两个无理数满足 $ + = 1 $，那么对于两个集合 $ A = {[na]}, B = {[na]}, n Z $ ，可得出 $ A B = , A B = N^{+} $ 。

简单证明如下：

• $ A B = $

  由 $ + = 1 $，且a，b为正，可以得到a，b均大于1，所以[na]的跨度大于1，向下取整不会重复。取整数k使得 $ k A, k B $，那么 $ k < ma < k+1, k < nb < k+1 $ ，化简一下 $ < a < < < $ ，同理 $ < < $ ，两式相加 $ < + < < 1 < k < m + n < k + 1 $ ，与m，n为整数矛盾。

• $ A B = N^{+} $

  取整数k满足 $ k C_{N^{+}}A B $ ，此时必有整数m，n满足 $ [ma] < k < [(m+1)a], [nb] < k < [(n+1)b] $ ，化简一下 $ ma < k - 1 $ ，由于a为无理数，所以有 $ ma < k < (m+1)a - 1 < < $ ，同理 $ < < $ ，两式相加 $ < + < < 1 < m + n < k < k + 1 < m + n + 2 $ ，与m+n和m+n+2间只有一个整数矛盾。