【专题】Wythoff博弈

Wythoff博弈

基本的威佐夫博弈(Wythoff Game)描述如下:

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

我们使用(a, b)来描述一个局面,可以发现(a, b)和(b, a)其实是一样的,所以在此定义a $ \le $ b。显然(0, 0)是第一个必败态(先手必败局面、奇异局面、P-position),使用P/N-状态或者SG函数可以更容易地分析局面,简单讲就是:“移动可以导致必败态的,此时先手必胜;移动只能导致必胜态的,此时先手必败”。打表可得必败态为(0, 0)、(1, 2)、(3, 5)、(4, 7)、(6, 10)、(8, 13)、(9, 15)、 $ \cdots\ $ 仔细观察,大胆假设,自行求证,对于 $ (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 $ 解方程 $ \frac{1}{a} + \frac{1}{a+1} = 1 $ 得 $ a = \frac{\sqrt{5} + 1}{2} $ 。即对于Wythoff博弈局面(a, b),当 $ a == (int)((b-a) \times \frac{\sqrt{5} + 1}{2}) $ 时先手必败,反之先手必胜。


Betty定理

Betty定理:

如果两个无理数满足 $ \frac{1}{a} + \frac{1}{b} = 1 $,那么对于两个集合 $ A = \{[na]\}, B = \{[na]\}, n \in Z $ ,可得出 $ A \cap B = \varnothing, A \cup B = N^{+} $ 。

简单证明如下:

  • $ A \cap B = \varnothing $

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

  • $ A \cup B = N^{+} $

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

_/_/_/_/_/ EOF _/_/_/_/_/