公平组合游戏

公平组合游戏（ICG）的定义如下：

• 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；

• 任意一个游戏者在某一确定局面可以作出的决策集合只与当前的局面有关，而与游戏者无关；

• 游戏中的同一个局面不可能多次抵达（DAG），游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

Nim 游戏

有 $n$ 堆石子，每堆石子的数量都是有限的，玩家可以选择一堆石子并拿走若干颗（不能不拿），若某一方无法操作判负。

现有 Alice 和 Bob 两个人参与游戏，Alice 先手，若两人都采取最优策略，问谁最后必胜。

定义游戏中可能的局面为 position，我们将 position 分为两类：

1. P-position：在当前的局面下，先手必败。
2. N-position：在当前的局面下，先手必胜。

下文将 P-position 和 N-position 简称为 P 和 N。

通过推导可以得到下面三条性质：

1. 合法操作集合为空的局面是 P；
2. 可以移动到 P 的局面是 N；
3. 所有移动都只能到 N 的局面是 P。

在这个游戏中，我们已知 $\forall i\in[1,n], a_i = 0$ 的局面是 P 局面，那么我们可以通过反向枚举推导出所有可能的局面，总状态数为 $\prod_{i=1}^n a_i$，时间复杂度过高。

对于 Nim 游戏我们有如下结论：

对于一个局面，当且仅当 $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$ 时，该局面为 P 局面。

对于这个结论的证明如下：

1. 全 $0$ 状态为P局面，即 $a_i=0$，则 $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$。
2. 从任意一个 $a_1 \oplus a_2 \oplus \dots \oplus a_N = k \neq 0$ 的状态可以移动到 $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$ 的状态。
   由于 $\textit{xor}$ 计算的特殊性，我们知道一定有一个 $a_i$ 最高位与 $k$ 最高位的 $1$ 是相同的，那么必然有 $a_i \oplus k < a_i$ 的，
   所以我们可以通过改变 $a_i$ 的值为 $a_i'$，使得

$$a_1 \oplus a_2 \oplus \dots \oplus a_i' \oplus \dots \oplus a_N = 0.$$

3. 对于任意一个局面，若 $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$，则不存在任何一个移动可以使得新的局面 $a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$。
   由于 $\textit{xor}$ 计算的特殊性，我们可以知道，一定是存在偶数个 1 时该位置的 1 才会被消除。若只改变一个 $a_i$，无论如何都会使得 1 的数量发生变化，从而导致 $a_1 \oplus a_2 \oplus \dots \oplus a_n \neq 0$。

以上三条满足 ICG 游戏中 N，P 局面的转移性质，所以该结论的正确性也得到了证明。

若规定一轮最多选 $k$ 个，则将 $a_i$ 都 $\bmod \ m$ 便可以规约到普通的 Nim 游戏。

显然，在每一堆都小于 $m$ 个之前，若某人在若干操作中选择了少于 $m$ 个，设这些操作一共取走了 $s$ 个，则这些操作都可以视为若干次全选 $m$ 的操作，最后 $s \bmod m$ 个放回去。

在每一堆都小于 $m$ 个后，就是普通的 Nim 游戏。

巴什博弈（Bash Game）

只有一堆 $n$ 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 $m$ 个。最后取光者得胜。

显然，如果 $n=m+1$，那么由于一次最多只能取 $m$ 个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。

容易发现若先手总是给对手留下 $(m+1)\times k$ 个，则先手必胜。

如果 $n=(m+1) \times k+r$，($k$ 为任意自然数，$r \leq m$)，那么先取者要拿走 $r$ 个物品，如果后取者拿走 $s \leq m$ 个，那么先取者再拿走 $m+1-s$ 个，就可以令结果剩下 $(m+1)(r-1)$ 个。

也就是说，如果初始状态有 $n \bmod (m+1)=0$，那么先手必败，否则必胜。

Lasker’s Nim 游戏

每一轮允许下面两种操作中之一：

• 从一堆石子中取走任意多个；
• 将一堆数量不少于 2 的石子分成都不为空的两堆。

容易得出：

1. $\operatorname{SG}(0) = 0$，$\operatorname{SG}(1) = 1$。
2. 状态 $2$ 的后继有：$0, 1, (1, 1)$，他们的 SG 值分别为 $0,1,0$，所以 $\operatorname{SG}(2) = 2$。
3. 状态 $3$ 的后继有：$0, 1, 2, (1, 2)$，他们的 SG 值分别为 $0,1,2,3$，所以 $\operatorname{SG}(3) = 4$。
4. 状态 $4$ 的后继有：$0, 1, 2, 3, (1,3), (2,2)$，他们的 SG 值分别为 $0,1,2,4,5,0$，所以 $\operatorname{SG}(4) = 3$。

可以发现。

$$\operatorname{SG}(4k)=4k-1 \\ \operatorname{SG}(4k+1)=4k+1 \\ \operatorname{SG}(4k+2)=4k+2 \\ \operatorname{SG}(4k+3)=4k+4 \\$$

通过这个 SG 函数的应用可以看出分析后继状态的重要性。

练习题目：HDU 3032 Nim or not Nim?

Sprague-Grundy 函数

任何一个 ICG 都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成一个“有向图游戏”。

首先定义 $\operatorname{mex}$ 运算，这是一个对集合的运算，表示最小的不属于这个集合的非负整数。

对于一个给定的有向无环图，定义关于图的每个顶点的 SG 函数 $g$ 如下：

$$\operatorname{SG}(x)=\operatorname{mex}\{ \operatorname{SG}(y) \mid \textit{y is x's successor.} \}$$

例如：取石子问题，有 $1$ 堆 $n$ 个的石子，每次只能取 $\{1,3,4\}$ 个石子，先取完石子者胜利，那么各个数的 SG 值为多少？

0. $\operatorname{SG}(0)=0$，$f=\{1,3,4\}$；
1. $x=1$ 时，可以取走 $1-f\{1\}$ 个石子，剩余 $\{0\}$ 个，$\operatorname{mex}\{\operatorname{SG}(0)\}=\{0\}$，故 $\operatorname{SG}(1)=1$；
2. $x=2$ 时，可以取走 $2-f\{1\}$ 个石子，剩余 $\{1\}$ 个，$\operatorname{mex}\{\operatorname{SG}(1)\}=\{1\}$，故 $\operatorname{SG}(2)=0$；
3. $x=3$ 时，可以取走 $3-f\{1,3\}$ 个石子，剩余 $\{2,0\}$ 个，$\operatorname{mex}\{\operatorname{SG}(2),\operatorname{SG}(0)\}=\{0,0\}$，故 $\operatorname{SG}(3)=1$；
4. $x=4$ 时，可以取走 $4-f\{1,3,4\}$ 个石子，剩余 $\{3,1,0\}$ 个，$\operatorname{mex}\{\operatorname{SG}(3),\operatorname{SG}(1),\operatorname{SG}(0)\}=\{1,1,0\}$，故 $\operatorname{SG}(4)=2$；
5. $x=5$ 时，可以取走 $5-f\{1,3,4\}$ 个石子，剩余 $\{4,2,1\}$ 个，$\operatorname{mex}\{\operatorname{SG}(4),\operatorname{SG}(2),\operatorname{SG}(1)\}=\{2,0,1\}$，故 $\operatorname{SG}(5)=3$。

以此类推，得到：

x       0  1  2  3  4  5  6  7  8 ....
SG(x)   0  1  0  1  2  3  2  0  1 ....

从上述计算过程，我们不难看出，SG 函数实际上代表的一个状态值。如果值为 $0$，表示当前已经是 P 局面，否则表示可以到达哪些 P 局面（即当前状态为 N 局面）。在前面对 Nim 游戏的分析中，我们知道，N 局面可以一步到达 P 局面，而 P 局面当前选手必输。

进一步考虑 SG 函数与 Nim 博弈。当 $g(x)=k$ 时，表明对于任意一个 $0 \le i<k$，都存在 $x$ 的一个后继 $y$ 满足 $g(y)=i$。也就是说，当某枚棋子的 SG 值是 $k$ 时，我们可以把它变成 $0\sim k-1$，但绝对不能保持 $k$ 不变。这与 Nim 游戏类似。

这也表明，如果将 $n$ 枚棋子所在的点的 SG 值看作 $n$ 堆相应数量的石子，那么这个 Nim 游戏的每个必胜策略都对应于原来这 $n$ 枚棋子的必胜策略！

这也与以下结论（SG 定理，Sprague-Grundy Theorem）相对应：

$\operatorname{SG}(G)=\operatorname{SG}(G_1) \oplus \operatorname{SG}(G_2) \oplus \dots \oplus \operatorname{SG}(G_n)$

也就是说，游戏的和的 $SG$ 函数值是它的所有子游戏的 $SG$ 函数值的异或。

当 $\operatorname{SG}(G)$ 为 $0$ 时，先手必输，否则先手必胜。

[SDSC2024 综合模拟 Day6 T1] Game

在一个 $n \times n$ 的棋盘上， $(i, j)$ 表示第 $i$ 行第 $j$ 列的格子。初始时棋盘上有 $m$ 个不同的格子上存在一个棋子。

Alice 和 Bob 轮流进行操作，Alice 先手，每次操作如下:

• 选择棋盘上一个存在棋子 的格子 $(i, j)$ 和任意 $k$ 满足 $1 \leq k \leq \min (i, j)$ ，然后对于以 $(i, j)$ 为右下角，边长为 $k$ 的正方形内的所有格子 $(x, y)$ （即所有满足 $i-k<x \leq i, j-k<y \leq j$ 的格子 $(x, y)$）:
• 如果 $(x, y)$ 原本没有棋子，则在该格子上放上一个棋子；否则移除该格子上的棋子。可以证明，游戏会在有限步数内结束，最后不能操作者失败。

Alice 和 Bob 都很聪明，他们都会采取最优策略行动。

Alice 和 Bob 将要下 $T$ 盘棋，你想知道这几盘棋都谁会贏。

子问题显然是一个棋子被去除。

定义 $(i,j)$ 棋子被移除的 SG 值为 $\operatorname{SG}(i,j)$

由 SG 定理，总问题 SG 值=子问题 SG 值的异或和。

打表 $\operatorname{SG}(i,j)$ 可以发现 $\operatorname{SG}(i,j)=min(lowbit(i),lowbit(j))$

打表代码：

const int N = 10, M = 100010;

int n = 4, m = 4, sg[M];
bool g[N][N];

int dfs(int u, int cnt) {
    if (!cnt) return sg[0] = 0;
    int st = 0, p = 0;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            st |= g[i][j] << p, p ++ ;
        }
    }
    if (~sg[st]) return sg[st];
    int mx = 0;
    unordered_map<int, bool> vis;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            if (!g[i][j]) continue;
            int up = min(i, j);
            for (int l = 1; l <= up; l ++ ) {
                for (int x = i - l + 1; x <= i; x ++ ) {
                    for (int y = j - l + 1; y <= j; y ++ ) {
                        g[x][y] ^= 1;
                        if (!g[x][y]) cnt -- ;
                        else cnt ++ ;
                    }
                }
                int suc = dfs(u + 1, cnt);
                vis[suc] = true, mx = max(mx, suc);
                for (int x = i - l + 1; x <= i; x ++ ) {
                    for (int y = j - l + 1; y <= j; y ++ ) {
                        g[x][y] ^= 1;
                        if (!g[x][y]) cnt --  ;
                        else cnt ++ ;
                    }
                }
            }
        }
    }
    for (int i = 0; i <= mx + 1; i ++ ) {
        if (!vis[i]) {
            sg[st] = i;
            break;
        }
    }
    return sg[st];
}

int main() {
    memset(sg, -1, sizeof sg);
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            g[i][j] = true;
            dfs(1, 1);
            printf("%d ", sg[1 << ((i - 1) * m + j - 1)]);
            g[i][j] = false;
        }
        puts("");
    }
    return 0;
}