- Nim 博弈
- SG 函数
- Bash 博弈
- 阶梯 Nim 博弈
- k-Nim 博弈
- 反 Nim 博弈
- 反 SG 博弈 / SJ 定理
- 反 k-Nim 博弈
- Every-SG 博弈
- Chomp 博弈
- Wythoff 博弈
- Fibonacci 博弈
- 动态减法博弈
- Euclidean 博弈
- 翻硬币博弈
- 树上删边博弈
- 无向图删边博弈
- 图上不重复游走博弈
- 二分图博弈
Nim 博弈
有 n 堆石子，第 i 堆石子有 ai 颗。两个人轮流取，每次从一堆取任意多个，但不能不取。无法取的人输掉游戏。
无需多言，先手必胜当且仅当 ⨁ni=1ai≠0。
SG 函数
对于有向无环图 G=(V,E) 及其中顶点 u∈V，有
SG(u)=mex{SG(v)∣(u,v)∈E}
n 个游戏的 Nim 和就是 ⨁ni=1SG(ui)，先手必胜当且仅当这个值不等于 0。
Bash 博弈
有 n 堆石子，第 i 堆石子有 ai 颗。两个人轮流取，每次从一堆取最多 k 个，但不能不取。无法取的人输掉游戏。
容易归纳得到 SG(x)=xmod(k+1)，因此先手必胜当且仅当 ⨁ni=1(aimod(k+1))≠0。
阶梯 Nim 博弈
有 n 堆石子，第 i 堆石子有 ai 颗。两个人轮流取，每次从第 i (2≤i≤n) 堆移动任意多个到第 i−1 堆。无法操作的人输掉游戏。
阶梯博弈等价于在偶数位置的石子堆上的 Nim 博弈。
如果这些石子满足先手必胜，先手总是可以阻止后手操作奇数位置的石子堆。反之，如果先手必败，后手也总是可以阻止先手操作奇数位置。
因此必胜当且仅当 ⨁⌊n2⌋i=1a2i≠0。
k-Nim 博弈
有 n 堆石子，第 i 堆石子有 ai 颗。两个人轮流取，每次从不超过 k 堆取任意多个，但不能不取。无法取的人输掉游戏。
先手必胜当且仅当存在 j∈N，在二进制下第 j 位为 1 的 ai 个数不是 k+1 的倍数。
反 Nim 博弈
有 n 堆石子，第 i 堆石子有 ai 颗。两个人轮流取，每次从一堆取任意多个，但不能不取。无法取的人赢得游戏。
不妨加一个超级石子在最后，这样还是变成公平组合游戏。
当所有 ai≤1 时，先手必胜当且仅当 2∣∑ni=1ai。否则，先手必胜当且仅当 ⨁ni=1ai≠0。
反 SG 博弈 / SJ 定理
简单地说就是反 Nim 博弈可以套用到任意博弈的 Nim 和的反博弈上。
反 k-Nim 博弈
有 n 堆石子，第 i 堆石子有 ai 颗。两个人轮流取，每次从不超过 k 堆取任意多个，但不能不取。无法取的人赢得游戏。
当所有 ai≤1 时，先手必胜当且仅当 ∑ni=1mod(k+1)≠1。否则，先手必胜当且仅当存在 j∈N，在二进制下第 j 位为 1 的 ai 个数不是 k+1 的倍数。
Every-SG 博弈
有 n 个公平组合游戏，两个人轮流操作，每次要在每个未结束的游戏里操作一步。无法操作的人输掉游戏。
在确定各个状态的胜负态之后再计算一个最大时长。当然，输家希望最小化。
具体而言，有
step(u)={0,∄(u,v)∈E1+max{step(v)∣(u,v)∈E,SG(v)=0},SG(u)≠01+min{step(v)∣(u,v)∈E,SG(v)≠0},SG(u)=0
先手必胜当且仅当 2∤maxni=1step(ai)。
Chomp 博弈
有 n×m 的棋盘，每次可以选择一个格子 (x,y) 并删除所有 (x′,y′) (x′≥x,y′≥y) 的格子，取到 (1,1) 的人输。
先手必胜当且仅当 max(n,m)>1。
Wythoff 博弈
有两堆石子，分别有 a,b 个石子，两个人轮流取石子，每次可以： - 从任意一堆石子里取走任意多石子，但不能不取。 - 从两堆石子里同时取走相同数目的石子，但不能不取。
结论：不妨设 a≤b，则先手必胜当且仅当不存在 k∈N+ 使得
{a=⌊k(1+√5)2⌋b=a+k
Fibonacci 博弈
有 n (n≥2) 颗石子，两个人轮流取石子。先手第一轮不能把石子取完。第二轮开始，每一轮取的石子个数至多为对手上一次取的石子个数的两倍。任意时刻不能不取。无法取的人输掉游戏。
经过一大堆基于 Zeckendorf 定理的推导后，先手必胜当且仅当 n 不是 Fibonacci 数。
动态减法博弈
有 n (n≥2) 颗石子，两个人轮流取石子。先手第一轮不能把石子取完。第二轮开始，每一轮取的石子个数至多为对手上一次取的石子个数的 k 倍。任意时刻不能不取。无法取的人输掉游戏。
构造递增序列，使得任何数都能唯一分解为其中某些数的和，且相邻之比 >k。
设该序列为 {ai}，bi 为 a1,a2,…,ai 能表示的数的最大值。
首先有 a1=b1=1，然后 ai=bi−1+1，bi=ai+max{bj∣kaj<ai}。
先手必胜当且仅当 n 在序列 {ai} 中。
如果把 k 倍换成其他单调不降的函数，仍然可以采用以上方法。
Euclidean 博弈
有 a,b 两个数字，两人轮流操作，每次可以用较大的数减去较小的数的倍数（但不能减到 <0），若某个时刻较小的数为 0 则当前操作者输掉游戏。
不妨设 b≥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 是最大匹配必经点。