本笔记内容来源于算法基础课

NIM 游戏

给定$N$堆物品，第$i$堆物品有$A_i$个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

先手必胜状态: 可以走到某一个必败状态

先手必败状态: 走不到任何一个必败状态

定理：

NIM博弈先手必胜，当且仅当 $A_1 \wedge A_2 \cdots \wedge A_n \neq 0$

NIM博弈先手必败，当且仅当 $A_1 \wedge A_2 \cdots \wedge A_n = 0$

证明：

存在三种状态：终态，必胜态，必败态

当$0 \wedge 0 \wedge \cdots \wedge 0 = 0$，因为无法拿取，所以此时必败

当$a_1 \wedge a_2 \wedge \cdots \wedge a_n = x \neq 0$时，则可以通过从某一堆中拿出若干个石子，使其变为0

$x$的二进制表示中最高的一位$1$为第$k$位，则$a_1 \sim a_n$中必然存在一个数$a_i$的第$k$位是$1$

$a_i \wedge x < a_i$，即使得最高位变为0，因此拿走$a_i - (a_i \wedge x) \ge 0$

则原式变为

$a_1 \wedge \cdots a_i \wedge x \cdots \wedge a_n = x \wedge x = 0$

当$a_1 \wedge a_2 \wedge \cdots \wedge a_n = 0$，则无论怎么拿，都会使得剩下的石子异或值不为0

反证法：设从$a_i$进行拿取后，使其值为0，则有$a_1 \wedge \cdots \wedge a_i’ \cdots \wedge a_n = 0$

因此$a_i = a_i’$，所以与条件矛盾

公平组合游戏ICG

若一个游戏满足：

1. 由两名玩家交替行动；
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3. 不能行动的玩家判负；

则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设S表示一个非负整数集合。定义$mex(S)$为求出不属于集合S的最小非负整数的运算，即：$mex(S) = min \{x\}$, $x$属于自然数，且$x$不属于$S$

如$mex(\{0,1,2,3\}) = 4$

SG函数

在有向图游戏中，对于每个节点$x$，设从$x$出发共有$k$条有向边，分别到达节点$y_1, y_2, \cdots , y_k$，定义$SG(x)$为$x$的后继节点$y_1, y_2, \cdots , y_k$ 的$SG$函数值构成的集合再执行$mex(S)$运算的结果，即：

$$SG(x) = mex(\{SG(y_1), SG(y_2), \cdots , SG(y_k)\})$$

特别地，整个有向图游戏$G$的$SG$函数值被定义为有向图游戏起点s的SG函数值，即$SG(G) = SG(s)$。

当没有出边时，$SG(x) = mex(\{ \}) = 0$，一个例子如下图所示

定理：

当$SG(G) \neq 0$时必胜，当$SG(G) = 0$时必败

证明：

存在三种状态：

1. 终态：因为无法移动，所以此时必败
2. 非0：则必然可以移动到为0的状态
3. 为0：则无论如何移动都会到达一个非0的状态

有向图游戏的和

设$G_1, G_2, \cdots , G_m$ 是$m$个有向图游戏。定义有向图游戏$G$，它的行动规则是任选某个有向图游戏$G_i$，并在$G_i$上行动一步。$G$被称为有向图游戏$G_1, G_2, \cdots, G_m$的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：

$SG(G) = SG(G_1) \wedge SG(G_2) \wedge \cdots \wedge SG(G_m)$

定理：

有向图游戏的某个局面必胜，当且仅当该局面对应节点的$SG$函数值大于0。

有向图游戏的某个局面必败，当且仅当该局面对应节点的$SG$函数值等于0。

证明：

1. $SG(G_i) = 0$，此时为终态，即任意图都是必败态
2. $SG(G_1) \wedge \cdots \wedge SG(G_n) = x\neq 0$，则一定存在$SG(G_i) = k$变为$0 \sim k - 1 \Rightarrow SG(G_i) \wedge x < SG(G_i)$，从而使其转化为0
3. $SG(G_1) \wedge \cdots \wedge SG(G_n) = 0$，则通过反证法，不存在$SG(G_i)$使得其变为非0，则有$SG(G_i) = SG(G_i’)$，但是$SG(G_i) = k$只能够转化到$0 \sim k-1$

性质：

$SG(G_i \bigcup G_j) = SG(G_i) \wedge SG(G_j)$，即一个局面拆分成了多个局面，则等于各个局面的异或和

代码模板

static int[] f = new int[N];
static void init() {
    // 初始化标记是否计算过
    for (int i = 0; i < n; i++) f[i] = -1;
}
static int SG(int x) {
    if (f[x] != -1) return f[x];
    Set<Integer> set = new HashSet<>(); // 储存所有可达的SG值

    set.add(...) // 插入可达的SG值

    // 返回最小的不包含的自然数
    for (int i = 0; ; i++)
        if (!set.contains(i))
            return f[x] = i;
}