每日算法 — 使用java实现Nim取石子游戏：Sprague-Grundy定理与组合博弈态分析

引言

Nim取石子游戏是组合博弈论中最经典的问题之一：若干堆石子，两位玩家轮流从任意一堆中取走至少一颗石子，无法行动者判负。看似简单的规则背后，隐藏着深刻的数学结构——Bouton定理揭示了Nim游戏的必胜策略与二进制异或运算之间的美妙联系。本文将用Java实现完整的Nim游戏AI，深入讲解Sprague-Grundy定理、Nim和的计算方法以及多堆扩展策略。

游戏规则与数学建模

基本规则

游戏开始时有 k 堆石子，各堆数量分别为 n₁, n₂, …, nₖ
两位玩家轮流操作，每次从一堆中取走至少1颗、至多全堆的石子
最后能行动的玩家获胜（正常游戏规则）

Bouton定理

1901年，Charles Bouton证明了Nim游戏的制胜法则：

设各堆石子数的异或和为 X = n₁ ⊕ n₂ ⊕ ... ⊕ nₖ。若 X ≠ 0，则先手必胜；若 X = 0，则后手必胜（在双方均采取最优策略的前提下）。

这一结论的优雅之处在于，将复杂的博弈状态分析转化为简单的位运算。

核心算法设计

1. Nim和计算与必胜态判定

public class NimGame {

    /**
     * 计算Nim和（各堆石子数的异或和）
     */
    static int nimSum(int[] piles) {
        int x = 0;
        for (int p : piles) x ^= p;
        return x;
    }

    /**
     * 判断当前局面是否为必胜态（对当前行动方）
     */
    static boolean isWinning(int[] piles) {
        return nimSum(piles) != 0;
    }

    /**
     * 寻找最优移动：返回 {堆索引, 取走石子数}
     * 核心思路：找到某堆p，使其变为 p ⊕ X（X为当前Nim和）
     */
    static int[] findBestMove(int[] piles) {
        int x = nimSum(piles);
        if (x == 0) {
            // 必败态，任意移动（这里取第一堆的1颗）
            return new int[]{0, 1};
        }

        // 必胜态：找到最高位为1的那一位
        for (int i = 0; i < piles.length; i++) {
            int target = piles[i] ^ x;
            if (target < piles[i]) {
                // 将该堆从 piles[i] 减少到 target
                return new int[]{i, piles[i] - target};
            }
        }
        return null; // 不应到达此处
    }

    public static void main(String[] args) {
        int[] piles = {3, 4, 5};
        System.out.println("初始局面: " + java.util.Arrays.toString(piles));
        System.out.println("Nim和: " + nimSum(piles));
        System.out.println("是否必胜: " + isWinning(piles));

        int[] move = findBestMove(piles);
        System.out.printf("最优移动: 从第%d堆取走%d颗石子%n", move[0] + 1, move[1]);
    }
}

2. 最优移动策略的数学证明

为什么 target = piles[i] ⊕ X 一定小于 piles[i]？

设 X 的最高位1在第 k 位。由于 X 是异或和，必然存在至少一堆石子在该位为1。选取这样的一堆 piles[i]，则有：

piles[i] 的第 k 位为 1
X 的第 k 位为 1
piles[i] ⊕ X 的第 k 位为 0（因为 1⊕1=0）

因此 piles[i] ⊕ X < piles[i]，这个操作是合法的（减少石子数）。

执行该操作后，新的Nim和为：

X' = X ⊕ piles[i] ⊕ (piles[i] ⊕ X) = 0

从而将必胜态转移给对手。

3. 完整的游戏模拟器

import java.util.*;

public class NimSimulator {

    static int nimSum(int[] piles) {
        int x = 0;
        for (int p : piles) x ^= p;
        return x;
    }

    static int[] aiMove(int[] piles) {
        int x = nimSum(piles);
        if (x == 0) {
            // 必败态：随机取一颗以延长游戏
            for (int i = 0; i < piles.length; i++) {
                if (piles[i] > 0) return new int[]{i, 1};
            }
        }
        for (int i = 0; i < piles.length; i++) {
            int target = piles[i] ^ x;
            if (target < piles[i]) return new int[]{i, piles[i] - target};
        }
        return null;
    }

    static boolean isGameOver(int[] piles) {
        for (int p : piles) if (p > 0) return false;
        return true;
    }

    static void printPiles(int[] piles) {
        System.out.print("[ ");
        for (int p : piles) System.out.print(p + " ");
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] piles = {3, 4, 5};
        Scanner sc = new Scanner(System.in);
        boolean humanTurn = true;

        System.out.println("=== Nim取石子游戏 ===");
        while (!isGameOver(piles)) {
            printPiles(piles);
            if (humanTurn) {
                System.out.print("你的回合：输入堆索引(从0开始)和取走数量，如 \"1 2\": ");
                int idx = sc.nextInt();
                int cnt = sc.nextInt();
                if (idx >= 0 && idx < piles.length && cnt > 0 && cnt <= piles[idx]) {
                    piles[idx] -= cnt;
                } else {
                    System.out.println("非法移动！");
                    continue;
                }
            } else {
                int[] move = aiMove(piles);
                piles[move[0]] -= move[1];
                System.out.printf("AI从第%d堆取走%d颗石子%n", move[0], move[1]);
            }
            humanTurn = !humanTurn;
        }
        System.out.println(humanTurn ? "AI获胜！" : "你获胜！");
    }
}

4. Sprague-Grundy定理扩展

Sprague-Grundy定理将Nim游戏的分析推广到所有无偏博弈（Impartial Game）：

任何无偏博弈的复合局面，等价于一个Nim堆，其大小等于各子局面Grundy数的异或和。

/**
 * 计算单堆Nim的Grundy数
 * 单堆Nim中，大小为n的堆的Grundy数就是n本身
 */
static int grundy(int pileSize) {
    // 在标准Nim中，g(n) = n
    // 因为可以转移到 0, 1, ..., n-1 中的任意状态
    return pileSize;
}

/**
 * 计算多堆Nim的Grundy数（即Nim和）
 */
static int compositeGrundy(int[] piles) {
    int g = 0;
    for (int p : piles) g ^= grundy(p);
    return g;
}

复杂度分析

时间复杂度：
Nim和计算：O(k)，k 为堆数
最优移动查找：O(k)
单步决策均为线性时间
空间复杂度：O(1)，仅使用常数额外空间

变种与扩展

Misère Nim（反Nim规则）

最后行动者判负。规则修正：当所有堆石子数均不超过1时，策略反转（X=0变必胜，X≠0变必败）；否则与正常Nim相同。

static boolean isMisereWinning(int[] piles) {
    int x = nimSum(piles);
    boolean allOne = true;
    for (int p : piles) if (p > 1) allOne = false;

    if (allOne) return x == 0; // 全为1时策略反转
    return x != 0; // 否则与正常Nim相同
}

限制取子数

若每堆每次最多取 m 颗，则Grundy数为 g(n) = n % (m + 1)。

小结

本文通过Java实现了Nim取石子游戏的完整AI系统：
– 基于异或运算的Nim和实现O(1)空间、O(k)时间的必胜态判定
– 严格数学证明的最优移动策略
– 完整的交互式游戏模拟器
– Sprague-Grundy定理的代码实现与扩展

Nim游戏之美在于，复杂的博弈分析最终被简化为一个位运算公式。这种从具体到抽象的提炼，正是算法思维的核心价值。

Tagged with: Nim游戏 Sprague-Grundy定理博弈论异或运算