公平组合游戏和有向图游戏

公平组合游戏满足：

1. 两名玩家交替行动。
2. 任意时刻可执行的行动与当前玩家是谁无关。
3. 不能行动的玩家输。

有向图游戏就是把博弈中的各个局面变成点，然后对其它局面有转移就连边。公平组合游戏一般都可以转化为有向图游戏。

SG 函数

令 $u$ 出发的 $k$ 条有向边连向 $v_1,v_2,\cdots,v_k$

$$\mathrm{SG}(u)=\mathrm{mex}(\{\mathrm{SG}(v_1),\mathrm{SG}(v_2),\cdots,\mathrm{SG}(v_k)\}) $$

一个有向图游戏的 SG 函数值为它的初始结点 SG 函数值，即 $\mathrm{SG}(G)=\mathrm{SG}(s)$

$m$ 个有向图游戏的 SG 函数和是它们 SG 函数值的异或和，即 $\mathrm{SG}(G)=\mathrm{xor}_{i=1}^m~\mathrm{SG}(G_i)$ 。