有向图游戏

两个人在一个 DAG 上玩一个游戏，DAG 只有一个出发点。在这个出发点上有一个棋子，两人轮流操作，每次可以将棋子推向其的一个儿子，无法操作的玩家判负。

\(SG\) 函数

每个节点都有唯一对应的一个 \(SG\) 值与之对应。\(SG\) 函数定义如下：

• 没有出度的节点（判负），\(SG_u=0\)；
• 对于其他节点，\(SG_u=\text{mex}_{v\in to[u]}\{SG_{v}\}\)

由定义我们得到一个重要的性质：

性质：对于任意节点 \(u\)，对于每个 \(sg\in[0,SG_u)\cap \Z\)，\(u\) 节点至少能直接到达一个节点 \(v\) 满足 \(SG_v=sg\)；\(SG\) 值为 \(0\) 的节点只能到达 \(SG\) 非零的节点。

\(SG\) 定理：当且仅当出发点的 \(SG\) 值非零，此游戏是先手必胜的。

证明

考虑数学归纳法。

首先，到达一个 \(SG\) 值更大的节点是无效的。因为对手可以立即返回一个 \(SG\) 值和原先相等的节点。

接着，对于最终的必败状态，\(SG=0\)；

当处于一个 \(SG\ne 0\) 的节点时，我们可以走到一个 \(SG=0\) 的子节点，使对手处于一个必败状态；对手所处的 \(SG=0\) 的节点只能走到 \(SG\ne 0\) 的必胜状态的节点，使我方总处于必胜状态。

组合游戏

有 \(n\) 个有向图游戏，每次玩家可以选择在任意一个 DAG 上移动一步，无法移动的判负。

定理：由 \(n\) 个有向图游戏组成的组合游戏，当且仅当

\[ \bigoplus_{i=1}^{n} SG(begin_i)\ne 0 \]

时，此游戏先手必胜。且此异或和可看作是整个游戏初始状态的 SG 值。

证明类似 Nim 游戏，每个有向图游戏的 \(SG\) 值可以改变为小于它的任何一个值，和 Nim 的规则相同。