博弈论与组合博弈 (Game Theory & ICG)¶

博弈论（Game Theory） 是算法竞赛与计算机科学中研究决策主体在对抗环境中如何选取最优策略的数学理论。

在算法竞赛中，绝大多数博弈问题属于公平组合游戏（Impartial Combinatorial Games, ICG）。掌握必胜/必败态的拓扑传递性、经典博弈模型（Bash、Wythoff、Nim）以及强大的 Sprague-Grundy (SG) 定理，是解决对抗决策与极值博弈问题的终极武器。

1. 公平组合游戏 (ICG) 核心公理¶

一个博弈被定义为公平组合游戏（ICG），当且仅当它满足以下四个特征： 1. 两人交替行动：两名玩家轮流做出合法决策； 2. 完全信息与无随机性：游戏中不存在隐藏信息（如暗牌），不存在骰子等随机因素； 3. 行动规则完全对称：在任意给定的游戏状态下，两名玩家所能采取的合法移动集合完全相同（国际象棋/围棋中双方执黑白不同，不属于 ICG）； 4. 有限步内必终止：无论双方如何决策，游戏必然在有限步内结束，且不存在平局。通常采用常规正规规则（Normal Play Convention）：最后一名能做出合法移动的玩家获胜（即无法移动者判负）。

2. 必胜态 (N-position) 与必败态 (P-position)¶

任何一个有限无环的 ICG 都可以抽象为一张有向无环图（博弈图 / Game DAG），图中的每个节点代表一个游戏状态，有向边代表一次合法的走步。

每个状态被严格分为两类： * 必败态（P-position / Previous Player Winning）：当前轮到行动的玩家处于必败局面；换言之，上一位刚行动完的玩家必胜。 * 必胜态（N-position / Next Player Winning）：当前轮到行动的玩家处于必胜局面；换言之，即将行动的玩家有必胜策略。

flowchart TD
    subgraph P_State["必败态 (P-position)"]
        P["任意移动"]
    end
    subgraph N_State["必胜态 (N-position)"]
        N1["存在某种移动"] --> P1["必败态 (P)"]
        N2["其他移动"] --> Any["其他状态"]
    end
    P --> N_All["必定只能转移到 必胜态 (N)"]

状态判定三大基本定理：¶

终局判定：所有无法进行任何移动的终局状态（Terminal States）均为 必败态（P-position）；
必胜态判定：若从当前状态出发，存在至少一种合法移动能够转移到某个必败态（P-position），则当前状态为 必胜态（N-position）（聪明的玩家会故意把必败烂摊子留给对手）；
必败态判定：若从当前状态出发，无论做出何种合法移动，都只能转移到必胜态（N-position），则当前状态为 必败态（P-position）。

3. 四大经典组合博弈模型¶

3.1 巴什博弈 (Bash Game)¶

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

结论与策略：¶

若 $n \bmod (m + 1) == 0$，则先手必败（P）；否则先手必胜（N）。

\[ n \equiv 0 \pmod{m + 1} \iff \text{P-position} \]

先手必胜策略：若 $n = k(m + 1) + r$（$1 \le r \le m$），先手第一次取走 $r$ 个，此后无论后手取 $x$ 个（$1 \le x \le m$），先手总是对应取走 $m + 1 - x$ 个，牢牢锁定每轮消耗 $m + 1$ 个物品的节奏，直至取光。

3.2 威佐夫博弈 (Wythoff's Game)¶

规则：有两堆物品，数量分别为 $a$ 和 $b$。两人轮流取物，每次可以： 1. 在其中任意一堆中取走任意数量的物品； 2. 或者在两堆中同时取走相同数量的物品。最后取光者胜。

奇异局势（必败态）：¶

前几个必败态（奇异局势）为：$(0, 0), (1, 2), (3, 5), (4, 7), (6, 10), (8, 13) \dots$

这些奇异局势与黄金分割比 $\phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887\dots$ 存在惊人的数学联系（Betty 定理）：

第 $k$ 个奇异局势 $(a_k, b_k)$（$k \ge 0$）满足：

\[ a_k = \lfloor k \cdot \phi \rfloor = \left\lfloor k \cdot \frac{1 + \sqrt{5}}{2} \right\rfloor \]

\[ b_k = a_k + k = \lfloor k \cdot \phi^2 \rfloor \]

判定算法：¶

给定两堆物品 $(a, b)$（设 $a \le b$）： 1. 计算差值 $k = b - a$； 2. 若 $a == \lfloor k \cdot \frac{1 + \sqrt{5}}{2} \rfloor$，则先手必败；否则先手必胜。时间复杂度 $\mathcal{O}(1)$。

3.3 斐波那契博弈 (Fibonacci Nim)¶

规则：有一堆 $n$ 个物品。先手第一次可以取任意个，但不能一次取完；此后每一次取的物品数至多为上一次对手所取物品数的 2 倍（且至少取 1 个）。

齐肯多夫定理 (Zeckendorf's Theorem) 与结论：¶

当且仅当 $n$ 是斐波那契数（Fibonacci Number）时，先手必败；否则先手必胜。

先手必胜策略：根据齐肯多夫定理，任何正整数都可以唯一分解为若干个不相邻的斐波那契数之和 $n = f_{i_1} + f_{i_2} + \dots + f_{i_k}$（其中 $f_{i_1}$ 最小）。先手只需在第一回合取走最小的基底 $f_{i_1}$，后续即可步步诱导对手落入斐波那契必败循环。

3.4 尼姆博弈 (Nim Game) 与 Bouton 定理¶

规则：有 $k$ 堆物品，每堆物品数量分别为 $a_1, a_2, \dots, a_k$。两名玩家轮流选择某一堆，从中取走任意正整数个物品（甚至可以整堆拿走）。最后取光者获胜。

Bouton 定理：¶

定义这 $k$ 堆物品数量的二进制按位异或和（Nim 和）为：

\[ X = a_1 \oplus a_2 \oplus \dots \oplus a_k \]

当且仅当 $X = 0$ 时，当前局面为必败态（P-position）；当且仅当 $X \ne 0$ 时，当前局面为必胜态（N-position）。

严格数学证明：¶

终局满足：所有物品取光时，$a_1 = a_2 = \dots = a_k = 0$，此时 $X = 0$，符合必败态定义；
从 $X \ne 0$ 必能一步转移到 $X = 0$：设 $X$ 的最高二进制位是第 $d$ 位。必然存在至少某一堆 $a_i$，其二进制表示在第 $d$ 位也为 $1$。显然 $a_i \oplus X < a_i$。我们将这一堆的物品数减少至 $a'_i = a_i \oplus X$，此时新的异或和变为： $$X' = X \oplus a_i \oplus a'_i = X \oplus a_i \oplus (a_i \oplus X) = 0$$ 这一合法操作成功将非零异或和变成了零！
从 $X = 0$ 无论如何移动，必然转移到 $X \ne 0$：若某步操作将堆 $a_i$ 变为 $a'_i$（$a'_i < a_i$），新异或和为 $X' = 0 \oplus a_i \oplus a'_i = a_i \oplus a'_i$。因为 $a'_i \ne a_i$，故 $X' \ne 0$。

4. Sprague-Grundy (SG) 函数与博弈复合¶

尼姆博弈是组合博弈论的核心基石，因为 任何公平组合游戏（ICG）都可以通过 SG 函数等价转化为一个尼姆堆！

4.1 MEX 运算与 SG 函数定义¶

MEX (Minimum Excluded Value)：对于一个非负整数集合 $S$，$\operatorname{mex}(S)$ 表示不属于 $S$ 的最小非负整数。例如 $\operatorname{mex}(\{0, 1, 2, 4\}) = 3$，$\operatorname{mex}(\emptyset) = 0$。
状态的 SG 值：对于游戏状态节点 $u$，设其所有后继合法状态集合为 $Succ(u) = \{v \mid u \to v\}$，则 $u$ 的 SG 函数定义为：

\[ SG(u) = \operatorname{mex}\Big(\{SG(v) \mid v \in Succ(u)\}\Big) \]

特殊状态：无法进行任何移动的终局状态 $t$，其后继集为空，因此 $SG(t) = \operatorname{mex}(\emptyset) = 0$。

4.2 Sprague-Grundy 定理 (SG 定理)¶

对于由 $k$ 个相互独立的子游戏构成的复合博弈 $G = G_1 + G_2 + \dots + G_k$（玩家每次只能在其中某一个子游戏中进行一步合法移动）：

复合游戏整体状态的 SG 值，等于各个子游戏当前状态 SG 值的按位异或和：

\[ SG(G) = SG(G_1) \oplus SG(G_2) \oplus \dots \oplus SG(G_k) \]

胜负判据：
$SG(G) \ne 0 \iff$ 先手必胜（N-position）；
$SG(G) == 0 \iff$ 先手必败（P-position）。

5. LeetCode 经典真题精选与深度精析¶

LeetCode 292 - Nim 游戏 (Nim Game) 简单
提示

巴什博弈 1:1 原型题。
- 每次可以拿 1 到 3 块石头。对应巴什博弈参数 $m = 3$。
- 周期模数为 $m + 1 = 4$。
- 当且仅当 $n \bmod 4 \ne 0$ 时先手必胜。
- 核心代码：return n % 4 != 0;。时间复杂度 $\mathcal{O}(1)$。
LeetCode 877 - 石子游戏 (Stone Game) 中等
提示

奇偶对称性染色必胜贪心。
- 数组总长为偶数，且石子总数为奇数。
- 先手可以选择拿走所有奇数下标的石子，或者所有偶数下标的石子。
- 既然总和为奇数，奇数下标之和与偶数下标之和必然不相等，先手必定能锁定较大的一半。
- 核心代码：return true;。时间复杂度 $\mathcal{O}(1)$。
LeetCode 1140 - 石子游戏 II (Stone Game II) 中等
提示

极小化极大（Minimax）记忆化搜索。
- 状态定义：dfs(i, M) 表示当前从第 $i$ 堆石子开始选，参数为 $M$ 时，当前玩家能获得的最大石子数。
- 状态转移：当前玩家尝试取 $X \in [1, 2M]$ 堆，获得当前区间的石子，给对手留下 dfs(i + X, max(M, X))。
- 目标是最大化自身得分：用剩余总石子数减去对手能拿的最大值。
- 记忆化维度 $\mathcal{O}(N^2)$，时间复杂度 $\mathcal{O}(N^3)$。
LeetCode 913 - 猫和老鼠 (Cat and Mouse) 困难
提示

博弈图状态反向拓扑染色（处理平局环路）。
- 状态由三元组构成：(mouse, cat, turn)。
- 终局状态：老鼠进洞（老鼠赢）、猫抓到老鼠（猫赢）、轮数超限（平局）。
- 采用反向拓扑排序：
- 从已知的确定胜负状态出发，沿着反向移动边倒推更新前驱状态；
- 若某状态能一步走到对手的必败态，则该状态立即被染为必胜态；
- 维护出度计数，只有当前状态的所有后继全都是必胜态时，该状态才被判定为必败态。
- 时间复杂度 $\mathcal{O}(V^2)$。
LeetCode 1406 - 石子游戏 III (Stone Game III) 困难
提示

动态规划与博弈差值最大化。
- 设 $dp[i]$ 表示从第 $i$ 堆开始取，当前玩家能领先对手的最大相对净得分。
- 转移：$dp[i] = \max_{k=1}^3 \big(\sum_{j=0}^{k-1} piles[i+j] - dp[i+k]\big)$。
- 最终判断 $dp[0]$ 大于、小于还是等于 0 即可。时间复杂度 $\mathcal{O}(N)$，空间复杂度 $\mathcal{O}(1)$。