简单博弈

巴什博弈

问题：\(2\) 人玩游戏，共有 \(n\) 个石子，每人每次可以取 \([1,k]\) 个石子，最后一次取石子的人获胜，问先手何时必胜？

结论：巴什博弈先手必败，当且仅当 \((k+1)\mid n\)，否则先手必胜。

证明：分类讨论。

1. \(n\le k\)：这时候先手可以一次性取完；
2. \(n=k+1\)：这时候先手无论取 \(x\in[1,k]\) 中的多少个石子，后手都可以一次取完剩余的 \(n-x\) 个石子；
3. \(n=\lambda(k+1)\)：这时候对于每个 \(k+1\) 的石子，情况与 2 同，结果就是后手胜；
4. \(n=\lambda(k+1)+\mu,\mu\in[1,k]\)：这时候，先手可以先把 \(\mu\) 个石子取走，转化为第 3 种情况，此时这里的“先手”变成了情况 3 中的“后手”，故其必胜。

Nim 博弈

定义：给定 \(n\) 堆物品，第 \(i\) 堆物品有 \(A_i\) 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人均采取最优策略，问先手能否必胜。我们把这种游戏称为 Nim 博弈。

基本概念：

局面：我们把 Nim 博弈游戏过程中面临的状态称为局面。

先手与后手：整局游戏第一个行动的称为先手，第二个行动的称为后手。

必胜局面与必败局面：若在某一局面下存在某种行动，使得行动后对手面临必败局面，则称这样的局面为必胜局面；若在某一局面下无论采取何种行动，都会输掉游戏，则称这样的局面为必败局面。

Nim 博弈不存在平局，只有先手必胜和先手必败两种情况。

Nim 定理：

内容：记 \(\displaystyle A=\bigoplus^{n}_{i=1}A_i\)，Nim 博弈先手必胜，当且仅当 \(A\neq 0\)。

证明：数学归纳法。

所有物品被取光是一个必败局面，此时显然有 \(A=0\)。

对于任意一个局面，如果 \(A\neq 0\)，设 \(A\) 的二进制表示下最高位的 \(1\) 在第 \(k\) 位，那么至少存在一堆物品 \(A_i\)，它的第 \(k\) 位是 \(1\)。显然 \(A_i\oplus A<A_i\)，我们就从 \(A_i\) 堆中取走若干物品，使其变为 \(A_i\oplus A\)，就得到了一个各堆物品数量异或和为 \(0\) 的局面。

对于任意一个局面，如果 \(A=0\)，那么无论如何取物品，得到的局面下各堆物品数量异或和一定不为 \(0\)。可以用反证法证明，假设 \(A_i\) 被取成了 \(A^{'}_i\)，并且 \(A_1\oplus A_2\oplus ...\oplus A^{'}_i\oplus ...\oplus A_n=0\)，由异或运算性质知 \(A_i=A^{'}_i\)，与 Nim 博弈游戏规则（不能不取）矛盾。

综上所述，由数学归纳法可知，\(A\neq 0\) 为必胜局面，一定存在一种行动使得对手面临“各堆物品数量异或和为 \(0\)”的局面。\(A=0\) 为必败局面，无论如何行动，都会让对手面临一个“各堆物品数量异或和不为 \(0\)”的必胜局面。

例题：P2197 【模板】Nim 游戏

板子题。根据 Nim 定理，当石子数量异或和不为 \(0\) 时，存在先手必胜策略，反之不存在。

代码如下（时间复杂度 \(O(Tn)\)）：

#include<bits/stdc++.h>
#define int long longusing namespace std;const int N = 1e4 + 10;int T, n;
int a[N];
int Nimsum;//Nim和 signed main()
{cin >> T;while(T --){Nimsum = 0;cin >> n;for(int i = 1; i <= n; i ++){scanf("%lld", &a[i]);Nimsum ^= a[i];}if(Nimsum != 0){puts("Yes");}else{puts("No");}}return 0;
}

公平组合游戏（ICG）与有向图游戏

公平组合游戏（ICG）：

若一个游戏满足：

1. 由两名玩家交替行动；
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3. 不能行动的玩家判负。

则称该游戏为公平组合游戏（ICG）。

Nim 博弈是一种公平组合游戏。

有向图游戏：

定义：给定一个 DAG，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是：把每个局面看成图中的结点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

博弈图：类似有向图游戏地，将博弈中所有可能的局面（状态）按递推关系画成一张 DAG，就是博弈图。

\(\text{mex}\) 运算与 \(\text{SG}\) 函数

\(\text{mex}\) 运算：

定义：设非空整数集 \(S\)，定义 \(\text{mex}(S)\) 为求出不属于 \(S\) 的最小非负整数的运算。

用公式表达为：

\[\boxed{\text{mex}(S)=\min_{x\in \mathbf{N},x\notin S}\{x\}} \]

\(\text{SG}\) 函数：

定义：在有向图游戏中，对于每个结点 \(x\)，设从 \(x\) 出发共有 \(k\) 条有向边，分别到达结点 \(y_1,y_2,...,y_k\)，定义函数 \(\text{SG}(x)\) 为 \(x\) 的后继结点 \(y_1,y_2,...,y_k\) 的 \(\text{SG}\) 函数值构成的集合再执行 \(\text{mex}\) 运算的结果。

用公式表达为：

\[\boxed{\text{SG}(x)=\text{mex}(\left\{ \text{SG}(y_1),\text{SG}(y_2),...,\text{SG}(y_k)\right\})} \]

特别地，整个有向图游戏 \(G\) 的 \(\text{SG}\) 函数值被定义为有向图游戏起点 \(s\) 的 \(\text{SG}\) 函数值，即：

\[\boxed{\text{SG}(G)=\text{SG}(s)} \]

有向图游戏的和：

设 \(G_1,G_2,...,G_m\) 是 \(m\) 个有向图游戏。定义有向图游戏 \(G\)，它的行动规则是任选某个有向图游戏 \(G_i\)，并在 \(G_i\) 上行动一步。\(G\) 被称为有向图游戏 \(G_1,G_2,...,G_m\) 的和。

有向图游戏的和的 \(\text{SG}\) 函数值等于它包含的各个子游戏 \(\text{SG}\) 函数值的异或和，即：

\[\boxed{\text{SG}(G)=\bigoplus^{m}_{i=1}\text{SG}(G_i)} \]

有向图游戏的胜负判定：

定理：有向图游戏的某个局面必胜，当且仅当该局面对应结点的 \(\text{SG}\) 函数值大于 \(0\)；有向图游戏的某个局面必败，当且仅当该局面对应结点的 \(\text{SG}\) 函数值等于 \(0\)。

证明与 Nim 博弈方法类似。

例题

例题 \(1\)：取石子游戏 1。

巴什博弈板子：

#include<bits/stdc++.h>using namespace std;int n, k;int main()
{cin >> n >> k;if(n % (k + 1)){puts("1");}else{puts("2");}return 0;
}

例题 \(2\)：移棋子游戏。

根据 \(\text{SG}\) 定理，本题所有 \(k\) 个给定节点的 \(\text{SG}\) 函数值的异或和为 \(0\) 时答案为 lose，否则为 win。

注意求 \(\text{SG}\) 函数的实现，我们采用了记忆化搜索的方式避免冗余统计：

#include<bits/stdc++.h>using namespace std;const int N = 2e3 + 10;int n, m, k;
vector<int> e[N];int mex(set<int> S)
{int res = 0;while(S.find(res) != S.end()){res ++;}return res;
}int sg[N];int SG(int u)
{if(sg[u] != -1){return sg[u];}set<int> S;for(auto i : e[u]){S.insert(SG(i));}return sg[u] = mex(S);
}int SGsum = 0;int main()
{cin >> n >> m >> k;for(int i = 1; i <= m; i ++){int u, v;scanf("%d%d", &u, &v);e[u].push_back(v);}memset(sg, -1, sizeof sg);for(int i = 1; i <= k; i ++){int u;scanf("%d", &u);SGsum ^= SG(u);}if(SGsum == 0){puts("lose");}else{puts("win");}return 0;
}

例题 \(3\)：BeiJing 2009 WC 取石子游戏。

在常规 Nim 博弈的基础上增加了取石子数量的限制集合，我们可以称这种类似 Nim 博弈的游戏为 exNim 博弈。

exNim 问题的一般解法是：通过有向图预处理 \(\text{SG}\) 函数，从而转化为 Nim 游戏求解。

对于本题，我们可以根据石子堆中石子数量 \([1,1000]\) 建 \(1000\) 个状态，并计算当前状态的 \(\text{SG}\) 函数值，将题目中的若干 \(A\) 值视为关键节点，根据 \(\text{SG}\) 定理，所有关键点的 \(\text{SG}\) 函数值的异或和为 \(0\) 则无必胜策略，反之有必胜策略。

#include<bits/stdc++.h>using namespace std;const int N = 1e3 + 10;int n, m;
int A[N], B[N];
int S[N];//set
int SG[N];
int SGsum = 0;int main()
{cin >> n;for(int i = 1; i <= n; i ++){scanf("%d", &A[i]);}cin >> m;for(int i = 1; i <= m; i ++){scanf("%d", &B[i]);}for(int i = 1; i <= 1000; i ++){for(int j = 1; j <= m; j ++){if(i < B[j]){continue;}S[SG[i - B[j]]] = i;}for(int j = 0; j <= 1000; j ++){if(S[j] != i){SG[i] = j;break;}}}for(int i = 1; i <= n; i ++){SGsum ^= SG[A[i]];}if(SGsum == 0){puts("NO");}else{puts("YES");for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){if(A[i] < B[j]){continue;}if(SG[A[i] - B[j]] == (SGsum ^ SG[A[i]]))//N-set{printf("%d %d", i, B[j]);return 0;}}}}return 0;
}