【学习笔记】博弈论 ---- 非偏博弈
博弈论入门
前言：
本篇按照 Qingyu 在省集讲的加入我这个萌新的萌新理解而成。
听了 Qingyu 的博弈论讲解，感觉我之前学过的博弈就是冰山一角。
由于有一些东西没听懂，就主要写写我听懂的部分，没懂得以后再说吧。
所以这篇只是一个入门，关于博弈的一些习题可能会咕咕咕。
平等博弈（非偏博弈）：
基础知识：
几个基本定义：
- Nimber（即 SG 值），使用 \(*_k\) 代表一堆 Nimber 为 \(k\) 的石子对应的博弈
- 基本的平等博弈的分析技巧：打表 SG 值、转化为经典模型
- Nim 和：\(*_a + *_b = *_{a \oplus b}\)，其中 \(\oplus\) 即按位异或。
在平等博弈中有如下的几种常见的性质以及技巧：
- 在分析问题时可以使用模仿的思想：
- 在阶梯 Nim 游戏中，可以理解为，先手将石子从偶数位移到奇数位后，后手可以将奇数位的这些石子不动地移动到偶数位，而地面为 \(0\) 为偶数位，也就是可以一直移动直到删除，那么偶数位就无用了，将奇数位的石子移动到偶数位就可以理解为删除
- Nimber 的性质：\(*_a + *_a = 0 \to *_a = -*_a\)，也就是我们的插入和删除本质上是相同的
- 必胜态的后继状态一定存在必败态，必败态的后继状态一定全是必胜态。
Anti-SG 游戏：
在原始的 sg 游戏中取最后一个若定义为输，则其被定义为 anti-sg，其满足以下性质：
若当局面中所有单游戏的 SG 值为 \(0\) 则游戏结束，则先手必胜当且仅当：
-
游戏的 SG 值不为 \(0\) 且游戏中某个单一游戏的 SG 大于 \(1\)
-
游戏的 SG 值为 \(0\) 且游戏中没有单一游戏的 SG 大于 \(1\)
这个定理证明过于复杂，在我写的《【学习笔记】博弈论(1)》里有，可以看看。
Multi-SG 游戏：
我们定义 Multi-SG 游戏满足以下的特征：
-
在符合拓扑序的前提下，Multi-SG 的每一个后继状态均为多个单一的游戏
-
Multi-SG 游戏的其他规则与一般 SG 游戏规则一致。
在这种情况下一个后继状态的 SG 值即为多个独立游戏的 SG 值的异或和。
对于一个二维的游戏，如果两个维度相互独立则可以证明：可以将两个维度独立计算，两个的 Nim 和即游戏的 SG 值
Nim 积：
我们定义两个非负整数之间的 \(\otimes\) 运算为 Nim 积运算，其满足如下的定义式：
并且满足以下的式子：
Nim 积有交换律、结合律和对 Nim 和的分配律。
为了高效计算 Nim 积，引入 Fermat power 的定义：我们定义形如 \(2^{2^{k}}\) 的数称为 Fermat power，那么它有如下的性质：
-
对于 \(n\)，若 \(N > n\) 且 \(N\) 为 Fermat power，则 \(n \otimes N = n \times N\)
-
若 \(N\) 为 Fermat power，则 \(N \otimes N = \frac{3}{2}N\)
因此我们就可以利用上述的性质快速计算 Nim 积。
考虑设 \(f(x,y) = x \otimes y\)，我们可以考虑按照二进制每一个单独考虑，即设 \(g(x,y) = 2^x \otimes 2^y\) 则 \(f(x,y) = \oplus_{x' \in x,y' \in y}\ \ g(x',y')\)，这里定义的 \(x' \in x\) 就是指的 \(x\) 二进制下 \(x'\) 这一位为 \(1\)。
然后下面就是考虑如果计算 \(2^x \otimes 2^y\) 的情况，也就是求解 \(g(x,y)\)，考虑 \(x,y\) 二进制下的最高位 \(k\)：
考虑将 \(x,y\) 按二进制拆分，从高到低考虑每一位，如果当前位均为 \(0\) 则忽略这一位，下面就是分类讨论一下：
若当前位都为 \(1\)：设 \(M = 2^{2^k},X = 2^{x - 2^{k}},Y = 2^{y - 2^{k}}\)，答案可以如下推导：
若当前位仅有一个为 \(1\)：设 \(x\) 这一位为 \(1\)，则类似设 \(M = 2^{2^{k}},X = 2^{x - 2^{k}},Y = 2^y\)，答案可以如下推导：
递归的考虑上述问题，按两种情况分类之后，可以得到如下的结论：
时间复杂度显然为 \(O(\log x \log y)\)
代码实现如下：
点击查看代码
#define Resolve(i, x) for (int u = (x), i = 0; (1ll << i) <= u; ++ i) if (u >> i & 1)
ll f(ll x, ll y);
ll g(int x, int y) {
if (!x || !y) return 1ll << (x | y);
if (~ tab[x][y]) return tab[x][y];
ll res = 1;
Resolve(i, x ^ y) res <<= (1 << i);
Resolve(i, x & y) res = f(res, 3ll << ((1 << i) - 1));
return tab[x][y] = res;
}
ll f(ll x, ll y) {
if (!x || !y) return 0;
if (x == 1 || y == 1) return max(x, y);
ll res = 0;
Resolve(i, x) Resolve(j, y) res ^= g(i, j);
return res;
}
经典模型：
掌握了这些理论知识，下面就要开始看一些经典的博弈问题了（感觉可能以后会换换顺序）：
Nim 博弈：
见《【学习笔记】博弈论（1）》
"翻硬币"游戏：
下面大概对着 《Game Thoery》的思路说了一下，加一些我自己的萌萌的解释
首先对"翻硬币"游戏进行定义：\(n\) 个硬币排成一排，每个硬币可能为正面可能为反面，从左到右按 \(1\) 到 \(n\) 编号，其必须满足以下的规则
-
对于我们按照规则约束的一次翻硬币的过程中，最右边的硬币必然从正面变成反面
-
定义不能翻的人为输
在这种定义下其满足这样的性质：
当前局面的 SG 值等于每个正面向上的棋子单独存在时的 SG 值的异或和。
例如：\(G(\text{10110}) = G(\text{1}) \oplus G(\text{001}) \oplus G(\text{0001})\)。
所以我们在此类问题中只需要考虑一个棋子的情况，所以在下文的所有类型中在不进行特殊标注的前提下，都默认只有最右边的棋子为正，其他的为负。
规则约束一：每次只能翻一个硬币
考虑对于一堆既有正也有反的硬币，按照上文的定理我们既然每次只能翻一个硬币，那么对于任意一个单独的正的棋子它的 SG 值都为 \(1\)，所以当前局面的 SG 值就为正棋子的个数的奇偶性，其中奇数为 \(1\)，偶数为 \(0\)。
规则约束二：每次可以翻转一个或者两个硬币（不要求连续）
依旧考虑一堆既有正也有负的棋子，我们将初始编号设为 \(0\)，并将每个棋子的 SG 值设为它的编号，则此时就等价于 Nim 游戏。
（不是很会证明）
规则约束三：每次必须连续翻转 \(k\) 个棋子
假设 \(k=3\)，可以有如下的分析：
当 \(n = 1\)，硬币：正，则先手必输，此时 \(SG[1] = 0\)
当 \(n = 2\)，硬币：负正，则先手必输，此时 \(SG[2] = 0\)
当 \(n = 3\)，硬币：负负正，先手翻转一次后的状态为：正正负，此时 \(SG[3] = \text{mex}\{0,0\} = 1\)
同理分析可以得到如下表格：
| n | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| SG | 0 | 0 | 1 | 0 | 0 | 1 |
所以其实当 \(k=3\) 时，我们的 SG 值的变化为 \(001001001\cdots\)
所以同理当 \(k \not= 3\) 时，SG 值就为 \(000\cdots001000\cdots001\cdots\)
其中每段中间的 \(0\) 的数量就是 \(k-1\)。
规则约束四：每次翻转 \(x\) 必须选择 \(x-1,x-2,x-3\) 中的一个翻转，除非 \(x\) 小于等于 \(3\)。（Subtraction Games）
当 \(n=1\)，硬币：正，则先手翻转一次后的状态为：负，此时 \(SG[1] = \text{mex} \{0\} = 1\)
当 \(n=2\)，硬币：负正，则先手翻转一次后的状态为：负负、正负，此时 \(SG[2] = \text{mex} \{0,1\} = 2\)
当 \(n=3\)，硬币：负负正，则先手翻转一次后的状态为：负正负、正负负、正正负，此时 \(SG[3] = \text{mex}\{2,1,0\} = 3\)
同理可以得到以下表格：
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| SG | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
趋势是十分明显的，如果限制不是 \(3\) 而是一些其他的值得到的结果也是类似的。
规则约束五：每次必须翻动两个硬币，且这两个硬币的距离必须在 \(S = \{1,2,3\}\) 中，硬币编号从 \(0\) 开始。（Twins 游戏）
当 \(n=1\)，硬币：正，则先手无法翻动，此时 \(SG[0] = 0\)。
当 \(n=2\)，硬币：负正，则先手翻动一次后的状态为：正负，此时 \(SG[1] = \text{mex}\{0\} = 1\)
当 \(n=3\)，硬币：负负正，则先手翻动一次后的状态为：正负负、负正负，此时 \(SG[2] = \text{mex}\{0,1\} = 2\)
同理可得以下表格：
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| SG | 0 | 1 | 2 | 3 | 0 | 1 | 2 |
规则约束六：每次可以翻动一个、两个或三个硬币，硬币编号从 \(0\) 开始。（Mock Turtles 游戏）
当 \(n=1\)，硬币：正，则先手翻动一次后的状态为：负，此时 \(SG[0] = \text{mex}\{0\} = 1\)
当 \(n=2\)，硬币：负正，则先手翻动一次后的状态为：负负、正负，此时 \(SG[1] = \text{mex}\{0,1\} = 2\)
当 \(n=3\)，硬币：负负正，则先手翻动一次后的状态为：负负负、负正负、正负负、正正负，此时 \(SG[2] = \text{mex}\{0,2,1,3\} = 4\)
同理可得以下表格：
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| SG | 1 | 2 | 4 | 7 | 8 | 11 | 13 | 14 | 16 | 19 |
可以发现值要么为 \(2\times x\) 要么为 \(2 \times x + 1\)。
我们此时定义一个非负整数 odious 当且仅当其二进制下 \(1\) 的个数为奇数，否则则定义为 evil，所以结论如下：
规则约束七：每次可以翻动任意多个连续的棋子，要求至少翻动一个。(Ruler 游戏)
考虑后继状态，如果我们翻动了 \(i\) 个，且总共有 \(n\) 个，则这个后继状态的 SG 值为：\(\oplus_{j \in [n-i+1,n-1]}\ \ SG[j]\)，需要特别注意的是，翻动 \(1\) 个的后继状态的 SG 值为 \(0\)，因为此时棋子全部为负。那么就有如下的式子：
依旧是注意 \(j=1\) 时括号内的值为 \(0\)。
此时打表出来即如下所示：
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| SG | 1 | 2 | 1 | 4 | 1 | 2 | 1 | 8 |
很显然 \(SG[n] = \text{lowbit}(n)\)
巴什博弈：
问题描述：一堆石子有 \(n\) 个，先后手轮流取，一次取 \([1,m]\) 个，无法操作的人为输.
结论：若 \(n \% (m+1) = 0\) 则先手必败。
证明：
若 \(n = m + 1\)，设先手取 \(x\) 个，则后手一定可以取 \(m + 1 - x\) 个，然后先手必败。
若 \(n = p(m+1)\)，则可以仿照上述的思路，每一次两人操作都使得 \(n\) 减少 \(m-1\)，先手必败。
若 \(n = p(m+1)+q\)，则先手可以一步将局势变为 \(n = p(m+1)\) 则此时后手必败。
威佐夫博弈：
问题描述：有两堆石子个数不一定相同，先后手轮流取，一次可以从一堆中取若干个或者从两堆中同时取若干个，无法取的人输。
结论：面对非奇异局势，则先手必胜，反之后手必胜。
证明：
首先就要定义一下什么叫做奇异局势，我们设一个局势为一个二元组 \((A,B)\) 分别表示两堆石子的数量，我们定义奇异局势就是先手必败的局势，可以发现奇异局势有很多的性质。
可以发现，前几个奇异局势如下：\((0,0)\)、\((1,2)\)、\((3,5)\)、\((4,7)\)
根据一堆复杂的推导，我们发现奇异局势一定满足如下公式：\(A_k = \big\lfloor k \times \dfrac{\sqrt{5} + 1}{2} \big\rfloor,B_k = A_k + k\)
我们就可以通过上述的式子判断奇异局势。
奇异局势有以下的性质：
- 任何自然数都被唯一的包含在一个奇异局势中
- 任何一个奇异局势都只能通过一次操作变成非奇异局势
- 任何一个非奇异局势都一定可以通过某个操作变为奇异局势
后面两条其实就是我们平等博弈的重要性质：必胜态的后继一定存在必败态，必败态的后继一定均为必胜态。
Fibonacci Nim：
问题描述：
有如下的规则：
- 先手不能在第一次把所有的石子取完
- 之后每一次可选择的石子数量下界为 \(1\) 上界为上一次取得个数乘 \(2\)。
结论：所有的必败态构成 Fibonacci 数列
证明就是要引入一个定理：Zeckendorf 定理：任何一个非负整数必然可以分解为不连续的 Fibonacci 数之和。
具体证明就是先通过数学归纳法证明当 \(n\) 为 Fibonacci 数时成立，然后再考虑若 \(n\) 不是则分解之后继续证明。
具体的证明在这里：有点复杂，感觉没啥营养
Green Hackenbush（无向图删边）：
Hackenbush 的一般问题描述为：给定一个有根图，其中地面为根，可以用一条虚线表示，每次可以删去一条边以及删去这条边后与地面断开的边，直到没有边与地面相连。
现在是平等博弈章节，仅讨论这个游戏的平等博弈版本，也就是每个玩家在其回合内可以删除任意的一条边，在以后我们会称这种每个玩家都可以删除的边为绿边。
情况一：Bamboo Stalks
可以算是 Green Hackenbush 的引入，问题描述具体为：给定一个具有 \(n\) 条边的线形图，其余规则同上。
具体可以根据下图来理解这个博弈：
设总共有 \(n\) 条线，其包含的边数分别为 \(A_1,A_2,A_3,\cdots,A_n\)，则该问题等价于 \(N\) 堆石子，每堆石子分别为 \(A_1,A_2,A_3,\cdots,A_n\) 的 Nim 博弈，因为我们进行的操作本质相同。
情况二：Green Hackenbush on Tree
问题描述：给定 \(n\) 棵树，根连接在地面上，其余规则同上。
具体可以根据下图来理解这个博弈：
根据情况一我们将这个游戏与 Nim 博弈结合了起来，所以其实对于解决此类问就是考虑如何计算对应的 SG 值。
对于这个问题我们要用到一个定理 Colon Principle：对于一个树上的节点，如果与它连接的路径都为线形结构，设各个路径的长度为 \(a_1,a_2,a_3,\cdots,a_n\)，则可以直接将这些路径用长度为 \(\oplus_{i=1}^n a_i\) 的线性结构代替
如下图所示：
我用红框标注的点就是每一次选择将边变为线性结构的点，看这个图应该很好理解。
Colon Principle 的证明也是简单的：就是我们对于原来图中任意删除一个边使得 SG 值产生的影响，在新图中必然也能做到。（当个感性理解就好）
情况三：Green Hackenbush on general rooted graphs
问题描述：给定一个任意图，可能有环可能一个联通块有多个根连在地面上，其余规则同上。
具体可以根据下图来理解这个博弈：
也是要求一下 SG 值，这个时候就有了一个新的定理：
The Fusion Principle：任何一个环内节点都可以缩成一个点而不影响图的 SG 值。
如下所示：
地面也可以理解为一个节点，所以第一步成立。
将这三个点两两缩为一个点，所以第二步成立。
此时每一个环都相当于一个长度为 \(1\) 的线形图，所以第三步成立。
根据 Colon Principle，所以第四步成立。
进而我们其实可以得到以下的推论：
任意一个奇环都可以缩成一条边，任意一个偶环都可以缩成一个点。
所以类似的就可以得到下图这种结论：
小练习
下面就是一些 Exercise，完成这一部分我们的平等博弈就算是完结撒花了
[清华集训2016]Alice 和 Bob 又在玩游戏 QOJ4549
问题描述：
有 \(n\) 个节点， \(m\) 条边（\(0 \le m \le n - 1\)），构成若干棵有根树，每棵树的根节点是该连通块内编号最小的点。
Alice 和 Bob 轮流操作（Alice 先手），每回合选择一个没有被删除的节点 \(x\)，将 \(x\) 及其所有祖先全部删除，不能操作的人输。
假设 Alice 和 Bob 都足够聪明，问 Alice 有没有必胜策略。
\(n \le 10^5\)
问题分析：
一开始的若干棵有根树相当于子游戏，所以只需要对于每一棵树单独求解它的 SG 值，最后异或即为所求。
对于单独一棵树，我们选择一个节点删除之后，相当于把树再次分成了若干棵树，也就是相当于一个 Multi-SG 游戏，所以对于每一个后继状态我们只需要递归下去继续求解即可。
其实我们就是要对于每一个点求 \(SG_u\) 表示 \(u\) 子树内的 SG 值，\(S_u\) 表示删除 \(u\) 到根的路径上的点的局面的 SG 的异或和。
那么也就是相当于：\(S_v = S_u \oplus SG_v\)，\(SG_u = \text{mex}\{S_v\}(v \in son_u)\)
这样我们就得到了这个问题的 \(O(n^2)\) 解法，优化就是放到 Trie 树上维护，不过与博弈论无关就不细说了。
[省选联考 2023]过河卒 Luogu P9169
问题描述：
有一个 \(n\) 行 \(m\) 列的棋盘。我们用 \((i,j)\) 表示第 \(i\) 行第 \(j\) 列的位置。棋盘上有一些 障碍，还有一个黑棋子和两个红棋子。
游戏的规则是这样的: 红方先走，黑方后走，双方轮流走棋。红方每次可以选择一个红棋子，向棋盘的相邻一格走一步。具体而言，假设红方选择的这个棋子位置在 \((i,j)\)，那么它可以走到 \((i-1,j),(i+1,j),(i,j-1),(i,j+1)\) 中的一个，只要这个目的地在棋盘内且没有障碍且没有红方的另一个棋子。
黑方每次可以将自己的棋子向三个方向之一移动一格。具体地，假设这个黑棋子位置在 \((i,j)\)，那么它可以走到 \((i-1,j),(i,j-1),(i,j+1)\) 这三个格子中的一个，只要这个目的地在棋盘内且没有障碍。
在一方行动之前，如果发生以下情况之一，则立即结束游戏，按照如下的规则判断胜负（列在前面的优先）：
-
黑棋子位于第一行。此时黑方胜。
-
黑棋子和其中一个红棋子在同一个位置上。此时进行上一步移动的玩家胜。
-
当前玩家不能进行任何合法操作。此时对方胜。
现在假设双方采用最优策略，不会进行不利于自己的移动。也就是说:
- 若存在必胜策略，则会选择所有必胜策略中，不论对方如何操作，本方后续获胜所需步数最大值最少的操作。
- 若不存在必胜策略，但存在不论对方如何行动，自己都不会落败的策略，则会选择任意一种不败策略。
- 若不存在不败策略，则会选择在所有策略中，不论对方如何操作，对方后续获胜所需步数最小值最大的操作。
如果在 \(100^{100^{100}}\) 个回合之后仍不能分出胜负，则认为游戏平局。请求出游戏结束时双方一共移动了多少步，或者判断游戏平局。
对于所有的数据，保证：\(1 \leq T \leq 10 ; 2 \leq n \leq 10 ; 1 \leq m \leq 10 ; \text{id}\) 等于测试点编号。
问题分析：
感觉解决这个题的关键是不要害怕这个题，正常分析性质就好。
一眼我们就能发现 \(n,m\) 超级小，所以我们可以直接 \(dp\) 表示博弈的状态，并且能直接将三个棋子的位置全部存下。
那么我们的 \(dp\) 过程其实就是拓扑排序 + 博弈论的一个过程。
这里用到的博弈论知识就是：必胜态后继一定存在必败态，必败态后继一定都是必胜态。
根据这个知识我们就能把博弈的状态表示好了，但是代码真的有点难写。
[SDOI2019]移动金币 Luogu P5363
问题描述：
Alice和Bob将要进行如下的一场游戏。二人轮流操作，且Alice先行。
当轮到一个玩家的时候，他可以选择一枚金币，并将其向左移动任意多格，且至少移动一格。
金币不能被移出棋盘，也不能越过其它金币。
一个 \(1\times n\) 的棋盘上最初摆放有 \(m\) 枚金币。其中每一枚金币占据了一个独立的格子，任意一个格子内最多只有一枚金币。
如果轮到一个玩家的时候他已经无法做出任何有效操作了（显然这个时候\(m\)枚金币恰好落在最左侧的\(m\)个格子中），则被判定为输家。已经知道Alice和Bob都是极致聪明的人，他们在任何局面下总能做出最优的操作。那么有多少初始状态能保证Alice必胜呢？
\(1\le n\le 150000\)且\(1\le m\le 50\)。
问题分析：
考虑我们一次移动其实相当于将它与其前面的棋子的空格移动到了它与其后面棋子的空格位置，那么我们如果将棋子间的距离视为石子数量，这个问题就相当于一个阶梯 Nim 游戏。
阶梯 Nim 的结论就是如果奇数位置的石子的异或和不为 \(0\) 则先手必败，但是不为 \(0\) 显然不如为 \(0\) 好限制，所以 \(dp\) 出为 \(0\) 的方案数最后用总数减一下就好了。
总数就是一个简单的组合数。