Nim 博弈SG 函数Bash 博弈阶梯 Nim 博弈k-Nim 博弈反 Nim 博弈反 SG 博弈 / SJ 定理反 k-Nim 博弈Every-SG 博弈Chomp 博弈Wythoff 博弈Fibonacci 博弈动态减法博弈Euclidean 博弈翻硬币博弈树上删边博弈无向图删边博弈图上不重复游走博弈二分图博弈
Nim 博弈
有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗。两个人轮流取，每次从一堆取任意多个，但不能不取。无法取的人输掉游戏。
无需多言，先手必胜当且仅当 \(\bigoplus_{i=1}^n a_i \ne 0\)。
SG 函数
对于有向无环图 \(G = (V, E)\) 及其中顶点 \(u \in V\)，有
\[ \mathrm{SG}(u) = \operatorname{mex}\{\mathrm{SG}(v) \mid (u, v) \in E\} \]
\(n\) 个游戏的 Nim 和就是 \(\bigoplus_{i=1}^n \mathrm{SG}(u_i)\)，先手必胜当且仅当这个值不等于 \(0\)。
Bash 博弈
有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗。两个人轮流取，每次从一堆取最多 \(k\) 个，但不能不取。无法取的人输掉游戏。
容易归纳得到 \(\mathrm{SG}(x) = x \bmod (k+1)\)，因此先手必胜当且仅当 \(\bigoplus_{i=1}^n \left(a_i \bmod (k+1)\right) \ne 0\)。
阶梯 Nim 博弈
有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗。两个人轮流取，每次从第 \(i\) \((2 \le i \le n)\) 堆移动任意多个到第 \(i-1\) 堆。无法操作的人输掉游戏。
阶梯博弈等价于在偶数位置的石子堆上的 Nim 博弈。
如果这些石子满足先手必胜，先手总是可以阻止后手操作奇数位置的石子堆。反之，如果先手必败，后手也总是可以阻止先手操作奇数位置。
因此必胜当且仅当 \(\bigoplus_{i=1}^{\lfloor\frac n2\rfloor} a_{2i} \ne 0\)。
k-Nim 博弈
有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗。两个人轮流取，每次从不超过 \(k\) 堆取任意多个，但不能不取。无法取的人输掉游戏。
先手必胜当且仅当存在 \(j \in \mathbb N\)，在二进制下第 \(j\) 位为 \(1\) 的 \(a_i\) 个数不是 \(k+1\) 的倍数。
反 Nim 博弈
有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗。两个人轮流取，每次从一堆取任意多个，但不能不取。无法取的人赢得游戏。
不妨加一个超级石子在最后，这样还是变成公平组合游戏。
当所有 \(a_i \le 1\) 时，先手必胜当且仅当 \(2 \mid \sum_{i=1}^n a_i\)。否则，先手必胜当且仅当 \(\bigoplus_{i=1}^n a_i \ne 0\)。
反 SG 博弈 / SJ 定理
简单地说就是反 Nim 博弈可以套用到任意博弈的 Nim 和的反博弈上。
反 k-Nim 博弈
有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 颗。两个人轮流取，每次从不超过 \(k\) 堆取任意多个，但不能不取。无法取的人赢得游戏。
当所有 \(a_i \le 1\) 时，先手必胜当且仅当 \(\sum_{i=1}^n \bmod (k+1) \ne 1\)。否则，先手必胜当且仅当存在 \(j \in \mathbb N\)，在二进制下第 \(j\) 位为 \(1\) 的 \(a_i\) 个数不是 \(k+1\) 的倍数。
Every-SG 博弈
有 \(n\) 个公平组合游戏，两个人轮流操作，每次要在每个未结束的游戏里操作一步。无法操作的人输掉游戏。
在确定各个状态的胜负态之后再计算一个最大时长。当然，输家希望最小化。
具体而言，有
\[
step(u) = \begin{cases}
0, & \nexists (u, v) \in E \\
1+\max\{step(v) \mid (u, v) \in E, \mathrm{SG}(v)=0\}, & \mathrm{SG}(u) \ne 0 \\
1+\min\{step(v) \mid (u, v) \in E, \mathrm{SG}(v)\ne0\}, & \mathrm{SG}(u) = 0 \\
\end{cases}
\]
先手必胜当且仅当 \(2 \nmid \max_{i=1}^n step(a_i)\)。
Chomp 博弈
有 \(n \times m\) 的棋盘，每次可以选择一个格子 \((x, y)\) 并删除所有 \((x', y')\) \((x' \ge x, y' \ge y)\) 的格子，取到 \((1, 1)\) 的人输。
先手必胜当且仅当 \(\max(n, m) > 1\)。
Wythoff 博弈
有两堆石子，分别有 \(a, b\) 个石子，两个人轮流取石子，每次可以： - 从任意一堆石子里取走任意多石子，但不能不取。 - 从两堆石子里同时取走相同数目的石子，但不能不取。
结论：不妨设 \(a \le b\)，则先手必胜当且仅当不存在 \(k \in \mathbb N^+\) 使得
\[
\begin{cases}
a = \left\lfloor\frac{k(1+\sqrt 5)}2\right\rfloor \\
b = a + k
\end{cases}
\]
Fibonacci 博弈
有 \(n\) \((n \ge 2)\) 颗石子，两个人轮流取石子。先手第一轮不能把石子取完。第二轮开始，每一轮取的石子个数至多为对手上一次取的石子个数的两倍。任意时刻不能不取。无法取的人输掉游戏。
经过一大堆基于 Zeckendorf 定理的推导后，先手必胜当且仅当 \(n\) 不是 Fibonacci 数。
动态减法博弈
有 \(n\) \((n \ge 2)\) 颗石子，两个人轮流取石子。先手第一轮不能把石子取完。第二轮开始，每一轮取的石子个数至多为对手上一次取的石子个数的 \(k\) 倍。任意时刻不能不取。无法取的人输掉游戏。
构造递增序列，使得任何数都能唯一分解为其中某些数的和，且相邻之比 \(> k\)。
设该序列为 \(\{a_i\}\)，\(b_i\) 为 \(a_1, a_2, \dots, a_i\) 能表示的数的最大值。
首先有 \(a_1 = b_1 = 1\)，然后 \(a_i = b_{i-1} + 1\)，\(b_i = a_i + \max\{b_j \mid ka_j < a_i\}\)。
先手必胜当且仅当 \(n\) 在序列 \(\{a_i\}\) 中。
如果把 \(k\) 倍换成其他单调不降的函数，仍然可以采用以上方法。
Euclidean 博弈
有 \(a, b\) 两个数字，两人轮流操作，每次可以用较大的数减去较小的数的倍数（但不能减到 \(< 0\)），若某个时刻较小的数为 \(0\) 则当前操作者输掉游戏。
不妨设 \(b \ge a\)，令 \(b = ka+r\)。
若 \(r=0\)，先手必胜。
若 \(k=1, r>0\)，递归处理。
若 \(k>1, r>0\)，根据 \((a, r)\) 的胜负情况，先手总是必胜。
翻硬币博弈
\(n\) 枚硬币排成一排，有的正面朝上，有的反面朝上。两个人轮流根据某个规则翻硬币，但规则保证翻的硬币中最右边的必须是从正面翻到反面，无法操作者输掉游戏。
等价于每个正面朝上的硬币单独存在时的博弈的 Nim 和。
树上删边博弈
给定一棵有根树，两人轮流操作，每次可以移除一棵子树，无法操作者输掉游戏。
叶子结点的 SG 值为 \(0\)，非叶结点的 SG 值为所有儿子的 SG 值加一的异或和。
无向图删边博弈
给定一张有根无向图，两人轮流操作，每次可以移除一条边和不与根连通的部分，无法操作者输掉游戏。
Fusion Principle：将偶环缩成点，奇环缩成一个点挂一条边，这个点继承原来环上的所有边，SG 函数值不变。
图上不重复游走博弈
给定一张无向图，先手选定一个点，然后两人轮流移动到从未到过的点上，无法移动者输掉游戏。
先手必败当且仅当存在完美匹配。
二分图博弈
给定一张二分图和一个起始点 \(s\)，然后两人轮流移动到从未到过的点上，无法移动者输掉游戏。
先手必胜当且仅当 \(s\) 是最大匹配必经点。