博弈论
ZHONGZIJIE0608
·
·
个人记录
简介
博弈论 \text{(Game Theory)}，是现代数学的一个分支，也是运筹学的一个重要组成部分，是经济学的一个分支，主要研究具有竞争或对抗性质的对象，在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。
博弈论主要研究公式化了的激励结构间的相互作用，是研究具有斗争或竞争性质现象的数学理论和方法。博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。生物学家使用博弈理论来理解和预测进化论的某些结果。
通俗地讲，博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家的策略。
游戏类型
开放性世界冒险游戏
公平组合游戏
公平组合游戏 \text{(Impartial Game)} 的定义如下：
-
游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；
-
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
-
游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。
非公平组合游戏
非公平组合游戏 \text{(Partizan Game)} （直译为游击队游戏？） 与公平组合游戏的区别在于在非公平组合游戏中，游戏者在某一确定状态可以做出的决策集合与游戏者有关。例如斗地主时你不能使用对方的牌。
非公平组合游戏可能出现平局。
如果象棋允许双方共享棋子？
反常游戏
反常游戏 \text{(Misère Game)} （“痛苦游戏”？）就是按照传统游戏规则进行游戏，但是胜者为第一个无法行动的玩家。
以 \text{Nim} 游戏为例，传统版本的 \text{Nim} 游戏是以玩家取走最后一颗石子作为胜利条件，但是反常 \text{Nim} 游戏是以玩家无法行动作为胜利条件。
你说得对，但是《取石子》是由【数据删除】独立开发的一款全新公平组合冒险游戏。
公平组合游戏
玩牛魔的 \text{Nim} 游戏，取数游戏，31 点，都是公平组合游戏。
定义
游戏有 2 人参与，分为先手和后手，且双方都作出对自己最有利的决策。
当有一人无法作出决策时游戏结束，无法作出决策的人输。
无论二者如何做决策，游戏总是能够在有限步内结束。
游戏同一状态不可能多次抵达，且游戏不会有平局出现。
任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关。
博弈图
考虑到每一种状态最多出现 1 次，公平组合游戏的决策可以被转化为博弈图，是一张 \text{DAG}。
一种状态是一个点，一种决策是一条边。
终止状态的出度为 0。
必胜态与必败态
先手必胜（必败）的状态。
如果后继状态存在必败状态则该状态必胜。
理由： 如果后继状态存在必败状态则当前操作者可以转到必败状态，此时对手必败。
如果无后继状态或者后继状态全是必胜态则当前状态为必败态。
理由： 先手要么无法决策，要么后手必胜。
博弈图是个有向无环图，我们可以用 O(N+M) 的时间复杂度遍历整张图得出每一种状态是必胜态还是必败态。
Nim 游戏
通过绘画博弈图，我们可以在 $O(\prod_{i=1}^n a_i)$ 的时间内求解该局面是否先手必胜。
但是这样的时间直接爆炸。
定义 $\text{Nim}$ 和为 $\bigoplus_{i=1}^n a_i$。
当且仅当 $\text{Nim}$ 和为 $0$ 时当前状态为必败态，否则为必胜态。
## Nim 和的证明
1. 最终异或和为 $0$。
2. 对于任意一个异或和不为 $0$ 的状态（必胜态），存在一种方案使得决策后异或和为 $0$。
设 $\bigoplus_{i=1}^n a_i=S$，一定存在 $a_i$ 在 $S$ 的最高位是 $1$。只要改变这一位使得 $S$ 上的这一位变成 $0$，其余的 $1$ 也相应操作变成 $0$ 即可。
3. 对于任意一个异或和为 $0$ 的状态，不存在后继的异或和为 $0$ 的状态。
## 有向图游戏
有向图游戏是一个经典的博弈游戏——实际上，大部分的公平组合游戏都可以转换为有向图游戏。
在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。
定义 $\text{mex}$ 函数为不属于集合 $S$ 中的最小非负整数，也就是：
$$\operatorname{mex}(S)=\min\{x\}(x \notin S,x \in \N)$$
您说得对，但是 $\text{mex}$ 怎么计算？总不能打暴力吧。
接下来祭出 [**P4137 Rmq problem/mex**](https://www.luogu.com.cn/problem/solution/P4137)。
用回滚莫队（离线）或者主席树（可在线）维护。
这里用主席树。
不难发现 $\text{mex}$ 不是 $0$ 就是 $a_i+1$，所以我们在传数据时要把这些数一起传进去。主席树维护每个数**最后一次出现的位置**（叶子赋值，$\text{pushup}$ 时用最小值）。最后在主席树 $r$ 号版本上找最后一个位置小于 $l$ 的权值。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
struct HJT{int lc,rc,sm;}t[N*50];
int rt[N*50],a[N*30],b[N*30],n,m,q,tot;
void pushup(int x){t[x].sm=min(t[t[x].lc].sm,t[t[x].rc].sm);}
int build(int L,int R){
int x=++tot;t[x].sm=1e17;
if(L==R)return x;int mid=(L+R)>>1;
t[x].lc=build(L,mid);t[x].rc=build(mid+1,R);
pushup(x);return x;
}
int upd(int ls,int pos,int val,int L,int R){
int x=++tot;t[x]=t[ls];
if(L==R){t[x].sm=val;return x;}
int mid=(L+R)>>1;
if(pos<=mid)t[x].lc=upd(t[x].lc,pos,val,L,mid);
else t[x].rc=upd(t[x].rc,pos,val,mid+1,R);
pushup(x);return x;
}
int qry(int x,int L,int R,int k){
if(!x||L==R)return b[L];
int mid=(L+R)>>1;
if(t[t[x].lc].sm<k)return qry(t[x].lc,L,mid,k);
else return qry(t[x].rc,mid+1,R,k);
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
cin>>n>>q;m=0;b[++m]=0;
for(int i=1;i<=n;++i)cin>>a[i],b[++m]=a[i],b[++m]=a[i]+1;
sort(b+1,b+1+m);m=unique(b+1,b+1+m)-b-1;
for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+1+m,a[i])-b,rt[i]=upd(rt[i-1],a[i],i,1,m);
while(q--){
int l,r;cin>>l>>r;
int pos=qry(rt[r],1,m,l);
cout<<pos<<'\n';
}
return 0;
}
```
## SG 函数
$\text{SG}$ 是 Sprague–Grundy 的缩写。
对于状态 $x$ 及其所有 $k$ 个后继状态 $y_1,y_2,\cdots,y_k$，定义 $\text{SG}$ 函数：
$$\text{SG}(x)=\text{mex}(\text{SG}(y_1),\text{SG}(y_2),\cdots,\text{SG}(y_k))$$
## SG 定理 (Sprague–Grundy Theorem)
对于分别由 $n$ 个起始状态 $s_1,s_2,\cdots,s_n$ 开始的 $n$ 个有向图游戏的组合游戏，**当且仅当 $\bigoplus_{i=1}^{n} \text{SG}(s_i) \neq 0$ 时，这个游戏先手必胜。同时这是这个组合游戏的状态 $x$ 的 $\text{SG}$ 值。**
## SG 定理的证明
[**Here**](https://oi.wiki/math/game-theory/impartial-game/#sg-%E5%AE%9A%E7%90%86%E7%9A%84%E8%AF%81%E6%98%8E)
## SG 定理的应用
SG 定理适用于 **任何公平的两人游戏**, 它常被用于决定游戏的输赢结果。
计算给定状态的 Grundy 值的步骤一般包括：
- 获取从此状态所有可能的转换；
- 每个转换都可以导致 **一系列独立的博弈**（退化情况下只有一个）。计算每个独立博弈的 Grundy 值并对它们进行 **异或求和**。
- 在为每个转换计算了 Grundy 值之后，状态的值是这些数字的 $\operatorname{mex}$。
如果该值为零，则当前状态为输，否则为赢。
## 将 $\text{Nim}$ 游戏转换为有向图游戏
把一个有 $x$ 个物品的堆视为点 $x$，当且仅当 $y<x$ 时节点 $x$ 可到达点 $y$。
然后 $n$ 个堆的 $\text{Nim}$ 游戏可以被视为 $n$ 个有向图游戏。
不难得到 $\operatorname{SG}(x)=x$，带入 SG 定理就有 $\text{Nim}$ 和的结论了。
每一个简单 SG-组合游戏都可以**完全等效**成一堆数目为 $K$ 的石子。
还有更多。
## 最简单的巴什博弈
两个人轮流取 $N$ 个石子，每次可以取 $1 \sim m$ 个，最先取完石子的一方获胜，问你先手有无必胜状态。
显然，设 $n \bmod (m+1)=p$，若 $p \ne 0$，第一轮先手取 $p$。然后无论后手取多少个石子（设为 $k$ 个），先手取 $m+1-k$ 个总能获胜。但是当 $p=0$ 时，后手就可以按照原本先手取了余数后的操作获胜。
于是判断 $n \bmod (m+1)$ 是否等于 $0$ 即可。
## SG 函数怎么用
首先定义 $\text{mex(minimal excludant)}$ 运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如 $\text{mex}\{0,1,2,4\}=3,\text{mex}\{2,3,5\}=0,\text{mex}\{\}=0$。
这一步应该是非常简单的，就是定义了新的运算为 $\text{mex}$。
对于任意状态 $x$ ， 定义 $SG(x) = \text{mex}(F)$，其中 $F$ 是 $x$ 后继状态的 SG 函数值的集合（就是上述 $\text{mex}$ 中的数值）。最后返回值（也就是 $SG(X)$）为 $0$ 为必败点，不为零必胜点。
进一步解释一下 $F$，就是题意中给出的可以移动的次数。举个例子来说，一堆石子，每次只能拿 $1,3,5,7$ 个，那么 $S$ 数组就是 $1,3,5,7$。
假如说是在一个游戏中有多个石子堆该怎么办了。我们只需要把对每个石子堆进行 sg 函数的调用，将得到的所有的值进行异或。得出来的结果为 $0$ 则该情形为必败态。否则为必胜态。
这样就可以打表啦。