博弈论们：

• Nim 博弈：

  先手，后手：第一个，第二个行动者。

  必胜，必败：指先手必胜或必败。

  定理：Nim 博弈先手必胜，当且仅当：$$\bigoplus_{i=1}^nA_i\ne 0$$
  证明：反证法假设 \(A_i'=A_i\) 得出矛盾。（懒，咕了，有机会再说）

• SG 函数

  • mex 运算：

    对于一个非空数集: \(S\)
    我们将 $$mex{S}$$ 定义为不属于数集的最小非负整数，如 \(mex\{0,1,3\}\) 为 \(2\) 。

  • SG 函数：

    对于每种可能状态的后继状态 \(y_i\)，我们将当前状态 \(x\) 的 SG 函数定义为：$$SG(x)=mex{SG(y_1),SG(y_2)......SG(y_n)}$$

  • SG 定理：

    只有当：$$\bigoplus{SG_i}\ne 0$$
    时，有先手必胜局面。
    证明：放在有向图上，剩下基本一样。（懒，咕）

• 有向图游戏：

  在一个有向图有一枚棋子，两个人轮流操纵棋子沿有向边移动，知道有一方不能移动后游戏结束，并此一方失败。

  实际上任意的博弈游戏均能转化成为有向图游戏，具体只要抽象出游戏的每个可能局面