Nim游戏

What · 是什么

Nim 游戏：共 n 堆石子，第 i 堆有 a_i 枚。两名玩家轮流操作，每次选取任意一堆，取走该堆中的任意正整数枚石子。无法操作（所有堆为空）的玩家输。结论（Bouton 定理）：局面先手必胜（N 态）当且仅当 Nim 和 s=a_1⊕a_2⊕⋯⊕a_n≠0；先手必败（P 态）当且仅当 s=0。必胜策略：找到最高位的 1（s 的最高位），选一堆 a_i 使其最高位为 1，将其改为 a_i⊕s（该值 < a_i），使新异或和为 0。

Why · 为什么

How · 实现

伪代码

# 判定先手胜负
def nim_win(piles):
  s = 0
  for a in piles: s ^= a
  return s != 0

# 构造必胜走法：返回 (堆下标, 取走后该堆大小) 或 None
def nim_move(piles):
  s = 0
  for a in piles: s ^= a
  if s == 0: return None
  for i, a in enumerate(piles):
    if (a ^ s) < a:
      return (i, a ^ s)  # 从第 i 堆取走 a-(a^s) 枚

Python 实现

def nim_win(piles):
    """返回当前局面是否为先手必胜（正常规则）。"""
    s = 0
    for a in piles:
        s ^= a
    return s != 0


def nim_move(piles):
    """返回必胜策略中的一步：元组 (堆下标, 操作后该堆剩余)。
    若已是 P 态（先手必败）返回 None。
    """
    s = 0
    for a in piles:
        s ^= a
    if s == 0:
        return None
    for i, a in enumerate(piles):
        if (a ^ s) < a:
            return (i, a ^ s)
    return None


def nim_strategy(piles):
    """演示：输出先手操作，并让后手（模拟最佳）应对后判断结果。
    仅用于教学演示。
    """
    if not nim_win(piles):
        return "P 态：先手必败"
    i, rest = nim_move(piles)
    return f"先手取第 {i} 堆，使其变为 {rest}"


if __name__ == "__main__":
    # 经典判定
    assert nim_win([1, 1]) is False        # 对称局面，后手跟手必胜
    assert nim_win([1, 2, 3]) is False     # 1^2^3 = 0
    assert nim_win([2, 5, 4]) is True      # 2^5^4 = 3
    assert nim_win([3]) is True
    assert nim_win([]) is False
    assert nim_win([1, 1, 1]) is True      # 1^1^1 = 1

    # 必胜走法正确性：移动后应为 P 态（异或和 0）
    for piles in [[2, 5, 4], [3, 4, 5, 6], [10, 8, 2], [7]]:
        i, rest = nim_move(piles)
        nxt = piles[:]
        nxt[i] = rest
        s = 0
        for a in nxt:
            s ^= a
        assert s == 0, (piles, nxt)

    # P 态无合法必胜走法
    assert nim_move([1, 1]) is None
    assert nim_move([1, 2, 3]) is None

    print("All tests passed.")

易错点

• 判断用『异或和==0 → 先手必败』，方向别记反
• a_i 可能为 0（空堆），异或不变，但全空局面是 P 态
• 构造走法时要找 (a^s)<a 的那一堆，不能随便取一堆
• P 态没有必胜走法，nim_move 返回 None 时别误报有解
• 异或用 Python 的 ^ 而非数学加号，两者不同
• 只适用于正常规则（最后取者赢）；misère 规则见 anti-nim

例题

信源

• 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