博弈论基础
前置知识
前言
博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏。
只需要关注公平组合游戏 \(\texttt{(ICG)}\)，反常游戏是公平组合游戏的变形，经济类博弈也不是博客所讨论的范围
- 两个玩家轮流行动且游戏方式一致。
- 两个玩家对状况完全了解。
- 游戏一定会在有限步数内分出胜负。
- 游戏以玩家无法行动结束。
博弈的双方都被认为是神之个体，因为所有玩家对状况完全了解，且充分为自己打算，绝对理性。
当局面确定，结果必然注定，并且没有任何随机的成分。
游戏中的每一个状态，最终导致的结果也必然注定，只有必胜态、必败态，两种状态。
这一类博弈问题的结果没有任何意外，一方可以通过努力去改变结果是不可能的，这一点是反直觉的。
- 常用对数器打表来找规律。
- 博弈论的题目就是 要干去干，去找规律，不要怕。
巴什博弈 \(\texttt{(Bash)}\)
\(n\) 个的石头，每次操作可以拿走 \([1,m]\) 个石头。拿到最后 \(1\) 个石头的人获胜（也就是不能拿石头的人输）。
这个问题特别简单，就是显然答案是如果 \(n\) 为 \(m+1\) 的倍数那么先手输，否则先手赢。
\(\texttt{sg}\) 函数
接下来引入 \(\texttt{sg}\) 函数。
\(\texttt{sg}\) 表示当前状态的胜负情况。
有如下公式 \(sg(A)=\operatorname {mex} (sg(B)|A\to B)\)。
式子中的 \(A\) 和 \(B\) 表示状态，\(A\to B\) 表示 \(A\) 状态可以达到 \(B\)状态。也就是说我们可以通过 \(A\) 能达到的状态的SG函数值推算出 \(A\) 的 \(SG\) 值。
如果 \(\texttt{sg}\) 值为 \(0\) 则表示先手输，否则先手赢。
数学归纳法证明：
- 最终状态 \(SG=0\)。
- 对于任意一个必胜态 \(SG\not=0\)，存在一个后继态 \(SG=0\)
- 对于任意一个必败态 \(SG=0\)，不存在一个后继态 \(SG=0\)。
\(\texttt{e.g.}\)：在巴什博奕中：当 \(m = 2\) 时，\(\texttt{sg[0]=0,sg[1]=1,sg[2], sg[3]=0,}\cdots\)。
\(\texttt{FAQ}\):
- Q: 不就是判断一个输赢吗？为什么要用一个 \(\texttt {int}\)，我 \(\texttt{bool}\) 也可以啊。
- A: 是的，确实可以只有 \(\texttt{bool}\)，用 \(\texttt{int}\) 另有用途，我们下面会讲。
P2197 【模板】\(\texttt{(Nim)}\) 游戏——\(\texttt{sg}\) 多个独立的子问题的合并
题目描述
甲，乙两个人玩 \(\texttt{nim}\) 取石子游戏。
\(\texttt{nim}\) 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
公式引入
若局面X由若干个子游戏 \(X1,X2...Xn\) 构成，则
\(SG(x)=SG(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)\)
数学归纳法证明：
- 最终局面成立
- \(\forall X\)，所有后继局面可以取到 \(G(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)-1\)，取不到\(SG(X_1)\oplus SG(X_2) \oplus \cdots \oplus SG(X_n)\)
同样看做 \(\texttt{Nim}\) 游戏
设 \(S \rightarrow S_1\)
\(S \oplus (S \oplus S_1) =S_1\)
设 \((S \oplus S_1)\) 最高位为 \(k\)，存在 \(A\) 使得 \(k\) 位为 \(1\)。
那么\(A \oplus (S \oplus S_1) < A\)，所以让 \(A\) 变成\(A \oplus (S \oplus S_1)\)就行了。
这就是 \(\texttt{SG}\) 定理( \(\texttt{Bouton}\) 定理)。
问题解答
显然对于每一个子问题，对于石头个数为 \(n\)， \(\texttt {sg(n)=n}\)。
所以 \(SG=\oplus_{i=1}^{n}a_i\)。判断 \(\oplus_{i=1}^{n}a_i 是否为零即可\)
代码
#include<bits/stdc++.h>
using namespace std;
int t, n, a;
signed main(){
scanf("%d", &t);
while (t--) {
scanf ("%d", &n); int ans = 0;
while (n--) scanf("%d", &a), ans ^= a;
if (ans == 0) puts("No"); else puts("Yes");
}
return 0;
}
P4279 [SHOI2008] 小约翰的游戏
题目描述
甲，乙两个人玩 取石子游戏。
游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(5000\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就赢了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
这一题唯一的区别是 最后没石子可取的人就赢了。
题目解析
首先，如果 \(\forall i\) 有 \(a_i=1\)，那么就是看 \(n\) 的奇偶性了。
其次，如果只有一个 \(a_i\not=1\)，那么先手必赢 为什么
最后，因为要的是“只有一个 \(a_i\not=1\)”，异或和不为 \(0\), 所以只要抓住异或和不为 \(0\) 即可获胜，那么就转化为 \(\texttt{(Nim)}\) 游戏了。
示例代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int t, n, x, ans, sum;
scanf("%d", &t);
while (t--) {
cin >> n, ans = sum = 0;
for(int i = 1; i <= n; ++ i) scanf("%d", &x), ans ^= x, sum += x;
if(sum == n) puts(n & 1 ? "Brother" : "John");
else puts(ans ? "John" : "Brother");
}
return 0;
}
P6487 [COCI2010-2011#4] HRPA ——斐波那契博弈
前置知识
- 斐波拉契数列：
- 齐肯多夫（Zeckendorf）定理：任何正整数都可以表示成若干个不连续的斐波那契数之和。如 \(4=1+3(1\) 和 \(3)\) 不相邻。
证明：
- 若正整数 \(n\) 为斐波那契数，得证。
- 否则，先取 $ F_{t_1} $，其中 $ t_1 $ 满足 $ F_{t_1} < n < F_{t_1 + 1} $。
- 令 $ n' = n - F_{t_1} $，同上一步取出一个 $ F_{t_2} $ 满足 $ F_{t_2} < n' < F_{t_2 + 1} $。
- 只要证明 $ t_1 \neq t_2 + 1 $。考虑反证法：
- 假设 $ t_1 = t_2 + 1 $，则第一步取出的应当是 $ t_1 + 1 $ 而不是 $ t_1 $。原因是 $ F_{t_1 + 1} = F_{t_1} + F_{t_1 - 1} $。
题目分析
如果 \(t\) 为斐波拉契数，那么必须全部取完。
设 $ n = F_{i b_t} $，我们把 $ n $ 看成 $ F_{i b_{t-1}} $ 和 $ F_{i b_{t-2}} $ 两堆。
- 若第一步取的个数超过 $ F_{i b_{t-2}} $，则后手可以直接取完剩余石子。
- 否则，该问题变成了一个规模更小的同样的问题。
考虑 $ n = 2 $ 的情况（即规模最小的情况），先手只能取 1，于是后手取 1获胜。
可以结合下面理解一下
比如 \(43=34+8+1\) 那么答案为 \(1\)。
首先取走 \(1\)，然后如果对方选择的数只能选择 \([1,2]\)
假如对方取的是 \(2\)，那么 \(8=3+5\)，我选择把 \(3\) 消掉，我就选择 \(1\)。
这时数字变成了 \(34+5\)
对方又只能选择 \([1,2]\), 假如他选择 \(1\),那么 \(5=2+3\),我就把 \(2\)消掉，选择 \(1\)
这时数字变成 \(34+3\)
对方又只能选择 \([1,2]\), 假如他选择 \(2\),那么我就把 \(3\)消掉，选择 \(1\)
这时数字变成 \(34\)
对方又只能选择 \([1,2]\), 假如他选择 \(2\),那么\(34=21+8+5\)消掉，我就把 \(5\) 消掉，选择 \(3\)
这时数字变成 \(21+8\)
对方又只能选择 \([1,6]\), 假如他选择 \(6\),那么\(29=21+8\)消掉，我就把 \(8\) 消掉，选择 \(2\)
这时数字变成 \(21\)
对方又只能选择 \([1,6]\), 假如他选择 \(6\),那么\(29=21+8\)消掉，我就把 \(8\) 消掉，选择 \(2\)
这时数字变成 \(21\)
对方又只能选择 \([1,4]\), 假如他选择 \(4\),那么\(21=13+8\)消掉，我就把 \(8\) 消掉，选择 \(4\)
这时数字变成 \(13\)
对方又只能选择 \([1,8]\), 假如他选择 \(8\),那么\(13=8+5\)消掉，我就把 \(5\) 直接消掉，获得胜利。
例题
例一：两堆石头的巴什博弈
题目描述
有两堆石头，数量分别为 \(a\)、\(b\)
两个人轮流拿，每次可以选择其中一堆石头，拿 \([1,m]\) 颗
拿到最后一颗石子的人获胜，根据 \(a\)、\(b\)、\(m\) 返回谁赢。
题解
根据 \(\texttt{SG}\) 定理，只要 \(sg[a] \oplus sg[b] \not = 0\) 即可，即 \(sg[a] \not = sg[b]\)，即 \(a \not \equiv b \pmod{m}\)。
代码
bool solve (int a, int b, int m) {return a % m != b % m; }
例二：三堆石头拿取斐波那契数博弈
题目描述
有三堆石头，数量分别为 \(a,b,c(a,b,c\le 10^5)\)。
两个人轮流拿，每次可以选择其中一堆石头，拿取斐波那契数的石头
拿到最后一颗石子的人获胜，根据 \(a,b,c\) 返回谁赢。
直接分别计算 \(\texttt{sg}\) 值即可。因为 \(\texttt{sg}\) 值都只会从最多 \(25\) 个后继推出，所以 \(\forall i, \texttt{sg[i]}\le30\)。时间复杂度为 \(O(nm)\)。 其中 \(m\) 为 \([1,n]\) 中斐波那契数的个数。
例三：P2148 [SDOI2009] E&D
题目描述
桌子上有 \(2n\) 堆石子，编号为 \(1,2,3\cdots,2n\)。
其中 \(1,2\) 为一组；\(3, 4\) 为一组； \(5, 6\) 为一组 \(,\cdots, 2n-1,2n\) 为一组。
每组可以进行分割操作：
- 任取一堆石子，将其移走，然后分割同一组的另一堆石子
- 从中取出若干个石子放在被移走的位置，组成新的一堆
- 操作完成后，组内每堆的石子数必须保证大于 \(0\)
- 显然，被分割的一堆的石子数至少要为 \(2\)
两个人轮流进行分割操作，如果轮到某人进行操作时，所有堆的石子数均为 \(1\)，判此人输掉比赛。
返回先手能不能获胜。
题目解析
首先 \(\texttt{sg(x,y)}\) 表示当前一组内石子数分别为 \(x,y\) 的胜负情况。
直接暴力算出 \(20\times20\) 的 \(\texttt{sg}\) 表。
找规律。
发现 \(sg(x, y)=f((x-1)|(y-1))\)。
其中 \(f(x)\) 表示 \(x\) 最低 \(0\) 的位置如 \(8=(1000)_2,f(8)=0;7=(0111)_2,f(7)=3\)。
详细证明见 题解 P2148 【[SDOI2009]E&D】。
代码易得，略。
例四：CF87C Interesting Game
题目简述
每次可以把一堆石子分成若干堆，使得分裂的石子是公差为 \(1\) 的等差数列。不能分的人输。
题目分析
直接算 \(\texttt{sg}\) 值。详见代码。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, sg[N], mex[N];
int main() {
scanf("%d", &n);
int ans = -1, cnt = 1;
for (int i = 3; i <= n; i++) {
for (int m = 2;; m++) {
int sum = i - (m - 1) * m / 2; // 都减去变成 a, a, a, a 的形式
if (sum < 0) break;
if (sum % m) continue;
int g = 0;
for (int j = 0; j < m; j++) g ^= sg[sum / m + j];
if (!g && i == n && !~ans) ans = m;
mex[g] = i; // 更新 mex； 如果 mex[g] != i 说明当前 i 的后继没有 sg = g 的。
}
for (int j = 0;; j++) {
if (mex[j] != i) { // sg 函数定义
sg[i] = j;
break;
}
}
}
printf("%d\n", ans);
return 0;
}
例五：AGC002E Candy Piles
题目描述
有 \(n\) 堆石子，每堆石子有 \(a_i\) 个，两人轮流操作。要么取走石子最多的一堆，要么将每堆石子取走 \(1\) 个。谁取走最后 \(1\) 个石子，谁就输了。假设两人都足够聪明，求先手必胜还是后手必胜。
\((1 \leq n \leq 10^5,1 \leq a_i \leq 10^9)\)
Solution
不妨先按 \(a_i\) 从大到小排序。对于石子最多的一堆，只要不直接取完，那么这堆石子仍然是最多的。
举个例子，对于 \(\{a\} = \{7,7,7,6,4,4,4,2,2\}\)，排完序后能够得到下图。
对于取走石子最多的一堆，实际就是消去最左边一行；对于取走每堆石子取走 \(1\) 个，实际就是消去最下面一行。
我们不妨再把点阵转化为一个网格图。
从原点开始，每人每次可以选择向右或向上移动一格，向右代表消去最左边一行，向上代表消去最下面一行。很容易发现，当走到网格图的边界（下图中的实线部分）时，所有石子刚好被取完。
显然边界上的点都是必败点，因为谁走到边界谁就输了。
对于任意一个不在边界上的点，如果它的上面和右面都是必败点，那么这个点一定是必胜点。如果它的上面和右面有一个是必胜点，那它就是必败点。（下图用 ○ / × 分别表示必败点和必胜点）
因为从原点 \((0,0)\) 出发，所以当原点是必胜点时，后手必胜；原点是必败点时，先手必胜。
将整个网格图构造出来复杂度太大，所以考虑找规律：
除了边界外，同一对角线上的点全部是相同类型的点。
我们可以通过算出原点最右上方且不在边界上的点的类型，来知道原点是必胜点还是必败点。
找到以原点为左下角的最大正方形，设其右上方顶点为 \((i,i)\) 。当它到最上面且不在边界上的点的距离和最右面且不在边界上的点的距离其中一个为奇数时，这个点为必败点，反之这个点为必胜点。
例六：CF388C Fox and Card Game
题目描述
桌子上有 \(n\) 堆牌。每张牌上都有一个正整数。Ciel 可以从任何非空牌堆的顶部取出一张牌，Jiro 可以从任何非空牌堆的底部取出一张牌。Ciel 先取，当所有的牌堆都变空时游戏结束。他们都想最大化他所拿牌的分数（即每张牌上正整数的和）。问他们所拿牌的分数分别是多少？
题目解析
因为对于每一张牌，如果 A 和 B 都想要，那么归近的一方。
所以每个人都拥有靠近他的一半。
只要分配中间的就行。
显然排序在 先、后、先、后的分配。
代码
#include <bits/stdc++.h>
using namespace std;
int n, k, x, aa, ab;
vector <int> m;
bool cmp (int a, int b) {return a > b;}
int main() {
cin >> n;
while (n--) {
cin >> k;
for (int i = 1; i <= (k / 2); i++)
cin >> x, aa += x;
if (k & 1) cin >> x, m.push_back(x);
for (int i = 1; i <= (k / 2); i++)
cin >> x, ab += x;
}
sort (m.begin(), m.end(), cmp);
for (int i = 0; i < m.size(); i++) {
if (i % 2 == 0) aa += m[i];
else ab += m[i];
}
cout << aa << ' ' << ab << '\n';
}
例七：ABC297G Constrained Nim 2
题目描述
给定 \(n\) 堆喵喵，你（First）和 lbw（Second） 轮流吃，每次可以选其中一堆、然后吃掉 \(l \sim r\) 个喵喵。谁不能吃喵喵了谁就输了。问谁会赢？
题解
找规律发现 \(\texttt{sg(x)}=x % (l + r) / l\)。
然后用 \(\texttt{SG}\) 定理合并。
示例代码
#include <bits/stdc++.h>
using namespace std;
int n, l, r, SG, x;
int sg(int x) { return x % (l + r) / l;}
int main() {
cin >> n >> l >> r;
for (int i = 1; i <= n; i++) {
cin >> x;
SG ^= sg(x);
}
cout << (SG ? "First" : "Second");
}
例八：CF850C Arpa and a game with Mojtaba
题目描述
Mojtaba和Arpa在玩一个游戏。
游戏中有一个 \(n\) 个数的数列，在一个回合中，他可以选取一个形如 \(p^k\) 的数，其中 \(p\) 是个质数，而 \(k\) 是一个正整数，并且满足这个数列中至少有一个数能被它整除。每一个回合结束时将整个数列中所有的能被这个数整除的数都将除以这个数。
（例如数列 \(\{1,1,17,289\}\) 如果选取了\(17\)，经过一个回合之后数列将变成 \(\{1,1,1,17\}\)）
而游戏胜负的条件是有一个人如果无法选出这样一个数就输了
游戏中Mojtaba先手，游戏双方都将用最优策略，输出胜利者的名字。
题目解析
因为每次只能删除 \(1\) 种质数，所以每一种质数互不干扰。考虑分开计算，最后求异或和。
显然我们要质因数分解。
对于每一个质数，显然如果有对个 \(k\) 相等那么相当于 \(1\) 个。又因为 \(p^k\le10^9\)，所以 \(k\le32\)。所以可以状压。用 \(b_i\) 记录这一个 \(k\) 有没有出现过，然后枚举除数 \(p^k\) 中的 \(k\) 进行 \(\texttt{SG}\) 转移（求 \(\operatorname{mex}\)）。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
map<int, int> mp, f; // 状态压缩； 记忆化
int SG(int x) {
if (!x) return 0; // 什么都没有就什么都不用干
if (f.count(x)) return f[x]; // 记忆化
set<int> st; // mex
int t = 0, p = x;
while (p) p >>= 1, t++; // 最高位（因为要保证有一个数能被除）
for (int i = 1; i <= t; i++)
st.insert(
SG((x >> i) | // 前半部分是被除以的，所以左移；
(x & ((1 << (i - 1)) - 1))) // 后半部分是只留取后 [1, i - 1] 位的
);
int now = 0;
while (st.count(now)) now++; // 求 mex
return f[x] = now; // 记忆化
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
for (int j = 2; j * j <= x; j++) {
if (x % j == 0) {
int cnt = 0;
while (x % j == 0)
cnt++, x /= j;
mp[j] |= (1 << (cnt - 1));
}
}
if (x > 1)
mp[x] |= 1;
}
int res = 0; // 异或和
for (auto i : mp)
res ^= SG(i.second); // 对于每一个子问题 (每一个质数)求解 SG
if (res)
cout << "Mojtaba" << endl;
else
cout << "Arpa" << endl;
}
例九：CF2004E Not a Nim Problem
题目描述
两个玩家 Alice 和 Bob 正在玩游戏。他们有 \(n\) 堆石头，其中第 \(i\) 堆最初包含 \(a_i\) 块石头。
轮到自己时，玩家可以选择任意一堆石头并从中取出任意数量的石头，但有一个条件：
- 假设堆中当前的石子数量为 \(x\) 。不允许从堆中取出数量为 \(y\) 的石子，使得 \(x\) 和 \(y\) 的最大公约数不等于 \(1\) 。
无法行动的玩家输了。两名玩家都发挥最佳水平(也就是说，如果一名玩家有一个可以让他们获胜的策略，那么无论对手如何回应，他都会获胜)。爱丽丝先走。
确定谁将获胜。
题目解析
肯定要计算 \(\texttt{SG}\) 值。
但是 \(a_i\le 10^7\)， \(O(n^2)\) 肯定不行。那么只能打标找规律。
0 1 2 3 4 5 6 7 8 9
0 1 0 2 0 3 0 4 0 2
10 11 12 13 14 15 16 17 18 19
0 5 0 6 0 2 0 7 0 8
20 21 22 23 24 25 26 27 28 29
0 2 0 9 0 3 0 2 0 10
30 31 32 33 34 35 36 37 38 39
0 11 0 2 0 3 0 12 0 2
40 41 42 43 44 45 46 47 48 49
0 13 0 14 0 2 0 15 0 4
50 51 52 53 54 55 56 57 58 59
0 2 0 16 0 3 0 2 0 17
60 61 62 63 64 65 66 67 68 69
0 18 0 2 0 3 0 19 0 2
70 71 72 73 74 75 76 77 78 79
0 20 0 21 0 2 0 4 0 22
80 81 82 83 84 85 86 87 88 89
0 2 0 23 0 3 0 2 0 24
90 91 92 93 94 95 96 97 98 99
0 4 0 2 0 3 0 25 0 2
通过表可以发现一些性质：
- 所有偶数的 \(\texttt{SG}\) 值都是 \(0\)。
参考资料
- 博弈类问题必备内容详解-上
- 博弈类问题必备内容详解-下
- SG 函数 & 博弈论
- OI-WiKi
- 博弈论 | 详解搞定组合博弈问题的SG函数
- [组合游戏与博弈论]【学习笔记】
- [COCI2010-2011#4] HRPA
- 题解 AT1999 【Candy Piles】