- 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\) 是最大匹配必经点。