博弈论

一.部分定义

1. 状态：到某一时刻为止，所有可能与状态有关的信息。
2. 局面：到某一时刻为止，双方玩家面对的局势。
3. 游戏：博弈图上的一个节点，通常用局面代替。
4. 博弈图：每个状态向下一个状态连边形成的有向图（可证明无环）。
5. 游戏的和：即许多游戏拼到一起，例如Nim游戏就是许多单堆Nim游戏的和。
6. 游戏的等价关系：如果对于所有游戏 $H$ ，游戏 $G_1+H$ 与 $G_2+H$ 都为必胜状态以及必败状态，那么称游戏 $G_1$ 和 $G_2$ 等价，记作 $G_1 \approx G_2$ 。

二.Nim游戏

1. 没有后继状态的状态是必败状态：先手选不了了，所以显然是必败。
2. 一个状态是必胜状态当且仅当后继状态中存在必败状态：这样的话，先手可以转到那个状态，后手就必败了。
3. 一个状态是必败状态等价于其后继状态都是必胜状态：转过去后后手变成先手，必胜，所以现在的先手必败。

三.Nim和

1. 如果 $a_i=0$ 对所有的 $i=1,2...n$ 都成立，那么该状态为必败状态，且Nim和为0,符合条件。
2. 如果当前 $S=0$，那么先手无论如何都会破坏这个状态；
3. 如果接上一步，那么后手一定有办法使其重新变成 $0$。具体方法：找到先手选完后 $S$ 的二进制表示中第一个非零的位置，可以证明目前的每个石子堆中石子个数的二进制表示中一定至少有一个这一位也是 $1$ ，那么，我们就可以把这个 $1$ 变成 $0$ ，然后其后面的位置随便放 $0$ 或 $1$ ，这样改变后的石子个数不会超过原先的，后面 $0$ 与 $1$ 的重新排列也可以使异或和重新变为 $0$ 。

四.SG函数

1. 终止状态的 $SG$ 值为 $0$ 。
2. 状态 $s$ 的 $SG$ 值为后继状态中的 $SG$ 值中的 $mex$ 。
3. 对于 $k$ 个独立的游戏而言，它们整体的 $SG$ 值为每个游戏 $SG$ 值的异或和。
4. $SG$ 定理：$SG$ 值为 $0$ 时先手必败，否则先手必胜。