VG 的博弈系列学习笔记（1）：浅谈 Wythoff 游戏
VinstaG173
·
·
个人记录
由于一些原因，此文仅保留 Wythoff 游戏部分，其余部分转移至此。
游戏介绍
威佐夫（Wythoff）游戏，又称威佐夫博弈，是博弈论中的著名游戏之一。
游戏内容：两堆石子，一堆 a 个，一堆 b 个，两位游戏者轮流操作，每次操作可以从一堆中取任意颗石子或者从两堆取同样多石子。谁不能再取，就算谁输。
游戏解法
Wythoff 游戏的解法，就是求出先手能否获胜。以下用整数对 (a,b) 表示两堆石子个数是 a 和 b 的情况。由于 (a,b) 与 (b,a) 是一种情况，所以此处只考虑 a \le b 的情况。
显然， (0,0) 时先手必败。接下来的一个必败情况就是 (1,2)。再往下，就得到 (3,5)。然后是 (4,7),(6,10),(8,13),(9,15),...。
我们设第 i 大的必败情况为 (a_i,b_i)。
根据规律，发现 a_i=\operatorname{mex}(a_1,b_1,a_2,b_2,...,a_{i-1},b_{i-1})（\operatorname{mex}(S) 为集合 S 中最小未出现整数，下同）， b_i=a_i+i。
规律证明
现在证明一个必败状态后继状态不可能是另一个必败状态。
因为 a_i 在前面没有出现过，所以 a_i>a_{i-1}。所以 b_i=a_i+i>a_{i-1}+i-1=b_{i-1}。所以为了使这个情况转化为另一个必败状态，必然要从两堆各取出同样多的石子。所以 a,b 差不变，而其余必败状态 a_j,b_j 差 j 均与 a_i 与 b_i 的差 i 不相等。所以它的所有后继状态均不是必败状态。
下面证明一个必胜状态必有一个后继状态是必败状态。
当 a>a_k,b=b_k 时，只需从 a 堆取出 a-a_k 个即可。 a=a_k,b>b_k 时亦然。
当 $a=a_{k+l}$ 时，若 $b>b_{k+l}$。则如上可证。否则，因为 $b \neq b_{k+l}$，所以 $b<b_{k+l}$。若 $b=b_m$，则满足 $a>a_m,b=b_m$，如上。若 $b=a_m$，因为 $b>a$，所以 $m>k+l$，所以 $0<a_m-a_{k+l}<k+l$，所以将 $b$ 堆取到 $b_{a_m-a_{k+l}}$ 时，a堆将取到 $a_{a_m-a_{k+l}}$ 颗，为一个必败状态。
综上，必胜状态必有一个后继状态是必败状态。
必败状态通项公式：设当前状态为 $(a,b)(a<b)$，则当 $a=\lfloor\frac{\sqrt{5}+1}{2}\rfloor\times(b-a)$ 时该状态为必败状态。
#### 有趣的性质
首先，我们定义 $a_{i+1}-a_i=c_i,b_{i+1}-b_i=d_i$。然后，有 $c_0=a_1=1,d_0=b_1=2$。我们发现， $d_i=c_i+1$。
每当 $d_i=2$ 时， $c_i$数组对应在最后添上一个 $2$；每当 $d_i=3$ 时， $c_i$数组对应在最后添上一个 $1$ 和一个 $2$。递推大概就是这个样子：
```cpp
for(int i=0;;i++)//c,d是vector动态数组
{
d[i]=c[i]+1;
if(d[i]==2)c.push_back(2);
if(d[i]==3)c.push_back(1),c.push_back(2);
}
```
这样就可以求出 $c_i$ 和 $d_i$，然后推出 $a_i,b_i$ 了。
#### Wythoff 和 Fibonacci 那些事
往著名的 Fibonacci 数列 $f_i$ 中，代入 Wythoff 的 $a_i,b_i$ 会出现神奇的事情。
有： $a_{f_i}=f_{i+1}-i \bmod 2$， $b_{f_i}=a_{f_i}+f_i=f_{i+2}-i \bmod 2$。（此处 $f_i$ 数列为 $1,2,3,5,8,\dots$ 且 $i>1$）。
关于 Wythoff 博弈就讲这么多。
两道 Wythoff 博弈的习题：[nyoj161 取石子（四）](http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=161)&[洛谷P2252取石子游戏](https://www.luogu.org/problemnew/show/P2252)
代码P2252:
```cpp
#include<cmath>
#include<cstdio>
using namespace std;
long long a,b;
int main()
{
scanf(" %lld %lld",&a,&b);
if(a>b)
{
long long t=a;a=b;b=t;
}
long long c=b-a;
int d=((sqrt(5.0)+1.0)/2.0*c);
if(a==d)printf("0");
else printf("1");
return 0;
}
```