博弈论中的 Sprague-Grundy (SG) 定理 与 Nim 游戏

这篇文章介绍博弈论中的 Sprague-Grundy (SG) 定理 与 Nim 游戏 。我们将从最基础的组合博弈论公理出发，推导至 SG 函数的核心逻辑，并解释为何异或运算（XOR）成为了连接独立子游戏的桥梁。

一、公平组合游戏

在探讨 SG 函数之前，必须明确我们所讨论的游戏类型。这些结论仅适用于 公平组合游戏 (Impartial Combinatorial Games, ICG)。

1. 公平组合游戏的定义

一个游戏若满足以下条件，则为 ICG：

  • 两人对弈：两名玩家轮流行动。
  • 信息完全：博弈双方知晓所有游戏状态（无隐藏牌、无战争迷雾）。
  • 无随机性：没有骰子或概率事件。
  • 有限性：游戏在有限步数内必然结束。
  • 公平性：这是最关键的一点。对于任意局势，可执行的合法操作仅取决于当前局势本身，与轮到哪位玩家无关。（象棋不是公平组合游戏，因为红方只能走红子，黑方只能走黑子）。
  • 胜负判定：通常采用“正常游戏规则”（Normal Play Convention），即无法进行合法移动的一方判负（Last Player Wins）。

2. 状态的分类：必胜与必败

在 ICG 中，任何一个状态都可以被归类为 必胜态 (N-position) 或 必败态 (P-position)。

  • P-position (Previous player win)：前一个走棋的人获胜，即当前轮到的人必败。
  • N-position (Next player win)：下一个走棋的人获胜，即当前轮到的人必胜。

核心递归逻辑：

  1. 终止态（无法移动）是 P-position。
  2. 若一个状态能转移到 至少一个 P-position，则该状态为 N-position。（只要能把必败局面丢给对手，我就必胜）。
  3. 若一个状态的所有后继状态 全部 都是 N-position，则该状态为 P-position。（无论怎么走，对手都必胜，所以我必败）。

二、从状态到数值 —— SG 函数与 Mex 运算

仅用 P/N 标记状态虽然逻辑完备，但在处理复杂游戏（尤其是多个游戏并行进行）时，计算量会指数级爆炸。我们需要将状态量化。

1. Mex 运算 (Minimum Excluded value)

定义 为一个非负整数集合。 定义为 不属于集合 的最小非负整数。

直观理解： Mex 寻找的是“缺失的第一块拼图”。它代表了当前状态相对于后续可能性的“空缺”。

2. SG 函数的定义

对于游戏中的任意状态 ，其 SG 函数值 定义为： 是的所有后继状态

通过 SG 值判定胜负：

  • 若 ，则 为必败态 (P-position)。
  • 若 ，则 为必胜态 (N-position)。

原理解析：

  • 终止态：没有后继状态，集合为空，。符合必败态定义。
  • 非零态：如果 ，根据 mex 定义，其后继状态的 SG 值集合中必然包含 。这意味着当前玩家一定可以将状态转移到一个 SG 值为 0 的状态（必败态）。
  • 零态：如果 ，说明其后继状态的 SG 值集合中没有 0。无论怎么走，下一个状态的 SG 值必然非 0。这意味着只能将非 0（必胜态）留给对手。

小结： SG 函数将复杂的胜负关系映射到了非负整数域，0 代表必败，非 0 代表必胜。数值的大小则隐含了该状态的“潜力”或“能量等级”。

三、游戏的加法与 Nim 和 (XOR)

这是博弈论中最令人着迷的部分。当我们将多个独立的子游戏组合成一个大游戏时（例如 Nim 游戏中的多堆石子），如何计算总局面的 SG 值？

1. 组合游戏和 (Disjunctive Sum)

设游戏 由两个独立的子游戏 和 组成。在 中行动意味着玩家可以选择在 中行动 或者 在 中行动。 记作 。

2. Sprague-Grundy 定理

定理断言：组合游戏总状态的 SG 值等于各独立子游戏 SG 值的异或和 (XOR, 符号 )。

3. 为什么是异或 (XOR)？

要理解为什么是异或，我们需要考察 Nim 游戏本身以及异或运算的性质。

异或运算的性质：

  • （自反性：相同的数相消）
  • 二进制下的不进位加法。

证明思路 (Bouton’s Theorem)： 假设总状态 SG 值为 。我们需要证明 符合 SG 函数的定义（即 所有后继总状态的值）。这等价于证明两点：

  1. 对于任意 ，存在一种走法使得新的总异或和为 。
  2. 无论如何走，新的总异或和不可能等于 。

推导过程：

  • 性质 1（能走到更小）： 设当前异或和 。设 是任意满足 的目标值。 我们需要找到某个子游戏 ，将其变为 ，使得新的总异或和 。 这等价于要求 。 设 是 和 二进制表示中最高位的不同位（必然存在，因为 ）。在该位上， 为 1， 为 0。 根据异或性质，必然存在至少一个 ，其二进制在第 位也是 1。 构造 。可以证明 。 根据 SG 函数定义，既然 ，那么在子游戏 中必然存在一步操作可以转移到 。

    结论：只要 ，我们就一定能一步走到异或和为 0 的状态（或其他更小的状态）。

  • 性质 2（走不到自己）： 如果在某个子游戏 中移动，其 SG 值从 变为 （显然 ）。 新的总异或和 。 由于 ，根据异或性质，。

    结论：无论怎么走，都无法维持当前的异或和不变。

Nim 游戏的特殊性： Nim 游戏是 SG 定理的最简应用。

  • 一堆数量为 的石子，其实就是一个子游戏。
  • 这个子游戏的后继状态是 。
  • 根据 mex 定义，。
  • 因此，Nim 游戏中一堆 个石子的 SG 值就是 本身。
  • 整个 Nim 游戏的 SG 值 = 各堆石子数量的异或和。

四、总结

到这里，我们可以发现：

  1. 量化状态：不要看具体的棋子或石子，要看状态背后的“能量值”（SG 值）。
  2. Mex 是局部属性：Mex 运算定义了单个子游戏内部的转移逻辑（填补空缺）。它保证了每个数值代表的胜负性质是自洽的。
  3. XOR 是全局属性：异或运算定义了多个子游戏之间的叠加逻辑。它利用二进制位的“不进位加法”特性，完美模拟了组合博弈中“如果两个子游戏状态完全相同则相互抵消（等同于必败态 0）”的性质。

一些结论：

  • SG(x) = mex(后继)：这是微观视角，解决了“在这个子游戏中我处于什么地位”。
  • SG(Total) = SG(1) ⊕ SG(2)…：这是宏观视角，解决了“当多个子游戏并行时，整体局势如何”。
  • Nim 游戏：是 SG 定理的一个特例，其中子游戏的 SG 值恰好等于石子数本身，使得 ，从而直接对石子数进行异或。