博弈论们：
博弈论们：
-
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$$
时，有先手必胜局面。
证明：放在有向图上，剩下基本一样。（懒，咕）
-
-
有向图游戏：
在一个有向图有一枚棋子，两个人轮流操纵棋子沿有向边移动，知道有一方不能移动后游戏结束，并此一方失败。
实际上任意的博弈游戏均能转化成为有向图游戏，具体只要抽象出游戏的每个可能局面