公平组合博弈理论

本文主要讨论 有限、无偏、正常玩法的组合游戏：双方在同一局面拥有相同的合法操作，没有随机与隐藏信息，游戏一定会在有限步内结束，并且无法行动的一方失败。

一、状态图与 P/N 状态

Q0 元问题

给你一个游戏局面，现在轮到我操作，我能否保证获胜？

一个状态的胜负是相对于“当前轮到行动的人”定义的。

• P-position：Previous player winning，当前玩家必败，也可以直接理解为 Lose。
• N-position：Next player winning，当前玩家必胜，也可以直接理解为 Win。

Previous 可以理解为刚刚操作完，把这个状态留给你的玩家获胜，所以是当前必败。

1. 先考虑终止状态，如果一个状态没有任何合法操作，那么当前玩家立即失败，因此终止状态一定是 P 状态。

2. 对于任意非终止状态来说，如果存在一个 P 状态作为后继，那么当前玩家就可以把必败局面交给对方，所以当前状态是 N 必胜态。

3. 反之，如果所有的后继状态都是 N，那么无论怎样操作都会把必胜局面交给对手，当前状态就是 P 必败态。

这就是 P / N 状态的三条基础规则：终止态为 P；P 的所有后继都是 N；每个 N 至少有一个 P 后继。

int dfs( int u ) {
    if( win[u] != -1 ) return win[u];
    for( int v : next_state( u ) ) {
        if( !dfs( v ) ) return win[u] = 1;
    }
    return win[u] = 0;
}

寻找 P 态并证明

Q1 Bash Game

有 $n$ 个物品，两名玩家轮流从中拿去物品，至少拿 $1$ 件，至多拿 $m$ 件，不能不拿，拿走最后一个物品的玩家获胜。

考虑最简单的情况 $m = 2$，我们可以手打一下表，发现：

 n   0 1 2 3 4 5 6 7 8 9
状态  P N N P N N P N N P

很容易发现必败态即 $n \equiv 0 \pmod{3}$，由于必胜策略的核心就是不断把 P 状态交给对手，所以很多博弈中只需要研究必败状态的结构。

在打表猜出一组 P 状态后，一般只需要证明两件事：

1. P 状态不可能一步走到另一个 P 状态。

2. 任意非 P 状态一步都至少能一步走到 P 状态。

对于 $m = 2$ 的情况是显然的，更一般的，我们可以推导出 $m = k$ 时，P 状态是 $n \equiv 0 \pmod{m + 1}$。

当然，这个结论本身并不重要，它只是当前操作规则下 P 状态的具体形式；真正可迁移的是寻找并证明 P 状态集合的方法。

状态图

若是把局面看作一个节点，将一次合法操作看作一条有向边。如果能找到一个每次操作都严格下降的量（剩余石子数，整数大小等），那么沿操作方向就不可能回到原状态，也就构成了一张 DAG。

于是，最基础的公平组合博弈本质上就是 DAG 上的 Bool DP。顺序 DP 和记忆化搜索只是两种不同的计算顺序。

如果状态图中存在真正的环，并且游戏允许无限进行，那么结果可能出现和局，此时就不能直接套用这里的 P/N 二分类和 SG 理论。

二、NIM 游戏与 SG 函数

Q2 Nim Game

假如有若干个互不影响的子游戏，应该怎样合并它们的胜负信息？

标准 Nim 有若干堆石子，每次只能选择一堆并取走任意正数颗，无法操作者失败。

标准 Nim 与 Nim 和

设当前有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 颗。因为一次操作只能改变其中一堆，所以每一堆都可以看成一个独立的子游戏。

定义这些石子堆的 Nim 和 为 $X = a_{1} \oplus a_{2} \oplus \dots \oplus a_{n}$，Nim 定理指出：当 $X = 0$ 时当前局面是 P 态，反之 $X \neq 0$ 时为 N 态。

这个结论可以用前面提到的两条 P 状态证明条件：

1. $X=0$ 的局面无法走到另一个 $X=0$ 的局面。记当前操作为 $a_i\gets b_i$，其中 $a_i\neq b_i$，那么新的 Nim 和满足 $X'=X\oplus a_i\oplus b_i=a_i\oplus b_i\neq0$，因此 P 状态不能一步走到另一个 P 状态。

2. 任意 $X\neq0$ 的局面，都可以一步走到 $X=0$ 的局面。考虑 $X$ 的最高非零位，因为这一位在所有 $a_i$ 中出现了奇数次，所以至少存在一堆 $a_i$ 在这一位为 $1$。令 $b_i=a_i\oplus X$，由于 $X$ 在更高位均为 $0$，所以 $a_i$ 与 $b_i$ 的更高位完全相同，而当前位从 $1$ 变为 $0$，因此 $b_i<a_i$，这是一次合法操作；修改后 $X' = X \oplus a_i \oplus( a_i \oplus X ) = 0$。

所以，异或和为 $0$ 恰好刻画了 Nim 游戏的必败状态。这个证明同时给出了具体的必胜策略：当 $X\neq0$ 时，找到满足 $a_i\oplus X<a_i$ 的一堆，并将它改成 $a_i\oplus X$，就能把一个 P 状态交给对手。

为什么 P/N 不够

既然每一堆都是独立子游戏，能否只用 P/N 描述每个子游戏，然后再组合呢？答案是显然不行的。

例如，单堆 $1$ 和单堆 $3$ 都是 N 态，但：$(1,1)$ 的 Nim 和 $= 0$，整体是 P 态；$(1,3)$ 的 Nim 和 $\neq 0$，整体仍然是 N 态。

因此，不同的 N 态其实并不等价，P/N 只能描述一个游戏单独进行时的胜负，却丢失了它与其他游戏组合时的信息。所以我们需要一个比 P/N 更丰富的值，用来描述一个局面在组合游戏中的类型。

SG 函数

先看一堆大小为 $x$ 的 Nim，它可以一步走到 $0, 1, \dots, x-1$。如果希望它的值恰好为 $x$，那么自然得到 $x = \operatorname{mex}\{0, 1, \dots, x-1\}$，其中 $\operatorname{mex}$ 表示集合中没有出现的最小非负整数。

于是，对于一般的游戏状态 $u$，定义 $SG(u) = \operatorname{mex}\{SG(v)\mid u\to v\}$，这个函数称为 Sprague-Grundy 函数。终止状态没有任何后继，因此其 $SG(u) = \operatorname{mex}\varnothing = 0$。

若 $SG(u)=0$，说明所有后继的 SG 都非零，因此所有后继都是 N，当前状态就是 P；若 $SG(u)>0$，根据 mex 的定义，后继集合中一定出现了 $0$，所以当前至少能一步走到 P，当前状态就是 N。

因此 $SG(u)=0$ 当且仅当 $u$ 是 P 状态，而 $SG(u)\ne0$ 当且仅当 $u$ 是 N 状态。对于大小为 $x$ 的标准 Nim 堆 $SG(x) = \operatorname{mex}\{ 0, 1, \dots, x-1 \} = x$。

笔记

注：这种思想其实类似于状态压缩，把不同的局面压缩成了一个 SG 值。

SG 定理与异或

若两个游戏 $G_1,G_2$ 相互独立，那么 $SG(G_1+G_2)=SG(G_1)\oplus SG(G_2)$。

更一般的，可以扩展到更多游戏，$SG(G_{1} + \dots + G_{n}) = SG(G_{1}) \oplus \dots \oplus SG(G_{n})$。

证明仍然沿用 mex 的两条条件。设 $x=SG(G_1)$、$y=SG(G_2)$，并记 $s=x\oplus y$。

组合游戏的一步操作只会改变一个子游戏。若 $G_1$ 的 SG 从 $x$ 变为 $x'\ne x$，则 $x'\oplus y\ne s$；操作 $G_2$ 时同理，因此任意后继都不能得到 $s$。

任取 $k<s$，观察 $k$ 与 $s$ 的最高不同位。不妨设这一位上 $x$ 为 $1$、$y$ 为 $0$，令 $x'=k\oplus y$，则 $x'<x$。根据 mex 定义，$G_1$ 一定能走到某个 SG 为 $x'$ 的后继，此时组合游戏的 SG 为 $x'\oplus y=k$；另一种情况同理。

因此所有 $k<s$ 都能出现，而 $s$ 不能出现，所以组合游戏后继 SG 的 mex 正是 $x\oplus y$。

这说明 $SG(G)=x$ 的组合含义是：$G$ 在与其他独立游戏组合时，与一堆大小为 $x$ 的 Nim 等价。

因此，一个能够拆成多个独立子游戏的问题，可以分别求出所有子游戏的 SG，再将它们异或，如果结果是 0 就是 P 态，不是 0 就是 N 态。

笔记

一个状态的 不同合法后继 之间取 mex；同一个后继内部的 多个独立子游戏 之间取异或。

三、状态图上的 SG 计算

如果状态空间不大，可以直接在状态 DAG 上记忆化计算 SG。对每个状态先递归得到所有后继 SG，再求 mex。

int dfs( int u ) {
    if( sg[u] != -1 ) return sg[u];
	set<int> s;
    for( int v : next_state( u ) ) {
        s.insert( dfs( v ) );
    }
	sg[u] = 0;
	while( s.count( sg[u] ) ) ++ sg[u];
    return sg[u];
}

状态规模较小时，可以直接根据定义计算 SG。

状态规模过大时，SG 定义通常只能得到一个正确但无法通过的暴力算法，此时可以保留小规模 SG 表，再寻找周期、二进制结构、质因子层数或其他规律。

具体问题见 公平组合博弈建模。

四、适用边界

标准 SG 理论依赖以下条件：

• 双方在同一局面拥有相同的合法操作；

• 游戏没有随机与隐藏信息；

• 游戏一定会在有限步内结束；

• 无法行动的一方失败；

• 被拆出的子游戏确实相互独立。

因此，最后一步胜负规则改变的 Misère 游戏、双方合法操作不同的非无偏游戏、可能无限循环并出现和局的游戏，以及包含随机或隐藏信息的游戏，都不能直接套用这里的 SG 定理。

它们可能仍然存在专门结论，但需要重新分析状态、终止条件与组合方式。

五、认知

公平组合博弈最基础的入口仍然是状态图。

如果只需要判断一个不可拆游戏的胜负，P/N 已经足够；但局面能够拆成多个独立子游戏时，P/N 会丢失组合信息，于是就需要用 SG 将每个子游戏压缩成一个等价的 Nim 堆，再通过异或合并。