ICG、Nim游戏、Bouton定理和SG函数

一、 ICG

ICG（Impartial Combinatorial Games），即公平的组合游戏，其定义如下：

两名选手。
两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个。
游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。

在ICG游戏中，先手不是必胜就是必败。证明过程：

双方互相决策，有限步骤，可以用树来描述，树的每个叶子节点表示对先手而言是必胜或者必败。

则对于树上的每个节点：

当这个节点轮到先手行动时，若其存在子节点对先手而言必胜，则当前节点对先手而言必胜，否则当前节点对先手而言必败。
当这个节点轮到后手行动时，若其存在子节点对先手而言必败，则当前节点对先手而言必败，否则当前节点对先手而言必胜。

按照上述过程，可以从决策树的叶子节点开始向根节点向上推出决策树上每个节点对于先手而言必胜还是必败，故先手不是必胜就是必败。

二、 Nim游戏

Nim游戏是ICG的一种，通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

三、 Bouton定理

假设Nim游戏的石子有 $n$ 堆，第 $i$ 堆的石子个数我们用 $a_i$ 表示，则我们可以使用 $(a_1, a_2, …, a_n)$ 表示一个Nim游戏的局面。对于 $(a_1, a_2, …, a_n)$ 的Nim游戏局面，当且仅当 $a_1 \wedge a_2 \wedge ... \wedge a_n \neq 0$ 时（其中 $\wedge$ 是按位异或运算），先手必胜。

证明：

对于 $a_1 \wedge a_2 \wedge ... \wedge a_n \neq 0$ 的Nim游戏局面 $(a_1, a_2, …, a_n)$ ，我们设 $a_1 \wedge a_2 \wedge ... \wedge a_n = k$ 。则必存在 $a_i$ ，其二进制表示在 $k$ 的最高位上为1（异或运算的性质），且有 $a_i \wedge k < a_i$ 。则对于当前局面下的先手可以通过合法的移动将第 $i$ 堆石子取到只剩 $a_i \wedge k$ 个，那么此时游戏局面变为 $(a_1, a_2, ..., a_{i-1}, a_i \wedge k, a_{i+1}, ..., a_n)$ ，而 $a_1 \wedge a_2 \wedge ... \wedge a_{i-1} \wedge (a_i \wedge k) \wedge a_{i+1} \wedge ... \wedge a_n = k \wedge k = 0$ 。用一句话来讲，就是异或和不为0的局面一定存在合法移动可以变为异或和为0的局面。
对于 $a_1 \wedge a_2 \wedge ... \wedge a_n = 0$ 的Nim游戏局面 $(a_1, a_2, …, a_n)$ ，假设我们将第 $i$ 堆石子由 $a_i$ 个取到 $a_i'$ 个，则有 $a_i \neq a_i'$ ，则必有 $a_1 \wedge a_2 \wedge ...\wedge a_{i-1} \wedge a_i' \wedge a_{i+1} \wedge ... \wedge a_n \neq 0$ （可用反证法证明）。用一句话来讲，就是异或和为0的局面无论怎样合法地进行移动，都将转变为异或和不为0的局面。
对于局面 $(0, 0, ..., 0)$ ，其异或和为0，对于先手而言是必输的局面。
对于任何异或和不为0的局面，先手只需要按照策略将其转变为异或和为0的局面，就能保证后手永远只能拿到异或和为0的局面。又因为每一次合法的移动都将导致石子个数减少，故总的移动步数是有限的，最终后手将拿到 $(0, 0, ..., 0)$ 的局面而无石子可拿，故后手必输，先手必胜。反过来即可证，对于任何异或和为0的局面，先手必输。

四、 SG函数

通过SG函数，每个ICG都可以转换成Nim游戏。

SG函数的定义域为ICG的决策树上的所有节点，其具体定义为： $SG(x) = mex\{SG(y) | y是x的子节点\}$ ，其中 $mex$ （minimal excludant）是施加于集合的运算，表示最小的不属于这个集合的非负整数，比如 $mex\{0, 1, 2, 4 \} = 3$ ， $mex\{1, 2, 3 \} = 0$ ， $mex\{\} = 0$ 。

对于ICG的决策树上的节点 $v$ ，我们可以把它想象成一个只有一堆石子，个数为 $SG(v)$ 的Nim游戏。

对于节点 $v$ 的子节点 $u$ ：

根据SG函数的定义，必有 $SG(v) \neq SG(u)$ 。
若 $SG(v) < SG(u)$ ，则根据SG函数的定义， $u$ 节点必定存在子节点 $w$ 使得 $SG(w) = SG(v)$ 。倘若先手尝试使得局面的SG函数值变大，由局面 $v$ 移动到局面 $u$ ，则后手必定可以将局面由 $u$ 转移到 $w$ ，恢复SG函数值。故先手无有效的手段让局面的SG函数值增大，我们只需要考虑 $SG(v) > SG(u)$ 的情况。
对于全体 $SG(v) > SG(u)$ 的子节点u，其SG函数值将完整覆盖区间 $[0, SG(v)-1]$ 上的所有整数。我们从局面 $v$ 移动到局面 $u$ ，其实相当于在一堆个数为 $SG(v)$ 的石子上取走若干石子，使剩下一堆个数为 $SG(u)$ 的石子。

当ICG中存在 $n$ 个互相不干扰的移动类型时，我们可以将这 $n$ 种移动类型视为 $n$ 堆石子，将该ICG视为 $n$ 堆石子的Nim游戏。运用前面的Bouton定理，该ICG的先手必胜与否的情况可以通过计算每个移动类型下的初始状态的SG函数，并计算这些SG函数值的异或和来得出。

五、例题HDU 1848 Fibonacci again and again

HDU 1848 Fibonacci again and again：

这题就是个ICG，其中在三堆石子上取石子的操作可以分成3种互相不干扰的移动类型，故可将该问题转换为3堆石子的Nim游戏。这三堆石子的初始状态为 $m$ 、 $n$ 、 $p$ ，计算 $SG(m) \wedge SG(n) \wedge SG(p)$ ，若该值不为0则先手必胜，输出“Fibo”，否则先手必败，输出“Nacci”。

参考AC代码：

#include <bits/stdc++.h>
using namespace std;
int f[500] = {1, 2}, mex[1001];
bool used[1001][1001];
int calc_mex(int x) {
    if (mex[x] >= 0) return mex[x];
    if (!x) return mex[x] = 0;
    for (int i=0; f[i]<=x; i++) used[x][calc_mex(x-f[i])] = 1;
    for (int i=0;;i++)
        if (!used[x][i]) return mex[x] = i;
}
int main() {
    for (int i=2;;i++) {
        f[i] = f[i-1] + f[i-2];
        if (f[i] > 1000) break;
    }
    memset(mex, -1, sizeof(mex));
    int m, n, p;
    while (scanf("%d %d %d", &m, &n, &p) && (m || n || p)) {
        int ans = calc_mex(m) ^ calc_mex(n) ^ calc_mex(p);
        printf(ans ? "Fibo\n" : "Nacci\n");
    }
    return 0;
}