博弈图与必胜必败态

What · 是什么

博弈图：公平组合游戏的所有状态作为顶点，状态 x 到后继 y 连有向边（一次合法操作）。若游戏有限且无平局，博弈图是有向无环图（DAG）。必胜必败态（N/P 态）由归纳规则定义：① 无后继的状态是 P 态（先手无路可走而失败）；② 存在至少一个后继为 P 的状态是 N 态；③ 所有后继都是 N 的状态是 P 态。通过逆拓扑序（从出度为 0 的顶点开始反图 BFS）可在 O(|V|+|E|) 内标记所有状态。该框架是 Nim 定理、SG 函数与有向图游戏的共同基础。

Why · 为什么

How · 实现

伪代码

# DAG 上标记 N/P 态（逆拓扑 + 反图队列）
indeg_out = [len(succ[u]) for u]      # 出度
state = [未知] * V                     # -1=P, 1=N
queue = [u for u in V if outdeg[u]==0]
for u in queue: state[u] = P
while queue:
  u = queue.pop(0)
  for v in pred[u]:                   # 反图
    if state[v] != 未知: continue
    if state[u] == P: state[v] = N; queue.append(v)
    else:
      outdeg[v] -= 1
      if outdeg[v] == 0: state[v] = P; queue.append(v)

Python 实现

from collections import deque


def classify_dag(n, graph):
    """在 DAG 上标记全部状态的 N/P 态。
    graph[u] = u 的后继列表。
    返回 state: 1=先手必胜(N), -1=先手必败(P)。
    """
    outdeg = [len(graph[u]) for u in range(n)]
    pred = [[] for _ in range(n)]
    for u in range(n):
        for v in graph[u]:
            pred[v].append(u)

    state = [0] * n
    q = deque()
    for u in range(n):
        if outdeg[u] == 0:
            state[u] = -1
            q.append(u)
    while q:
        u = q.popleft()
        for v in pred[u]:
            if state[v] != 0:
                continue
            if state[u] == -1:
                state[v] = 1
                q.append(v)
            else:
                outdeg[v] -= 1
                if outdeg[v] == 0:
                    state[v] = -1
                    q.append(v)
    return state


if __name__ == "__main__":
    # 链式博弈 0->1->2->3（终点 3 无后继）
    g1 = [[1], [2], [3], []]
    s1 = classify_dag(4, g1)
    assert s1 == [1, -1, 1, -1], s1

    # 取 1 或 2 个石子的单堆游戏：状态 k 有后继 k-1,k-2
    g2 = [[], [0], [0, 1], [1, 2], [2, 3], [3, 4]]
    s2 = classify_dag(6, g2)
    assert s2 == [-1, 1, 1, -1, 1, 1], s2  # SG: 0,1,2,0,1,2

    # 与 SG 表交叉验证：取 1..K 的游戏 SG(k)=k%(K+1)，N 态 ⟺ SG≠0
    def sg_win(k, K):
        return k % (K + 1) != 0

    for K in [1, 2, 3]:
        g = [[max(0, k - d) for d in range(1, K + 1) if k >= d] for k in range(12)]
        s = classify_dag(12, g)
        for k in range(12):
            assert (s[k] == 1) == sg_win(k, K), (K, k, s[k])

    print("All tests passed.")

易错点

• P 态定义是『所有后继都是 N』，不是『存在后继是 N』（后者是 N 态）
• 标记过程必须用反图（pred），正图会漏更新
• 出度为 0 的顶点初始化为 P 态，别忘了入队
• 有环图不能直接跑该算法（会残留未知状态当作 P 导致错误），需三分类
• state 用 0 表示未定，注意与真实 P(-1)/N(1) 区分
• 若状态含大量未达态（孤点）要按真实出度处理

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/game-theory/impartial-game/
• OI Wiki✓ https://oi-wiki.org/math/game-theory/intro/
• 书籍✓ CPH ch25 Game theory, pp.245-252