浅谈博弈论
Atserckcn
·
·
算法·理论
浅谈博弈论
巴巴博弈。
巴巴博弈？
巴巴博弈！
博弈
多名玩家参与的竞争游戏。
特征
- 每次只允许一个人行动，通常轮流行动。
- 每个玩家的目标是获胜，且每个人都是上帝视角，可以找到最优方案。
- 获胜条件通常为多得分或达到指定局面。
- 大部分为两个玩家 A、B 参与。结果只有 A 胜，B 胜和平局三种。
公平组合游戏
若一个游戏满足：
- 两名玩家交替行动。
- 玩家决策相同，只与当前局面有关。
- 不能行动的玩家负。
则这个游戏称为公平组合游戏。例如下文的 Nim 博弈。
状态设计
- 包含当前游戏的局面和即将行动的玩家。
- 即将行动的玩家称为先手，对方称为后手。
- 结果分为先手必胜（简称胜）、先手必败（简称败）和平。
注意操作完后先手不一定会改变。下文假定轮换行动玩家。
有向图游戏
在一个有向图里，两名玩家从起点依次移动棋子，首先无法移动的玩家负。
所以我们可以把任意的公平组合游戏的每一个状态看作有向图的点，决策看作边，建立有向图。
注意不一定是 DAG，可能有环。
这种图被称为博弈图。
状态转移与决策
设当前先手为 A，对手为 B。
此时从当前状态转移到的结果有三种情况：
- 先手必胜。此时先手指 B，故结果为对于 A 是必败的。
- 先手必败。此时后手 A 必胜。
- 平。
然后由于每个玩家开了挂，所以一定会选择最利于自己的那个状态去转移。
就是有必胜状态就不选平和必败，有平就不选必败。
所以我们有：
- 可以变化到任意先手必败的状态，当前状态为先手必胜。
- 所有变化都为先手必胜，当前状态为先手必败。
- 只能转移到平和先手必胜，当前状态为平。
所以说博弈论的求解是先 DFS 把可行状态求出来，后根据搜出来的结果调整。
即搜索方向与转移方向是反着的。
所以就十分自然地想到用记忆化搜索。
小 trick：越靠近终止状态的状态一定是越先被记搜搜到的。因为搜索反向。
若图中存在环，可以利用拓扑排序，将能计算的点的状态先计算出来，没被计算过的点的状态就是平。因为它们既不能转移到先手必胜，也不能转移到先手必败。符合平局的定义。
板子是设 f_u 表示在局面 u 的情况下，先手的最优结果。有些题目如果先后手人不同操作不同还需要再开一维存先手。
分类
- 公平博弈：每名玩家可进行的操作相同。
- 零和博弈：玩家们收益总和一定。
游戏可能会无限进行。因为如果存在环，且其余状态为必败态，则先手为了不败会选择在环内周旋。
Nim 博弈
情景类似于：有 n 堆石子，第 i 堆石子有 a_i 个，两名玩家轮流取石子，每次可以选择任意一堆取不多于该堆石子个数个石子，不能不取，无法操作者负。
同样地，Nim 博弈可以根据所有堆的石子个数确定状态。
这样，一共有 \prod_{i=1}^n a_i 种状态，要 O(\prod_{i=1}^n a_i) 地求出所有状态的胜负是绝对不允许的。
那么如何快速判断呢？
定理：若一个局面，满足 \bigoplus_{i=1}^n a_i\neq 0，则先手必胜，反之先手必败。
证明：
结论一：若 \forall a_i=0，则游戏结束，先手必败。
结论二：若 \bigoplus _{i=1}^n a_i=k\neq 0，设 k 的二进制下为 1 的最高位为第 p 位，则必然存在某个 a_j 的二进制下第 p 位为 1。
由于 a_j 和 k 的 1 的最高位相同，异或完一定等于 0，所以 a_j\bigoplus k<a_j。
那么我们可以从 a_j 中取走 a_j-a_j\oplus k 个石子，使得 a_j\leftarrow a_j\oplus k，则原式变为：
\bigoplus _{i=1}^{j-1}a_i \ \oplus a_j \oplus k \ \bigoplus_{i=j+1}^n a_j=0
所以一定存在一种取法，使得剩下的石子异或和为 0。
结论三：若 \bigoplus _{i=1}^n a_i=0，则不管取多少个，必然会使剩下的异或和不等于 0。
因为所有石子二进制下每一位为 1 的数字个数必定是偶数，而设取了 m 个石子，则 m 二进制下有至少一位必定是 1，使得这一位所有的 1 的个数变成偶数，异或完就不为零了。
结论四：石子一定越取越少，最后必然会达到全为 0 的局面。
所以如果局面的异或和不为 0，先手一定可以使其变为 0，一步一步变成全为 0 的局面，所以先手必胜。
（发现者是怎么想到用异或判定的啊……）
SG 函数
首先定义一下 \operatorname{mex} 运算。
$$
\operatorname{mex}(S)=\min_{i=0,i\notin S} {i}
$$
上文提到，任意的公平组合游戏都可以转化为有向图游戏。
设在博弈图中，从点 $x$ 出发，可到达的点的集合为 $S=\{y_1,y_2,\cdots ,y_k\}$，则定义 $\operatorname{SG}(x)=\operatorname{mex}(\operatorname{SG}_{i\in S}(i))$，即所有可达点的 $\operatorname{SG}$ 值的 $\operatorname{mex}$ 值。
特别地，如果 $S=\empty$，则 $\operatorname{SG}(S)=0$。
对于一个有向图 $G$ 的 $\operatorname{SG}$ 值定义为起点 $s$ 的 $\operatorname{SG}$ 值。即 $\operatorname{SG}(G)=\operatorname{SG}(s)$。
### 有向图游戏的和
设 $G_1,G_2,\cdots,G_m$ 为 $m$ 个有向图游戏，它们的 $\operatorname{SG}$ 值分别为 $\operatorname{SG}(G_1),\operatorname{SG}(G_2),\cdots,\operatorname{SG}(G_m)$。
定义有向图游戏 $G$，其游戏规则为任选一个有向图游戏进行操作一次，则称 $G=\sum_{i=1}^m G_i$，定义 $\operatorname{SG}(G)=\bigoplus _{i=1}^m \operatorname{SG}(G_i)$。
### SG 定理
定理：若 $\operatorname{SG}(x)=0$，则该局面为必败局面，否则为必胜局面。
证明：
设可达点集合为 $S=\{y_1,\cdots ,y_k\}$。
+ 若 $S=\empty$，则 $\operatorname{SG}(x)=0$，无法移动，先手必败，成立。
+ 若 $\operatorname{SG}(x)\neq 0$，则必然存在一个 $y_j\in S$，满足 $\operatorname{SG}(y_j)=0$，先手就可以将状态转移到 $y_j$。
+ 若 $\operatorname{SG}(x)=0$，则必然 $\forall y_j\in S,\operatorname{SG}(y_j)>0$，即先手无论如何转移，都无法转移到一个 $\operatorname{SG}(x')=0$ 的点 $x'$。必定会转移到一个 $\operatorname{SG}$ 值不等于零的点。
+ 在没有环的情况下，状态是不可以无限扩展的，所以必定会遇到无法扩展的终止状态 $t$，必定有 $\operatorname{SG}(t)=0$，满足先手必败态。
证毕。类似于 Nim 博弈的证明。
对于有向图游戏的和的 $\operatorname{SG}$ 值，可以把每个**子有向图游戏**看成一堆石子，每次操作就是取石子，无法操作就是取完了。就可以更好地理解对于有向图游戏的和的 $\operatorname{SG}$ 的定义了。
实在不行感性理解一下。
所以，SG 定理的伟大之处在于，它让我们在知道了 Nim 博弈的判断条件后，利用 $\operatorname{SG}$ 值，将 Nim 博弈推广到了普通的公平博弈，功德无量。
### 博弈论解题步骤
+ 像 DP 一样，抽象出状态。
+ 设定初始状态、结束状态。
+ 状态转移。
计算 $\operatorname{SG}$ 值时一定要注意：
+ 状态**转移**时用 $\operatorname{mex}$。
+ 多个子任务同时进行时用 $\oplus$。
### 例题
#### CF859C Pie Rules
[link.](https://codeforces.com/problemset/problem/859/C)
因为是按照**从左到右**的顺序取的，所以考虑设 $f_u$ 表示取完 $[u,n]$ 后**先手**的最优得分。
还要统计后缀和，设 $s_i=\sum_{j=i}^n a_j$。
那么转移分为两种，一种是把分给自己，让出先手，贡献是 $a_u+s_{u+1}-f_{u+1}$。
否则就是给对方，留下先手，贡献是 $f_{u+1}$。
然后搞个记搜就做完了。
~~复习博弈论时竟然被我秒了。~~
Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
const int N=55;
int n,a[N],f[N],sum[N];
int dfs(int u)
{
if(f[u]!=-1)return f[u];
if(u>n)return 0;
f[u]=0;
if(u==n){f[u]=a[n];return f[u];}
//use
int ans=a[u]+sum[u+1]-dfs(u+1);
ans=max(ans,dfs(u+1));
f[u]=ans;
return f[u];
}
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
memset(f,-1,sizeof(f));
for(int i=n;i>=1;--i)sum[i]=sum[i+1]+a[i];
cout<<sum[1]-dfs(1)<<' '<<dfs(1)<<'\n';
return 0;
}
```
#### AT_dp_k Stones
[link.](https://atcoder.jp/contests/dp/tasks/dp_k)
这里设 $f_u$ 表示还剩下 $u$ 颗石头时先手的最优结果。
由于不存在平，所以只考虑胜负。
每次转移就是枚举 $a_i$，用 $f_{u-a_i}$ 更新状态。
小技巧：轮换状态可以用 $\oplus 1$ 操作来 $0\rightarrow 1$，$1\rightarrow 0$。然后取最优状态可以用按位或运算。
~~哦哦哦我竟然也秒切出来了。~~
Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
const int N=105,K=1e5+5;
int n,k,a[N],f[K];
int dfs(int u)
{
if(f[u]!=-1)return f[u];
if(u==0)return 0;
int ans=0;
for(int i=1;i<=n;++i)
{
if(u>=a[i])
ans|=(dfs(u-a[i])^1);
}
f[u]=ans;
return f[u];
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>k;
for(int i=1;i<=n;++i)cin>>a[i];
memset(f,-1,sizeof(f));
if(dfs(k))cout<<"First\n";
else cout<<"Second\n";
return 0;
}
```
#### P10501 Cutting Game
[link.](https://www.luogu.com.cn/problem/P10501)
蓝书上的例题。
设 $n$ 行 $m$ 列为当前的状态。
首先肯定没人想剪出 $1\times k$ 的矩阵，因为这样下一步对方就可以剪出 $1\times 1$ 的矩阵，这是必败状态。
然后我们考虑分割。按照横着切，可以分为两个子矩阵，一个大小为 $i\times m$，一个大小为 $(n-i)\times m$。
同理，按照纵向切，可以分为 $n\times j$ 和 $n\times (m-j)$ 的两个子矩阵。
然后我们就可以枚举，从“完成一个矩阵”这一状态转移到“完成两个子矩阵”。
放图：
所以我们要求 $\operatorname{SG}(\{n,m\})$，只要求出右边那坨的 $\operatorname{SG}$ 值即可。
而右边那个的 $\operatorname{SG}$ 值，则等于 $\operatorname{SG}({n-i,m})\oplus \operatorname{SG}(i,m)$。
由于不止一种剪法，所以要对多个新状态的 $\operatorname{SG}$ 值取 $\operatorname{mex}$。
所以要注意什么时候用异或，什么时候用 $\operatorname{mex}$。
Code：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ljl;
const int N=205;
int n,m,sg[N][N];
int getsg(int a,int b)
{
if(sg[a][b]!=-1)return sg[a][b];
bool vis[N*N];memset(vis,0,sizeof(vis));
for(int i=2;i<a-1;++i)
vis[getsg(i,b)^getsg(a-i,b)]=1;
for(int i=2;i<b-1;++i)
vis[getsg(a,i)^getsg(a,b-i)]=1;
for(int i=0;;++i)
if(!vis[i])
{
sg[a][b]=i;
return i;
}
}
void Main()
{
cout<<(getsg(n,m)==0?"LOSE\n":"WIN\n");
return;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
memset(sg,-1,sizeof(sg));
for(int i=1;i<=200;++i)
sg[1][i]=sg[i][1]=0;
while(cin>>n>>m)Main();
return 0;
}
```
### 参考资料
+ 李煜东小蓝书《算法竞赛进阶指南》第 0x3A 节《博弈论之 SG 函数》
+ [OI wiki 博弈论](https://oi-wiki.org/math/game-theory/impartial-game/)
+ [浅谈SG函数和博弈论](https://www.luogu.com.cn/article/shyocttb)