每日算法 — 使用java实现Nim取石子游戏：异或运算与Sprague-Grundy定理

可莉爸爸 AI算法

Nim取石子游戏是组合数学中最经典的 impartial game（公平博弈）之一。传说它起源于中国，由哈佛大学数学家Charles Bouton于1901年系统分析并给出了完整的必胜策略。本文将用Java实现一个带AI对手的Nim游戏，深入讲解异或运算（XOR）判定胜负的核心原理，并扩展介绍Sprague-Grundy定理如何将单堆结论推广到任意多堆组合的通用框架。

一、Nim游戏规则

游戏开始时桌面上有若干堆石子，两位玩家轮流操作。每次操作可以选择任意一堆，从中取走至少一颗、至多整堆的石子。无法操作（即所有堆均为空）的玩家判负。

示例

假设有三堆石子，数量分别为 (3, 4, 5)：
– 玩家A从第3堆取走2颗，局面变为 (3, 4, 3)
– 玩家B从第2堆取走4颗，局面变为 (3, 0, 3)
– 玩家A从第1堆取走3颗，局面变为 (0, 0, 3)
– 玩家B从第3堆取走3颗，局面变为 (0, 0, 0)，玩家A无子可取，判负

二、Nim和定理：异或运算的魔力

Bouton证明了一个惊人的结论：将每堆石子的数量进行异或（XOR）运算，得到的结果称为 Nim和（Nim-sum）。

  • 若 Nim和 ≠ 0，当前局面为必胜态（N-position），先手必胜
  • 若 Nim和 = 0，当前局面为必败态（P-position），先手必败（在对手不犯错的前提下）

2.1 异或运算回顾

异或是按位运算，相同为0，不同为1。对于整数运算，它有几个关键性质：

性质 说明
自反性 a ^ a = 0
零元 a ^ 0 = a
交换律/结合律 a ^ b = b ^ a，(a ^ b) ^ c = a ^ (b ^ c)

2.2 为什么Nim和能判定胜负

核心思路是证明三个引理：

引理1：若当前Nim和为0，任何合法操作都会使Nim和变为非0。
– 证明：设操作前各堆为 a₁, a₂, ..., aₙ，有 a₁ ^ a₂ ^ ... ^ aₙ = 0。
– 操作某一堆 aᵢ 变为 aᵢ'，由于 aᵢ' ≠ aᵢ，则新的Nim和为 0 ^ aᵢ ^ aᵢ' = aᵢ ^ aᵢ' ≠ 0。

引理2：若当前Nim和不为0，必存在一种合法操作使Nim和变为0。
– 证明：设 S = a₁ ^ a₂ ^ ... ^ aₙ ≠ 0。设 S 的最高位1在第 k 位，则至少存在一个 aᵢ 的第 k 位也为1。
– 取 aᵢ' = aᵢ ^ S，则 aᵢ' < aᵢ（因为最高位1被消去），且新的Nim和为 S ^ aᵢ ^ aᵢ' = S ^ aᵢ ^ (aᵢ ^ S) = 0。

引理3：终局状态 (0, 0, ..., 0) 的Nim和为0。

由这三个引理，Nim和为0的局面只能转移到非0局面，而Nim和非0的局面总能转移到0局面。因此持有0局面的玩家终将被逼入终局而败北。

三、Java实现：核心算法

3.1 游戏状态与Nim和计算

/**
 * Nim游戏核心状态类
 * 维护多堆石子的当前数量，提供Nim和计算与必胜策略查询
 */
public class NimGame {
    private int[] piles;  // 各堆石子数量

    public NimGame(int[] initialPiles) {
        this.piles = initialPiles.clone();
    }

    /**
     * 计算当前局面的Nim和（所有堆的异或值）
     * 时间复杂度：O(n)，n为堆数
     */
    public int nimSum() {
        int sum = 0;
        for (int pile : piles) {
            sum ^= pile;
        }
        return sum;
    }

    /**
     * 判断当前是否为必胜态
     */
    public boolean isWinningPosition() {
        return nimSum() != 0;
    }

    /**
     * 判断游戏是否结束
     */
    public boolean isGameOver() {
        for (int pile : piles) {
            if (pile > 0) return false;
        }
        return true;
    }

    /**
     * 执行取石子操作
     * @param pileIndex 堆的索引（从0开始）
     * @param removeCount 取走的石子数
     * @return 是否操作成功
     */
    public boolean take(int pileIndex, int removeCount) {
        if (pileIndex < 0 || pileIndex >= piles.length) return false;
        if (removeCount <= 0 || removeCount > piles[pileIndex]) return false;
        piles[pileIndex] -= removeCount;
        return true;
    }

    public int[] getPiles() {
        return piles.clone();
    }
}

3.2 必胜策略引擎：找到使Nim和为0的操作

/**
 * Nim策略引擎
 * 基于Nim和定理计算最优走法
 */
public class NimStrategy {

    /**
     * 计算当前局面的最优操作
     * 若当前为必胜态，返回一个使Nim和变为0的操作
     * 若当前为必败态，返回任意合法操作（或null表示认输）
     *
     * @param piles 当前各堆数量
     * @return 最优操作 [堆索引, 取走数量]，若无法必胜则返回null
     */
    public static int[] findBestMove(int[] piles) {
        int sum = 0;
        for (int pile : piles) {
            sum ^= pile;
        }

        // 必败态：任何操作都会让对手处于必胜态
        if (sum == 0) {
            return findAnyMove(piles);
        }

        // 必胜态：找到一堆，使其变为 (pile ^ sum)
        for (int i = 0; i < piles.length; i++) {
            int target = piles[i] ^ sum;
            if (target < piles[i]) {
                // 验证：操作后Nim和应为0
                int newSum = 0;
                for (int j = 0; j < piles.length; j++) {
                    newSum ^= (j == i ? target : piles[j]);
                }
                if (newSum == 0) {
                    return new int[]{i, piles[i] - target};
                }
            }
        }

        return null;
    }

    /**
     * 在必败态下寻找任意合法操作
     */
    private static int[] findAnyMove(int[] piles) {
        for (int i = 0; i < piles.length; i++) {
            if (piles[i] > 0) {
                return new int[]{i, 1}; // 取走1颗
            }
        }
        return null;
    }
}

四、完整游戏：人机对战实现

import java.util.Scanner;

/**
 * Nim取石子游戏完整实现
 * 支持人机对战，AI基于Nim和定理进行最优决策
 */
public class NimGameDemo {

    private NimGame game;
    private Scanner scanner;

    public NimGameDemo(int[] piles) {
        this.game = new NimGame(piles);
        this.scanner = new Scanner(System.in);
    }

    /**
     * 启动游戏主循环
     */
    public void start() {
        System.out.println("=== Nim取石子游戏 ===");
        System.out.println("规则：多堆石子，每次从一堆取至少1颗，取最后一颗者胜\n");

        boolean humanTurn = true; // 玩家先手

        while (!game.isGameOver()) {
            printState();

            if (humanTurn) {
                playerMove();
            } else {
                aiMove();
            }

            humanTurn = !humanTurn;
        }

        // 游戏结束，上一轮操作者获胜
        System.out.println("\n游戏结束！" + (humanTurn ? "AI" : "玩家") + "获胜！");
    }

    /**
     * 打印当前局面
     */
    private void printState() {
        int[] piles = game.getPiles();
        System.out.print("当前局面: ");
        for (int i = 0; i < piles.length; i++) {
            System.out.printf("[%d]=%d ", i, piles[i]);
        }
        System.out.println("| Nim和 = " + game.nimSum() +
                          (game.isWinningPosition() ? " (必胜态)" : " (必败态)"));
    }

    /**
     * 玩家回合
     */
    private void playerMove() {
        while (true) {
            System.out.print("玩家回合 - 请输入[堆索引 取走数量]：");
            try {
                int pile = scanner.nextInt();
                int count = scanner.nextInt();
                if (game.take(pile, count)) {
                    System.out.printf("玩家从第%d堆取走%d颗石子\n", pile, count);
                    return;
                }
                System.out.println("非法操作，请重新输入！");
            } catch (Exception e) {
                System.out.println("输入格式错误！");
                scanner.nextLine();
            }
        }
    }

    /**
     * AI回合：基于Nim和定理的最优策略
     */
    private void aiMove() {
        int[] piles = game.getPiles();
        int[] move = NimStrategy.findBestMove(piles);

        if (move == null) {
            System.out.println("AI无合法操作，认输！");
            return;
        }

        int pile = move[0];
        int count = move[1];
        game.take(pile, count);
        System.out.printf("AI从第%d堆取走%d颗石子", pile, count);

        if (game.nimSum() == 0) {
            System.out.print(" (策略：使Nim和归零)");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 经典开局：3堆石子 (3, 5, 7)
        // Nim和 = 3 ^ 5 ^ 7 = 1，为必胜态
        int[] initialPiles = {3, 5, 7};
        new NimGameDemo(initialPiles).start();
    }
}

五、Sprague-Grundy定理：从Nim到一切

Nim和定理只能处理标准的Nim游戏，而Sprague-Grundy定理将其推广到了所有 impartial game 的组合。

5.1 Grundy数（Sprague-Grundy函数）

对于任意 impartial game 的某个局面，定义其 Grundy数（或称Nimber） g(x) 为：

g(x) = mex { g(y) | y 是 x 的所有直接后继局面 }

其中 mex（minimum excluded value）是不在该集合中的最小非负整数。

局面 后继局面的Grundy数集合 mex g(x)
终局（无操作） ∅ mex{} 0
单堆1颗石子 {0} mex{0} 1
单堆2颗石子 {0, 1} mex{0,1} 2
单堆3颗石子 {0, 1, 2} mex{0,1,2} 3

关键发现：对于Nim的单堆局面，Grundy数恰好等于堆中石子的数量！

5.2 多游戏组合的Grundy数

Sprague-Grundy定理指出：多个 impartial game 组合的总局面的Grundy数，等于各子游戏Grundy数的异或值。

G(总局面) = g₁ ^ g₂ ^ ... ^ gₙ

这意味着任何 impartial game 的组合都可以等价地转化为一个Nim游戏！只需将每个子游戏的Grundy数视为Nim的一堆石子即可。

5.3 Java实现：Grundy数计算器

import java.util.*;

/**
 * Grundy数计算器（以Nim单堆为例验证定理）
 * 可通过修改getSuccessors扩展到其他impartial game
 */
public class GrundyCalculator {

    private Map<Integer, Integer> memo = new HashMap<>();

    /**
     * 计算单堆Nim的Grundy数
     * 结果验证：g(n) = n（与Nim堆大小一致）
     */
    public int grundy(int pileSize) {
        if (pileSize == 0) return 0;
        if (memo.containsKey(pileSize)) return memo.get(pileSize);

        // 后继局面：可以取走1到pileSize颗，得到 0 到 pileSize-1
        Set<Integer> successors = new HashSet<>();
        for (int i = 0; i < pileSize; i++) {
            successors.add(grundy(i));
        }

        int g = mex(successors);
        memo.put(pileSize, g);
        return g;
    }

    /**
     * 计算mex：不在集合中的最小非负整数
     */
    private int mex(Set<Integer> set) {
        int m = 0;
        while (set.contains(m)) {
            m++;
        }
        return m;
    }

    public static void main(String[] args) {
        GrundyCalculator calc = new GrundyCalculator();
        System.out.println("Nim单堆的Grundy数验证：");
        for (int i = 0; i <= 10; i++) {
            int g = calc.grundy(i);
            System.out.printf("g(%d) = %d %s\n", i, g, g == i ? "✓" : "✗");
        }
    }
}

运行结果：

Nim单堆的Grundy数验证：
g(0) = 0 ✓
g(1) = 1 ✓
g(2) = 2 ✓
g(3) = 3 ✓
g(4) = 4 ✓
g(5) = 5 ✓
...

六、复杂度分析

操作 时间复杂度 空间复杂度 说明
Nim和计算 O(n) O(1) n为堆数
最优策略查找 O(n) O(1) 遍历所有堆
Grundy数（含memo） O(n²) O(n) n为单堆最大石子数
游戏主循环 O(总操作数 × n) O(n) 每次操作后重新计算

七、总结

本文从Nim取石子游戏出发，系统推导了Nim和定理的完整证明，展示了异或运算如何优雅地判定组合博弈的胜负。通过Java实现的完整人机对战系统，读者可以直观感受AI如何基于数学定理进行不可战胜的决策。

进一步介绍的Sprague-Grundy定理揭示了更深刻的规律：所有 impartial game 的组合本质上都是Nim游戏的伪装。掌握Grundy数和 mex 运算，就能将这一理论工具应用到取石子变体、翻硬币游戏、棋类简化模型等更广泛的场景中。理解Nim游戏，是踏入组合博弈论（Combinatorial Game Theory）这座数学殿堂的第一步。

Tagged with: