SG函数/Sprague-Grundy定理

What · 是什么

Sprague-Grundy 理论：任何公平组合游戏（双方行动集相同、完全信息、有限、无平局、正常规则）都等价于某个单堆 Nim 游戏。定义 SG 函数：终止状态 SG=0；一般状态 SG(x)=mex{SG(y): y 是 x 的后继}，其中 mex 是集合外的最小非负整数。SG(x)=k 表示该状态等价于一堆大小为 k 的石子。Sprague-Grundy 定理：多个独立子游戏的和（每步只能操作一个子游戏）的总 SG 值 = 各子游戏 SG 值的异或。总 SG=0 ⟺ 先手必败。

Why · 为什么

How · 实现

伪代码

# 对单个状态空间 0..n 计算 SG（moves 为可减少量集合）
def sg_table(n, moves):
  sg = [0]*(n+1)
  for k in 1..n:
    reach = { sg[k-m] for m in moves if k >= m }
    mex = 0
    while mex in reach: mex += 1
    sg[k] = mex
  return sg
# 多个子游戏：总 SG = xor of sg[i]；总 SG==0 → 先手必败

Python 实现

def sg_table(n, moves):
    """计算 SG(0..n)。moves 为一次可取走数量的集合。
    返回 sg 数组，sg[k] 为状态 k 的 SG 值。
    """
    sg = [0] * (n + 1)
    for k in range(1, n + 1):
        reach = {sg[k - m] for m in moves if k >= m}
        mex = 0
        while mex in reach:
            mex += 1
        sg[k] = mex
    return sg


def combine_sg(sub_sg):
    """Sprague-Grundy：多个独立子游戏总 SG = 异或。
    返回 0 表示先手必败，非 0 表示先手必胜。
    """
    x = 0
    for g in sub_sg:
        x ^= g
    return x


def sg_win(sub_sg):
    """总 SG 值异或判定胜负。"""
    return combine_sg(sub_sg) != 0


if __name__ == "__main__":
    # 游戏 1：取 1..K 个石子，SG(k) = k % (K+1)（周期）
    for K in range(1, 6):
        sg = sg_table(60, range(1, K + 1))
        for k in range(61):
            assert sg[k] == k % (K + 1), (K, k, sg[k])

    # 游戏 2：取平方数个石子（subtract-a-square），与递归定义交叉验证
    sq = [i * i for i in range(1, 8)]
    sg = sg_table(30, sq)
    from functools import lru_cache

    @lru_cache(maxsize=None)
    def sg_brute(k):
        if k == 0:
            return 0
        reach = {sg_brute(k - m) for m in sq if k >= m}
        mex = 0
        while mex in reach:
            mex += 1
        return mex

    for k in range(31):
        assert sg[k] == sg_brute(k), (k, sg[k], sg_brute(k))

    # SG 基本性质
    assert sg[0] == 0
    # 取 1 或 2 的游戏：SG(0..5)=0,1,2,0,1,2
    sg2 = sg_table(5, [1, 2])
    assert list(sg2) == [0, 1, 2, 0, 1, 2]
    # 组合游戏：两个取1/2子游戏，各自 3 个石子 → SG=0（先手必败）
    assert sg_win([sg2[3], sg2[3]]) is False
    assert sg_win([sg2[3], sg2[4]]) is True

    print("All tests passed.")

易错点

• mex 是『集合外最小非负整数』，不是 max+1（除非集合恰好是 0..max 全覆盖）
• 总 SG 用异或而非加法；多个子游戏异或后为 0 是必败而非必胜
• sg_table 里 moves 若含 0（允许不取）会自环，必须保证每次真正减少
• 状态需满足有限 + 无平局（DAG）才有 SG；有环见 game-on-graph 的胜负平局分类
• 找周期时周期起点的偏移也要测（SG 可能在若干项后才进入周期）
• SG 值可能超过 |moves|，mex 的上界是 |moves|，不必担心溢出

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/game-theory/impartial-game/
• CP-Algorithms✓ https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
• 书籍✓ CPH ch25 Game theory, pp.245-252