有向图游戏是一个经典的博弈游戏——实际上，大部分的公平组合游戏都可以转换为有向图游戏。

在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。

定义 $\operatorname{mex}$ 函数的值为不属于集合 S 中的最小非负整数，即：

$\operatorname{mex}(S)=\min\{x\} \quad (x \notin S, x \in N)$ 例如 $\operatorname{mex}(\{0, 2, 4\})=1$，$\operatorname{mex}(\{1, 2\})=0$。

对于状态 x 和它的所有 k 个后继状态 $y_1, y_2, \ldots, y_k$，定义 $\operatorname{SG}$ 函数：

$\operatorname{SG}(x)=\operatorname{mex}\{\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k)\}$ 而对于由 n 个有向图游戏组成的组合游戏，设它们的起点分别为 $s_1, s_2, \ldots, s_n$，则有定理：当且仅当 $\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n) \neq 0$ 时，这个游戏是先手必胜的。同时，这是这一个组合游戏的游戏状态 x 的 SG 值。

这一定理被称作 Sprague–Grundy 定理(Sprague–Grundy Theorem), 简称 SG 定理。

必败态可达态全为必胜态

必胜态可达态包含必败态

nim游戏

$n$ 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。

取走最后一个物品的人获胜。

如果现在有 n=3 堆物品，而每堆分别有 2, 5, 4 个。转化为有向图游戏

graph TD

2z((2)) --> 1z((1)) & 0z((0))
1z --> 0z

4y[4] --> 3y[3] & 2y[2] & 1y[1] & 0y[0]
3y --> 2y & 1y & 0y
2y --> 1y & 0y
1y --> 0y

5x[5] --> 4x[4] & 3x[3] & 2x[2] & 1x[1] & 0x[0]
4x --> 3x & 2x & 1x & 0x
3x --> 2x & 1x & 0x
2x --> 1x & 0x
1x --> 0x

$0$为必败态$SG(0)=0$

$SG(1) = MEX\{SG(0)\} = 1$

$SG(2) = MEX\{SG(0), SG(1)\} = 2$

$SG(3) = MEX\{SG(0), SG(1), SG(2)\} = 3$

$SG(4) = MEX\{SG(0), SG(1), SG(2), SG(3)\} = 4$

$SG(5) = MEX\{SG(0), SG(1), SG(2), SG(3), SG(4)\} = 5$