博弈论入门
FLY_lai
·
·
算法·理论
贾志豪：SG 游戏的若干变形
【定义】
-
公平组合游戏（Impartial Game）。
需要满足：
-
非公平组合游戏（Partizan Game）与公平组合游戏的区别在于在非公平组合游戏中，游戏者在某一确定状态可以做出的决策集合与游戏者有关。大部分的棋类游戏都 不是 公平组合游戏，如国际象棋、中国象棋、围棋、五子棋等（因为双方都不能使用对方的棋子）。
-
反常游戏（Misère Game）按照传统的游戏规则进行游戏，但是其胜者为第一个无法行动的玩家。以 Nim 游戏为例，Nim 游戏中取走最后一颗石子的为胜者，而反常 Nim 游戏中取走最后一颗石子的为败者。
-
P-set 与 N-set。一个局面是 P-set 当且仅当从这个局面开始先手必败，N-set 相反。
P-set 每个后继状态都是 N-set，N-set 存在一个后继是 P-set。
-
有向图游戏。在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。大部分的公平组合游戏都可以转换为有向图游戏。
-
SG 定理。一个局面 X 的 sg 值 sg(X) 定义为 X 所有后继局面 sg 值的 \operatorname{mex}。
若有多个游戏 X_1,X_2,X_3,\dots,X_k 共同组合成游戏 X，有 sg(X)=sg(X_1)\oplus sg(X_2)\oplus\cdots\oplus sg(X_k)。
一个局面先手必败 \iff 其 sg 值为 0。
证明一下 SG 定理。记 k 个游戏上位于局面 s_1\sim s_k，共同构成大游戏的局面 s。
证明几个命题：
-
记 $p=sg(s)$，设 $p$ 的最高二进制位为 $bit$。根据定义，$sg(s_1)\sim sg(s_k)$ 里有奇数个数 $bit$ 位上是 $1$，所以我们总能取一个 $s_*$ 使得 $sg(s_*)$ 在 $bit$ 位上是 $1$。
$sg(s_*)\oplus p<sg(s_*)$，这是因为第 $bit$ 位从 $1$ 变 $0$，其余变化都是在 $<bit$ 位做的。因为 $sg(s_*)$ 是后继 $sg$ 值的 $\mathrm{mex}$，所以它能到达所有 $<sg(s_*)$ 的 $sg$ 值，也就能到达 $sg(s_*)\oplus p$。这么走之后，$sg(s')=sg(s)\oplus p=0$。
-
若能走到 $sg(s')=0$，设这一步是 $s_*\rightarrow s_*'$。那么 $sg(s_*')=sg(s_*)$，根据 $\mathrm{mex}$ 的性质应该有 $sg(s_*)>sg(s_*')$，矛盾。
-
没有后继的局面 sg(s)=0。
根据定义显然。
证毕。
【例题与策略】
【copy 策略】
copy 策略是利用局面对称性行动的策略。一般有这样的表现形式：
-
当 A 行动时，B 总能对称地行动，那么 B 就有必胜策略（A 无论怎么走 B 都能走）。
-
或者若 B 能采用某种策略使得 A 无法行动，那么 A 可以凭借先手优势先采用这个策略让 B 无法行动。
例一：Chomp 游戏
给定一个 n\times m 的矩形。一次操作为选择某个格子 (i,j) 并删除它和它右下方的所有格子。删了 (1,1) 的人输。
学会改造局面，变成公平组合游戏。
从小例子出发找规律。
乍一看这个问题不属于公平组合游戏：删了 (1,1) 的人输，而不是无法行动的输。但事实上这依然是公平组合游戏，我们在一开始就把 (1,1) 视作不存在，就变成无法行动者输了。
那这个问题怎么做呢？不妨从小情况出发。
-
-
-
多玩几个例子，发现全是先手胜。我们大胆猜想：后手必胜当且仅当 n=m=1。
这是可以证明的：核心思想就是如果后手能获胜，我们就偷他的策略。
假设某 n,m>1 是 P-set。
-
让先手取 (n,m)。因为 n,m 是 P-set，现在肯定是 N-set。
-
假设后手取了 (x,y)，让 N-set 转化到 P-set。
-
那么先手在第一步就可以取 (x,y)。此时后手面临一个 P-set。
所以先手必胜。
例二：Gamegame
无题号。
例三：Euclid's game
POJ2348。
初始有两个数 a,b，不妨 a\le b。两人轮流行动。一次行动选择 k\ge 1，令 b\leftarrow b-ka，但是要保证依然非负。谁上手时出现 0 了谁就输。
---
一个显然的情况是 $a=0$ 时先手必败。
另一个简单的情况是 $b<2a$，这时先手只有一种方案：$(a,b)\rightarrow (b-a,a)$。我们可以直接模拟，如果后继状态是 P-set 当前状态就是 N-set。根据辗转相除法，这样递归只需要 $O(\log V)$ 次就能处理这种情况。
那么剩下的就是 $b\ge 2a$ 的情况了。我们发现这种情况先手第一步的可能性很多！大胆猜想：这种情况下先手必胜。
这里用的方法和例一类似。如果 B 有策略使得 A 进入 P-set，A 可以采用 B 的策略。
反证，设此时 $(a,b)$ 是 P-set。
1. 不妨先手让 $(a,b)\rightarrow (a,b-a)$。
2. 因为 $b\ge 2a$，所以 $b-a\ge a$，所以后手只能 $(a,b-a)\rightarrow (a,b-ka)$。
3. 那先手就可以 $(a,b)\rightarrow (a,b-ka)$。
所以 $b\ge 2a$ 时先手必胜。
### 例四：Candy Piles
[AGC002E Candy Piles](https://atcoder.jp/contests/agc002/tasks/agc002_e)
有 $n$ 堆糖果。第 $i$ 堆有 $a_i$ 个。两人轮流操作，一次操作为两者之一：
1. 吃掉最多的那堆。
2. 每堆吃掉一个。
谁不能吃就输了。问谁有必胜策略。
$n\le 10^5,a_i\le 10^9$。
---
**巧妙的 trick**。
把 $a$ 从大到小排序。$\{a_i\}$ 视作一个不断下降的柱状图。
所以每次操作等价于去掉最左侧的列或者最下方的行。
这里可以 DP 了：$dp[i][j]$ 表示保留上方 $i$ 行，右侧 $j$ 列开始玩，是先手必胜还是先手必败。复杂度 $O(nV)$。
但这样显然过不了，我们进一步转化：从左下角出发，每一步向上或向右走。
看作谁走到边界谁就输。
令 $f(i,j)=0/1$ 表示从 $(i,j)$ 出发是先手必胜/必败。直接递推还是 $O(nV)$，但可以找规律了：$f(i,j)=f(i+1,j+1)$！！！
1. 若 $f(i,j)=0$，那么 $f(i+1,j)=f(i,j+1)=1$（必败只能到必胜）。若 $f(i+1,j+1)\neq 0$，那么 $f(i+2,j)=f(i,j+2)=0$（必胜可以到必败）。同理有 $f(i+2,j+1)=f(i+1,j+2)=1$。那 $(i+1,j+1)$ 只能到必胜，所以 $f(i+1,j+1)=0$。
2. 若 $f(i,j)=1$，那么 $f(i+1,j),f(i,j+1)$ 里有 $0$，那 $f(i+1,j+1)=1$。
所以 $(0,0)$ 的答案等于 $(x,x)$ 的答案，直接一直往右上方走，走到终点就可以分类讨论了。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int n, a[N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1, greater<int>());
for (int i = 1; i <= n; i++)
if (i + 1 > a[i + 1]) {
int j = 0;
for (; a[j + i + 1] == i; j++);
if (((a[i] - i) & 1) || (j & 1))
puts("First");
else
puts("Second");
return 0;
}
return 0;
}
```
## 【Nim 游戏及其拓展】
### 例零：Nim 游戏
有 $n$ 堆石子各 $a_1\sim a_n$ 个，每次选一堆取 $\ge 1$ 个。谁不能取就输。
---
结论：$a_1\oplus\cdots\oplus a_n=0\iff$ 先手必败。
直接上 SG 定理。一堆 $x$ 大小的石子等价于 $x+1$ 个点编号 $0\sim x$，点 $i$ 向 $0\sim i-1$ 连边。容易看到 $sg(x)=x$。那么 $n$ 堆石子就是 $n$ 个游戏的组合，SG 值是它们的异或。
当然也可以不用 SG 定理本身，但是证明和 SG 定理类似。
### 例一：巴什博弈
Nim 游戏，额外限制一次最多拿 $m$ 颗。
---
SG 定理。类似构图，但是 $i$ 向 $i-m\sim i-1$ 连边。得到 $sg(x)=x\bmod (m+1)$。
所以 $b_i=a_i\bmod (m+1)$，$b_1\oplus b_2\oplus\cdots\oplus b_n=0\iff $ 先手必败。
### 例二：Northcott Game
[Northcott Game - HDU 1730](https://vjudge.net/problem/HDU-1730)
有一个 $n\times m$ 的棋盘，每行恰有一黑一白两个棋子。黑方先行。
一次操作可以选一行，把己方棋子移动到这一行的任何一个空格，但是不允许越过敌方棋子。谁动不了就输。
---
每行是独立的，只需算出每行的 SG 值异或起来即可。
那一行的 SG 怎么算呢？乍一看，根本用不了 SG 定理。因为这根本不是公平组合游戏：只能动自己的棋子。但仔细分析，是可以转化为 Nim 游戏的。
不妨黑在左、白在右。首先，在两颗棋子相对距离不变的情况下，黑方肯定希望左侧的格子越多越好，因为多了可以增加一个落脚点，即使放着不动也是和少了一样。
进而得出结论：向对手反方向移动是没有意义的。如果黑方向左移动 $d$ 个格子，白方也可以跟着向左移动 $d$ 个。此时相对距离不变，黑方左侧格子更少了，肯定不优。
所以，双方只会相向而行。那么游戏的胜负之和两颗棋子的相对距离有关。记相对距离为 $x$，发现这实际上等价于一堆 $x$ 个石子的经典 Nim 游戏。
因此 $dist_1\oplus dist_2\oplus\cdots\oplus dist_n=0\iff $ 先手必败。
### 例三：Staircase Nim
有 $n$ 堆石子，放在高度为 $1\sim n$ 的阶梯上，第 $i$ 堆有 $a_i$ 个。每次选择一堆里 $\ge 1$ 个石子放到下一级。谁不能动就输。
---
结论：$a_1\oplus a_3\oplus\cdots\oplus a_{2[\frac{n-1}{2}]+1}=0\iff $先手必败。
证明类似 SG 定理。记 $O=a_1\oplus\cdots\oplus a_{2[\frac{n-1}{2}]+1}$。
1. 没有石子，显然 $O=0$，先手必败。
2. 证明 $O\neq 0$ 总能走到 $O=0$。这个证明和 Nim 几乎完全一样，略过。
3. 证明 $O=0$ 不能走到 $O=0$。分类讨论一下。
- 若是操作奇数位置的石子，即选了一个 $i\bmod 2=1$，使得 $a_i\leftarrow a_i-x$。
如果还是 $O=0$，说明 $a_i=a_i-x\Rightarrow x=0$，矛盾。
- 若是操作偶数位置的石子，即选了一个 $i\bmod 2=0$，使得 $a_{i-1}\leftarrow a_{i-1}+x$。
如果还是 $O=0$，说明 $a_i=a_i+x\Rightarrow x=0$，矛盾。
或者这么看：先手把一些石子从偶数放到奇数，后手总能把这些石子再放回偶数。
---
[P8382 [POI 2004] Gra - 洛谷](https://www.luogu.com.cn/problem/P8382)
$1\times m$ 的板子上有 $n$ 个棋子，位于 $x_1\sim x_n$。每个棋子恰好一个格子，没有棋子在 $m$。
两人轮流操作，一次可以选定一颗棋子，移动到它右侧第一个没有被占据的位置。谁先占据 $m$ 谁就获胜。
求保持先手必胜的情况下，第一步可能的走法个数。
$n\le 10^6,m\le 10^9$。
---
**正负形转化：棋子可以是空格，空格也可以是棋子**。
**把新问题转化为原有的模型！！！**
这是 staircase nim 的变种。
**记棋子距离 $m$ 的空格个数为 $cnt$，就认为它在第 $cnt$ 级台阶，变成 staircase nim**。
但胜利条件有些不一样：原本是 "不能操作输"，也就是 "谁把棋子全部移下台阶就胜"；但这里是 "谁把第一颗棋子移下台阶就胜"。
有一个到 $m$ 获胜 $\iff$ 有一个到 $m-1$ 就输 $\iff$ 全部都到 $m-2$ 就胜。
特判存在棋子在 $m-1$ 的情况。改为统计棋子与 $m-2$ 的距离。现在就变成全部移下台阶者获胜了。
然后怎么统计第一步方案数呢？要保证第一步走完先手必胜，就是要走完之后奇数位异或 $=0$。注意第一步不一定只能走奇数位。设原 $sg$ 值 $=s$。
1. 走奇数位。即 $(a_i-x)\oplus a_i=s$，也就是要求 $a_i\oplus s<a_i$ 时答案加一。
2. 走偶数位。这里又分 "新增加了一个奇数位" 和 "使旧奇数位增加了"。
1. 如果新增加一个奇数位，其实就是要增加一个 $s$。判断 $a_i\ge s$ 即可。
2. 否则 $(a_{i-1}\oplus s)-a_{i-1}$ 要在 $(0,a_i]$ 之间。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, a[N];
map<int, int> mp;
int main() {
// freopen("1.in", "r", stdin);
// freopen("1.out", "w", stdout);
cin >> m >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
if (a[n] == m - 1) {
int ans = 0;
for (int i = n; i >= 1; i--)
ans += (a[i] == (m - (n - i + 1)));
cout << ans << endl;
return 0;
}
int cnt = (m - 2) - a[n];
for (int i = n; i >= 1; i--) {
mp[cnt]++;
cnt += a[i] - a[i - 1] - 1;
}
int sg = 0;
for (auto i: mp)
if (i.first % 2 == 1)
sg ^= i.second;
if (sg == 0) {
puts("0");
return 0;
}
int ans = 0;
for (auto i: mp) {
if (i.first == 0)
continue;
if (i.first % 2 == 1) {
if ((i.second ^ sg) < i.second)
ans++;
}
else {
if (mp.find(i.first - 1) != mp.end()) {
auto p = mp.find(i.first - 1);
if (0 < (sg ^ (*p).second) - (*p).second && (sg ^ (*p).second) - (*p).second <= i.second)
ans++;
}
else {
if (i.second >= sg)
ans++;
}
}
}
cout << ans << endl;
return 0;
}
```
### 例四：Wythoff's Game
[P2252【模板】威佐夫博弈](https://www.luogu.com.cn/problem/P2252)
有两堆石子，各 $a,b$ 个。两人轮流行动，一次操作可以从一堆取走 $\ge 1$ 颗石子或在两堆取走相同数量的石子。谁走不了就输。
$a,b\le 10^9$。
---
经典博弈问题。但这个问题没啥拓展，典型的 ad-hoc 题。结论背下来。
令 $f(i,j)=0/1$ 表示两堆石子分别 $i,j$ 个是先手必败/必胜。容易发现如果把 $i,j$ 画成方格表，$f(i,j)$ 可以转移到其正上方、正左方、正左上方。到这里可以 $O(ab)$ 的 DP 做了。
考虑优化。容易发现每行每列恰有一个 $0$。观察这些 $0$ 的位置：$(r,p)$ 表示在第 $r$ 行的 $0$ 在第 $p$ 列。为了方便，我们只研究 $r\le p$ 的 $0$，因为这个方格表显然行列对称。
红点表示先手必败，蓝点相反。左上角为 $(0,0)$。
列出这些 $0$ 的坐标（只考虑 $x\le y$ 的）：$(0,0),(1,2),(3,5),(4,7),(6,10),\dots
观察到第 i 个的 y-x=i（从 0 编号），且每个坐标都是前面没出现过的。
然后大佬们搞出一个结论：
第 i 个 0 的 x 坐标为 [\frac{\sqrt 5+1}{2}\cdot i]，y 坐标为 x 坐标 +i。
所以，如果这是一个先手必败局，那么第一个数是两数差值乘黄金比下取整。
证明不会。记住结论。
例五：Yet Another Number Game
CF282D Yet Another Number Game
三堆石子各 a,b,c 个。两人轮流，可以在一堆里取任意个，也可以三堆一起取相同数量。取不了的输。
结论：a\oplus b\oplus c=0\iff先手必败。
和 Nim 游戏证明类似。
-
-
-
证毕。
例六：Fibonacci Nim
一堆石子初始 n 个。两人轮流取。先手第一次不能全部取完。之后每次取石子至少取一个，至多取刚才对手取的数量的 2 倍。
问先手什么时候有必胜策略。
神秘博弈。和 Zeckendorf 表示法有关。
Zeckendorf 定理：任意数可以被唯一地分解为若干个不相邻斐波那契数的和。
存在性证明：
-
若 n 为斐波那契数，显然。
-
否则归纳法。设 <n 的都能分解。
找到 fib_i<n<fib_{i+1}，先分解一个 fib_i 出来。若还要分解 fib_{i-1} ，有 n\ge fib_i+fib_{i-1}=fib_{i+1} 矛盾。所以不会有 fib_{i-1}。根据归纳假设，n-fib_i 是可以分解的。
唯一性证明：
归纳法。然后试证明 n 必须分解出 fib_i\le n<fib_{i+1} 的 fib_i。因为 fib 增长很快，简单放缩是可以证明的。
当然，不记证明记得结论也行。
然后是这题的解法。
结论：先手必败当且仅当 n 为斐波那契数。
证明：
咕咕。
【SG 定理应用】
例一：Cutting Game
POJ2311 Cutting Game
有一张 n\times m 方格纸，两人轮流行动。每人都可以任意横向或竖向剪。谁剪完出现 1\times 1 的获胜。
---
这是一个公平组合游戏。记 $sg(n,m)$ 为 $n\times m$ 矩形的 SG 值。
1. $sg(1,1)=0$。不能再剪了。
2. 对于 $sg(n,m)$，我们直接枚举第一步怎么剪的。
如果剪成 $n'\times m+(n-n')\times m$，这种情况下的 SG 值为 $sg(n',m)\oplus sg(n-n',m)$，因为这相当于两个新游戏的组合了。
所以有：$sg(n,m)=\mathrm{mex}\{sg(n',m)\oplus sg(n-n',m),sg(n,m')\oplus sg(n,m-m')\}$。
因为 $n,m$ 的后继 $\le n+m$ 个，所以 $sg(n,m)\le n+m$，枚举 $n'/m'$ 标记对应数，再 $O(n+m)$ 从小到大枚举看哪个没被标记。
$O(n^3)$ 递推即可。
### 例二：分裂游戏
[P3185 [HNOI2007] 分裂游戏 - 洛谷](https://www.luogu.com.cn/problem/P3185)
有 $n$ 个瓶子，编号 $1\sim n$。初始第 $i$ 个瓶子里有 $a_i$ 颗豆子。两人轮流操作。一次操作在 $1\sim n-1$ 中选择一个有豆子的瓶子 $i$，拿走一颗豆子；再从 $i+1\sim n$ 里选择两个瓶子 $j,k$（可以相同），在 $j,k$ 中各放入一颗豆子。
不能操作者败。问先手是否必胜，若必胜，输出第一步可能走法。
$n\le 21$。
---
首先这是一个公平组合游戏。把 $i$ 的瓶子看作 $3^{n-i}$ 的三进制位。每次操作后数必定减小。
因此可以考虑 SG 定理。
发现每颗豆子其实可以看作一个独立的游戏。因此考虑 $sg(i)$ 表示恰有一颗豆子在第 $i$ 个瓶子时的 SG 值。
显然 $sg(n)=0$。类似上题，有 $sg(i)=\mathrm{mex}\{sg(j)\oplus sg(k)\}$。
### 例三：取一半
一堆石子，两人轮流取。每次至多取当前石子数的一半。问谁必胜。
$n\le 10^9$。
---
显然公平组合游戏。考虑 SG 定理：
$sg(i)=\mathrm{mex}\{sg(i-1),sg(i-2),\dots,sg(i-[i/2])\}$。边界 $sg(1)=0$。
直接推显然不行。找找规律。一个容易观察到的事情是 $sg(2^i-1)=0$，其余非 $0$。
那么这题已经解完了，不过我们可以多观察一下。
```cpp
0
1 0
2 1 3 0
4 2 5 1 6 3 7 0
8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 0
```
按 $0$ 隔开，我们发现第 $i$ 行其实是 $i-1$ 行和 $2^{i-2}\sim 2^{i-1}-1$ 归并排序。进一步：
$$
sg(n)=
\begin{cases}
0&n=1\\
\frac{n}{2}& 2\mid n\\
sg(n-[\frac{n}{2}]-1)&2\nmid n\\
\end{cases}
$$
拓展到 [ARC091F Strange Nim](https://atcoder.jp/contests/arc091/tasks/arc091_d) 上，有：
$$
sg(n)=
\begin{cases}
0&n<k\\
\frac{n}{k}& k\mid n\\
sg(n-[\frac{n}{k}]-1)&k\nmid n\\
\end{cases}
$$
直接递归的复杂度：[题解 AT3939 【Strange Nim】 - 洛谷专栏](https://www.luogu.com.cn/article/coe1l229)