Bash博弈

一堆石子，总共n个，两个人轮流取，每次取[1,m]个，不能操作的人输。

剩余石子为[1,m]时，显然是先手必胜，必胜策略是全取。
剩余石子为m+1时，是先手必败，无论第一步如何操作第二步都可以全取。
那么从[m+1+1,m+1+m]都是先手必胜，因为可以一步取到先手必败态。
故剩余石子为k(m+1)时，先手都是必败的，因为无论第一步先手取什么，后手都可以保持石子数为m+1的倍数。

总结：先手必胜当且仅当n不是m+1的倍数。

Nim博弈

有n堆石子，分别是a1,a2,...an个，每次从一堆石子取任意正数个，不能操作的人输。

异或和为0时，先手必败，其余情况先手必胜。
若异或和为x，且x不为0，设x的二进制最高位为第k位，那么至少存在1堆石子ai其数量的第k位为1，易知ai xor x < ai，故可以从这堆石子中转移到异或为0的状态。
反之，假如当前异或和为0，那么无论怎么取，下一步异或和必定是非0值。
所以当异或和为0时，无论先手做什么，后手都能维持异或和为0的状态转移回来，直到胜利。反之先手可以把局面变成异或和为0的状态转移给后手。

公平组合游戏：
双方均直到场上的所有信息，双方每一步能做的事情和当前轮是谁无关，同一局面不可多次到达，有限步内会结束，没有平局，无法行动的人输。多个公平组合游戏合起来也是一个公平组合游戏。

把公平组合游戏的每个状态看作节点，合法的决策是转移边，那么一个公平组合游戏就是一个DAG，出边为0的点（无法移动的点）是必败点，由于这是一个DAG所以可以通过DP求出所有的状态的胜负性。然后可以规定出SG函数：一个点的SG函数值为其后继点的SG值的集合的mex。

显然的结论：必败点的SG值为0，经过一次转移之后SG值必定改变，SG值不为0的点都是必胜点，因为其后继状态一定有一个是SG值为0的点。

不知道怎么证明的SG定理：若干个公平组合游戏的SG值，是他们一个一个的SG值的异或和。

使用SG定理解决的思路：观察哪个是一个单独的最小的公平组合游戏，对这个游戏进行打表，然后强行看出SG函数的规律。

Nim-k 博弈

有n堆石子，分别是a1,a2,...an个，每次从[1,k]堆石子取任意正数个，不能操作的人输。（Nim游戏是k=1的特殊形式）

当且仅当任意的k都有 \(k+1|\frac{\sum_{i=1}^n (2^k&a_i)}{2^k}\) 时先手必败，其余情况先手必胜。

Wythoff 博弈

二分图博弈

起点有一颗棋子，转移图是一个二分图，当起点在所有二分图的最大匹配中时，先手必胜。否则先手必败。