讲解
基本概念
局面：游戏过程中面临的状态
先手：整局游戏第一个行动的
后手：整局游戏第二个行动的
必败局面：在某一局面下无论采取什么行动都会输
必胜局面：在某一局面存在某行动能够使对手面临必败局面
公平组合游戏 ICG
1、两名玩家交替行动
2、可执行的合法行动与轮到谁无关
3、不能行动判负
$\text{SG}$ 函数
$\text{Mex}$运算
设$S$表示一个非负整数集合，则
$$
\text{Mex}(S)=\min_{x \in \mathbb{N}, x \notin S} (x)
$$
$\text{SG}$ 函数
$$
\text{SG}(x)=\operatorname{Mex}\limits_{i=1}^k(\text{SG}(y_i))
$$
一个有向图
$$
\text{SG}(G)=\text{SG}(s)
$$
$$
\text{SG}(G)=\text{SG}(G_1) \text{xor} \text{SG}(G_2) \text{xor} … \text{xor} \text{SG}(G_m)
$$
局面必胜：$SG > 0$
局面必败：$SG=0$
