博弈论

博弈论

一月 07, 2024

定义

此处的博弈论只研究 ICG(公平组合游戏)和反常游戏中的 ICG,很多棋类游戏都是非公平组合游戏,因为双方只能移动自己的棋子。

一个游戏是 ICG 当且仅当:

  • 游戏有两个人参与,二者轮流做出决策,双方均知道游戏的完整信息。

  • 有明确的终止态,游戏不会无休止地进行下去。

  • 每一个局面都是先手必胜(N)或者先手必败的局面(P)。

  • 任意时刻双方可以执行的操作集合只与游戏的状态无关,与双方的身份无关。

性质

由第二条定义可得我们可以抽象成一个有向无环图,每个玩家操作一枚棋子往一条出边移动,谁移动不了了就输了。

那么对于没有出边的位置肯定是 P 局面,那么我们考虑倒推所有位置的 N/P 状态,从而得知整个游戏是先手必胜还是先手必败。

  • 如果一个点的出边中有 P 局面,那么这个点是 N 局面。

  • 如果一个点的出边中全是 N 局面,那么这个点是 P 局面。

这两条性质是双向的,并且可以很显然地由 ICG 的定义得到。

小例子,有一堆石子大小为 $n$,你和小 A 每次可以从中取出来 $[1,k]$ 区间中的石子,谁无法取了就失败。

可以发现一个大小为 $n$ 的后继节点是 $[n-k,n-1]$,然后直接打表 SG 值即可,或者构造一种必胜的方案,方案小学生都会就不写了。

相关函数与模型

Nim 游戏

给定 $n$ 堆石子,每堆石子有 $a_i$ 个石子,你和小 A 每次可以从任意一堆石子中选出来至少一个石子扔掉,无法操作的人输,你先手,问最后你和小 A 谁有必胜策略。

定理

如果 $ans=\operatorname{xor}_{i=1}^n a_i>0$ 的话先手一定有必胜策略,否则后手必胜。

证明

首先,没有后继的状态,即 $a_1=a_2=\dots=a_n=0$ 的时候一定先手必败。

然后如果 $k=\operatorname{xor}{i=1}^n a_i>0$ 的话一定存在一种操作使得 $\operatorname{xor}{i=1}^n a_i=0$,我们显然可以找到一个 $a_i \operatorname{xor} k < a_i$,然后改成 $a_i \operatorname{xor} k$ 就可以了。

最后需要证明如果 $k=\operatorname{xor}{i=1}^n a_i=0$ 的话不可能存在任何一种操作使得 $k=\operatorname{xor}{i=1}^n a_i=0$,显然成立。

所以结论成立。

SG 函数

定义集合的 SG 运算为 $\operatorname{mex}{S}$ 表示 $S$ 中最小的没有出现过的自然数,那么 $SG(x) = \operatorname{mex}{y_1,y_2,\dots,y_k}$,其中 $y$ 是 $x$ 的后继节点。

如果 $SG(x)>0$,那么代表先手的棋子如果在 $x$ 这个节点先手必胜,否则后手必胜。这个的证明也很显然,参考前面的 ICG 游戏的性质即可。

那么如果我们是多个游戏拼在一起的怎么办呢?

例如我们在有向图游戏上有多个棋子,然后每次可以移动一颗,最后不能移动者失败。

我们发现 $x$ 可以移动到 $SG(y) < SG(x)$ 或者 $SG(y)>SG(x)$ 的节点,如果我们移动到了 $y$ 满足 $SG(y)>SG(x)$,那么后手如果觉察到不优秀,肯定会从 $y$ 移动到 $z$ 满足 $SG(x)=SG(z)$,这样的操作是不优秀的。

那么我们只剩下移动到 SG 值比它小的节点,那么这就是一个 Nim 博弈,我们相当于每次可以拿走若干个大于等于 $1$ 小于等于全部的石头,于是直接把所有起点的 SG 值异或起来,然后按照 Nim 博弈的判断标准来判断就行了。

注意:每个局面都可以转化为含有 $SG(x)$ 个石子的 Nim 游戏,如果有多个局面,就相当于 Nim 游戏有多个石堆。

解题方法

  • 如果我们构造了一个模型发现一个石子移动了会影响另外的石堆,那么我们可以对每个石子单独考虑得出结果。

  • SG 函数不一定是直接取若干个后继节点的 $\operatorname{mex}$,而是有可能每个后继节点又衍生出两个游戏,那么我们要把这两个游戏的 SG 值异或起来再取 $\operatorname{mex}$。

  • 有些 SG 函数十分刁钻,需要打表,并且可能会出现循环节,并且只有几个特殊情况。

例题

有 $n$ 堆石子,每堆石子有 $a_i$ 个石头,每次可以选择 $i<j \le k$ 且 $a_i>0$,从第 $i$ 堆石头中选择一个石头扔掉,然后给第 $j$ 和 $k$ 堆石头中添加一个石头,最后无法操作的人失败,问先手是否拥有必胜策略。

首先,因为一次操作会影响石堆互相的值,所以考虑对每个石头分开考虑,如果当前石头距离最后一堆石头 $k$ 堆,那么我们可以扔掉它,然后加入两个距离最后一堆石头 $<k$ 的石头,就相当于可以让一个值为 $k$ 的数分裂为两个 $1 \le k_1,k_2<k$ 的数,然后分开考虑,最后异或起来就可以了。

因为 $n$ 只有 $20$,所以 $k$ 也只有 $20$,记忆化搜索打表即可。

题目如果要求输出第一次操作的方案,我们直接暴力 $O(n^3)$ 枚举第一次操作的 $i,j,k$,拿走之后判断是否先手必败即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t,n,a[25],b[25],i,j,k,l,ans,ans1,ans2,ans3,sg[22]={0,0,1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38};
inline ll solve(ll a[25]){
ll ans = 0;
for(ll i=1;i<=n;i++){
if(a[i]%2==0) continue;
ans^=sg[n-i+1];
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin>>t;
while(t--){
cin>>n;
for(i=1;i<=n;i++) cin>>a[i];
ans=solve(a);
if(ans==0){
cout<<"-1 -1 -1\n0\n";
continue;
}
ans=0,ans1=ans2=ans3=LLONG_MAX;
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
for(k=j;k<=n;k++){
for(l=1;l<=n;l++) b[l]=a[l];
b[i]--,b[j]++,b[k]++;
if(solve(b)==0){
ans++;
if(i<ans1) ans1=i,ans2=j,ans3=k;
else if(i==ans1){
if(j<ans2) ans2=j,ans3=k;
else if(j==ans2){
if(k<ans3) ans3=k;
}
}
}
}
}
}
cout<<ans1-1<<" "<<ans2-1<<" "<<ans3-1<<endl<<ans<<endl;
}
return 0;
}

附:有些题也不需要转化为 Nim 游戏,直接通过题目的性质转化为有向图游戏,然后通过 SG 函数计算即可。(需要去除一些无用状态或者记忆化一下)

取石子游戏

一维翻硬币问题有一个结论:

局面的 SG 值等于局面中所有反面朝上的硬币单独存在时的 SG 值的异或和。

这个结论同样适用于二维的翻硬币问题。

删边游戏

有一幅图,每次操作可以删去图上的一条边,操作结束之后把所有没有与 $root$ 相连的边和点删去,最后无法操作者失败。

首先对于叶子结点,因为只剩一个节点,所以 SG 值为 $0$。

然后对于某些其它节点 $i$,它的 SG 值经过证明可得 $SG_i = \operatorname{xor}_{v \in son_i}{SG_v+1}$.

最后整张图的 SG 值就是 $SG_{root}$。

首先需要找出所有的环(边双连通分量),如果一个环内的边数是偶数,那么直接将这个环缩成一个点即可。

否则需要将环缩成一个点还要再新建一个点挂一条边。

然后如果根属于一个环,那新的根就是环缩点的那个点。

容易发现这样操作完成之后是一棵树,于是直接用树删边定理即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define N 300005
using namespace std;
vector<pair<int,int> > op[N];
vector<int> op2[N],op3[N],ans[N];
int T,n,m,x[N],y[N],i,j,tot,scc,dfn[N],low[N],cut[N],vis[N],edge[N],sg[N],root,id[N],col[N];
void tarjan(int x,int r){
dfn[x] = low[x] = ++tot;
for(int i=0;i<op[x].size();i++){
if(!dfn[op[x][i].first]){
tarjan(op[x][i].first,op[x][i].second);
low[x] = min(low[x],low[op[x][i].first]);
if(low[op[x][i].first]>dfn[x]) cut[op[x][i].second] = 1;
}
else if(r!=op[x][i].second) low[x] = min(low[x],dfn[op[x][i].first]);
}
}
void dfs(int x){
vis[x] = 1,ans[scc].push_back(x),col[x] = scc;
for(int i=0;i<op2[x].size();i++){
edge[scc]++;
if(!vis[op2[x][i]]) dfs(op2[x][i]);
}
}
void solve(int x,int fa){
for(int i=0;i<op3[x].size();i++){
if(op3[x][i]==fa) continue;
solve(op3[x][i],x);
sg[x] ^= (sg[op3[x][i]]+1);
}
}
int main(){
ios::sync_with_stdio(false);
cin>>T;
while(T--){
cin>>n>>m;
for(i=1;i<=m;i++){
cin>>x[i]>>y[i];
op[x[i]].push_back(make_pair(y[i],i)),op[y[i]].push_back(make_pair(x[i],i));
}
for(i=1;i<=n;i++) if(!dfn[i]) tarjan(i,-1);
for(i=1;i<=m;i++){
if(!cut[i]){
op2[x[i]].push_back(y[i]);
op2[y[i]].push_back(x[i]);
}
}
for(i=1;i<=n;i++) if(!vis[i]) scc++,dfs(i),edge[scc]/=2;
for(i=1;i<=scc;i++){
if(ans[i].size()==1&&edge[i]==0){
id[i]=ans[i][0];
continue;
}
if(edge[i]%2==1) id[i]=++n,++n,op3[id[i]].push_back(n),op3[n].push_back(id[i]);
else id[i]=++n;
}
for(i=1;i<=m;i++){
if(cut[i]){
op3[id[col[x[i]]]].push_back(id[col[y[i]]]);
op3[id[col[y[i]]]].push_back(id[col[x[i]]]);
}
}
root = id[col[1]];
solve(root,-1);
if(sg[root]) cout<<"Alice\n";
else cout<<"Bob\n";
for(i=0;i<=2*n;i++) op[i].clear(),op2[i].clear(),op3[i].clear(),ans[i].clear(),col[i]=id[i]=edge[i]=vis[i]=sg[i]=low[i]=dfn[i]=0;
tot=0,scc=0;
for(i=0;i<=m;i++) x[i]=y[i]=cut[i]=0;
}
return 0;
}

反常游戏

给定 $n$ 堆石子,每堆石子有 $a_i$ 个石子,你和小 A 每次可以从任意一堆石子中选出来至少一个石子扔掉,取走最后一个石子的人输,你先手,问最后你和小 A 谁有必胜策略。

设 $k=\operatorname{xor}_{i=1}^n a_i$。

如果 $a_i$ 有的为 $0$,删去不影响答案。

如果 $a_i$ 全部为 $1$,如果 $n$ 为奇数先手必败,$n$ 为偶数先手必胜。

否则如果 $k>0$ 先手必胜,否则先手必败。

证明

第一条结论显然。

第二条结论每次只能拿走一堆石子,所以显然。

第三条结论:

  • 如果只有一个 $a_i>1$,那么先手必胜,因为先手可以让全部 $a_i$ 为 $1$,并且控制堆数的奇偶性。

  • 有至少两个 $a_i>1$,那么如果 $k>0$ 由 Nim 游戏可得先手可以把 $k$ 转化成 $0$。

  • 若 $k=0$,先手可以转化为至少两个 $a_i>1$ 并且 $k>0$ 的情况,那么这么交叉进行最后 $a_i$ 的堆数会逐渐减少,回归最开始的情况。

  • 并且这种情况可以让对方必胜,也可以转化为至少两个 $a_i>1$ 并且 $k>0$ 的局面,并且至少两个 $a_i>1$ 并且 $k>0$ 的局面只能转化为 $k=0$ 的局面,所以这种情况先手必胜。

得证。

Nim-k 游戏

给定 $n$ 堆石子,每堆有 $a_i$ 个石头,每次可以选择 $1 \sim k$ 堆,从每堆中拿走一部分石子,拿走的石子总数必须大于等于 $1$,谁无法操作就失败,问什么情况下先手必胜。

结论:如果存在一位 $j$ 使得 $a_i$ 二进制下第 $j$ 位为 $1$ 的个数 $\ \bmod \ (k+1) \ne 0$,那么先手必胜,否则先手必败。

容易发现,Nim 游戏就是在 $k=1$ 的时候的特例。

证明

首先如果不存在任何一位 $j$ 满足上述条件,一次操作之后不可能也不存在一位 $j$ 满足上述条件。

如果存在,那就把所有的 $j$ 拿出来,然后因为 $a \bmod (k+1) \le k$,所以一定可以加入到 $k$ 个集合中,于是我们通过 Nim 游戏的证明就可以证出可以通过一次操作使得不存在任何一位 $j$ 满足上述条件。

当所有元素都为 $0$ 时,不存在任何一位 $j$ 满足上述条件,先手必败。

于是一来一回归纳得证。

其它

如果是到达一个状态先手必胜,那么我们必须转化为到达某个状态先手必败,然后再用 Nim/SG 的相关知识解决。

例题:

有 $n$ 个棋子,第 $i$ 个棋子在 $(x_i,y_i)$,每次可以移动一颗棋子到 $(x_i-k,y_i),(x_i,y_i-k),(x_i-k,y_i-k)$ 之一($1 \le k$),$x \ge 0,y \ge 0$,AB互相博弈,A先手,如果某人移动了某颗棋子到 $(0,0)$,此人胜利,问先手是否必胜。

因为是移动到 $(0,0)$ 就胜利,而且有多颗棋子,我们可以考虑什么情况下面某人必败,来转化。

首先,一个人不会傻到移动棋子到 $(0,k),(k,0),(k,k)$,除非没有地方移动了。

我们就会发现如果有一个棋子位于上面三个位置,先手必胜,特判掉即可。

如果不,那么当且仅当棋子在 $(1,2)$ 或者 $(2,1)$ 的时候一定会移动到上面三个位置之一,这就是终止态,先手必败。

然后按照 SG 函数合并即可,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define ll long long
#define N 305
using namespace std;
ll T,n,x,y,ans,i,j,sg[N][N],temp;
ll dfs(ll x,ll y){
if(x==0||y==0||(x==y)) return 10000;
if(sg[x][y]!=-1) return sg[x][y];
bool vis[1005];
memset(vis,0,sizeof(vis));
for(ll i=1;i<=x;i++){
ll temp = dfs(x-i,y);
if(temp<=1000) vis[temp]=1;
}
for(ll i=1;i<=y;i++){
ll temp = dfs(x,y-i);
if(temp<=1000) vis[temp]=1;
}
for(ll i=1;i<=min(x,y);i++){
ll temp = dfs(x-i,y-i);
if(temp<=1000) vis[temp]=1;
}
for(ll i=0;;i++) if(!vis[i]) return sg[x][y]=i;
}
int main(){
ios::sync_with_stdio(false);
memset(sg,-1,sizeof(sg));
for(i=0;i<100;i++) for(j=0;j<100;j++) dfs(i,j);
cin>>T;
while(T--){
ans=0,temp=0;
cin>>n;
while(n--){
cin>>x>>y;
if(x==0||y==0||(x==y)) temp=1;
ans^=sg[x][y];
}
if(ans||temp) cout<<"^o^\n";
else cout<<"T_T\n";
}
return 0;
}