每日算法 — 使用java实现Nim游戏：SG函数与博弈论组合分析

引言

Nim游戏是组合博弈论中最经典的问题之一。游戏规则简单：有若干堆石子，两位玩家轮流从任意一堆中取走至少一颗石子，取走最后一颗石子者获胜。看似简单的规则，却引出了Sprague-Grundy定理这一博弈论的基石。本文将用Java完整实现Nim游戏及其变种，深入讲解SG函数的计算方法与应用。

游戏规则与数学建模

标准Nim规则

游戏开始时设有n堆石子，第i堆有 $a_i$ 颗石子
两名玩家轮流操作
每次操作：选择一堆非空石子，从中取走任意正数颗（至少1颗，最多整堆）
取走最后一颗石子的玩家获胜（正常游戏规则）

必胜态与必败态

在组合博弈论中，状态可分为：
– N-position（Next player wins）：先手必胜态
– P-position（Previous player wins）：先手必败态

Bouton定理指出：Nim游戏的某个局面是P-position（先手必败），当且仅当所有堆的石子数异或和为0。即：

$$a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$$

基础Nim游戏的Java实现

import java.util.*;

/**
 * Nim游戏核心算法实现
 * 重点：SG函数、异或和判定、必胜策略生成
 */
public class NimGame {

    private int[] piles;
    private Random random;

    public NimGame(int[] initialPiles) {
        this.piles = Arrays.copyOf(initialPiles, initialPiles.length);
        this.random = new Random();
    }

    /**
     * 计算当前局面的异或和（nim-sum）
     * 若结果为0则为必败态，非0则为必胜态
     */
    public int calculateNimSum() {
        int xor = 0;
        for (int pile : piles) {
            xor ^= pile;
        }
        return xor;
    }

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

    /**
     * 寻找必胜策略：返回一个合法的获胜移动
     * 策略：找到最高位的1所在堆，将该堆减少到 pile XOR nimSum
     * @return int[]{堆索引, 取走后的剩余数量}，若无可行移动返回null
     */
    public int[] findWinningMove() {
        int nimSum = calculateNimSum();
        if (nimSum == 0) {
            return null; // 必败态，无必胜策略
        }

        for (int i = 0; i < piles.length; i++) {
            // 目标：使得该堆操作后，整体异或和变为0
            // 新数量 = piles[i] XOR nimSum
            int target = piles[i] ^ nimSum;
            if (target < piles[i]) {
                return new int[]{i, target};
            }
        }
        return null;
    }

    /**
     * 执行移动：从指定堆取石子至目标数量
     * @param pileIndex 堆索引
     * @param targetAmount 目标剩余数量
     * @return 实际取走的石子数
     */
    public int makeMove(int pileIndex, int targetAmount) {
        if (pileIndex < 0 || pileIndex >= piles.length) {
            throw new IllegalArgumentException("无效的堆索引");
        }
        if (targetAmount < 0 || targetAmount >= piles[pileIndex]) {
            throw new IllegalArgumentException("无效的目标数量");
        }

        int taken = piles[pileIndex] - targetAmount;
        piles[pileIndex] = targetAmount;
        return taken;
    }

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

    /**
     * AI玩家进行最优操作
     * @return 操作描述字符串
     */
    public String aiMove() {
        int[] move = findWinningMove();

        if (move != null) {
            int taken = makeMove(move[0], move[1]);
            return String.format("AI从第%d堆取走%d颗石子，剩余%d颗",
                move[0] + 1, taken, move[1]);
        } else {
            // 必败态：随机取走一颗石子
            List<Integer> nonEmpty = new ArrayList<>();
            for (int i = 0; i < piles.length; i++) {
                if (piles[i] > 0) nonEmpty.add(i);
            }
            int pileIdx = nonEmpty.get(random.nextInt(nonEmpty.size()));
            int taken = random.nextInt(piles[pileIdx]) + 1;
            int target = piles[pileIdx] - taken;
            makeMove(pileIdx, target);
            return String.format("AI（必败态）从第%d堆取走%d颗石子，剩余%d颗",
                pileIdx + 1, taken, target);
        }
    }

Sprague-Grundy函数理论

SG函数是组合博弈论的核心工具。对于每个游戏状态，定义其SG值为所有后继状态SG值的mex（最小非负整数排除值）：

$$g(x) = \text{mex}{g(y) \mid y \text{ 是 } x \text{ 的后继状态}}$$

其中 $\text{mex}(S) = \min{k \in \mathbb{N} \mid k \notin S}$

对于Nim的单堆情况，SG函数值恰好等于堆中石子数：$g(n) = n$

    /**
     * 计算单堆Nim的SG函数值
     * 对于标准Nim，SG(n) = n
     */
    public static int sgNimSingle(int n) {
        return n;
    }

    /**
     * 使用动态规划计算一般单堆游戏的SG函数
     * @param maxN 最大堆大小
     * @param moves 可执行的操作集合（表示每次可取走的数量）
     * @return SG函数值数组
     */
    public static int[] computeSgFunction(int maxN, int[] moves) {
        int[] sg = new int[maxN + 1];
        boolean[] seen = new boolean[maxN + 1];

        for (int i = 1; i <= maxN; i++) {
            Arrays.fill(seen, false);

            // 标记所有后继状态的SG值
            for (int move : moves) {
                if (i - move >= 0) {
                    seen[sg[i - move]] = true;
                }
            }

            // mex操作：找最小未出现的非负整数
            int g = 0;
            while (g <= maxN && seen[g]) {
                g++;
            }
            sg[i] = g;
        }

        return sg;
    }

Nim变种：限制每次取石数量

在Nim的变种中，每次最多只能取k颗石子。这种限制会改变SG函数的计算方式。

    /**
     * 限制取石数量的Nim游戏
     * 每次最多取maxTake颗石子
     */
    public static class BoundedNim {
        private int[] piles;
        private int maxTake;

        public BoundedNim(int[] piles, int maxTake) {
            this.piles = Arrays.copyOf(piles, piles.length);
            this.maxTake = maxTake;
        }

        /**
         * 计算限制取石数量的单堆SG值
         * SG(n) = n % (maxTake + 1)
         */
        public int calculateBoundedNimSum() {
            int xor = 0;
            for (int pile : piles) {
                xor ^= (pile % (maxTake + 1));
            }
            return xor;
        }

        /**
         * 寻找必胜移动（限制取石数量版本）
         */
        public int[] findWinningMove() {
            int nimSum = calculateBoundedNimSum();
            if (nimSum == 0) return null;

            for (int i = 0; i < piles.length; i++) {
                int currentMod = piles[i] % (maxTake + 1);
                int targetMod = currentMod ^ nimSum;

                // 需要调整取石数量使得新的mod等于targetMod
                int diff = currentMod - targetMod;
                if (diff > 0 && diff <= maxTake && diff <= piles[i]) {
                    return new int[]{i, piles[i] - diff};
                }
            }
            return null;
        }
    }

组合游戏：多子游戏的SG和

Sprague-Grundy定理的关键结论：多个独立子游戏的组合，其SG值等于各子游戏SG值的异或和。这正是Nim游戏中多堆石子异或判定胜负的理论基础。

    /**
     * 计算多个独立子游戏组合后的SG值
     * @param subGameSgs 各子游戏的SG值数组
     * @return 组合游戏的SG值
     */
    public static int combineSgValues(int[] subGameSgs) {
        int combined = 0;
        for (int sg : subGameSgs) {
            combined ^= sg;
        }
        return combined;
    }

    /**
     * 适用于复合Nim局面：每堆可能有不同的取石规则
     */
    public static class CompositeNim {
        private List<NimPile> piles;

        static class NimPile {
            int stones;
            int[] allowedMoves; // 该堆允许的取石数量

            NimPile(int stones, int[] allowedMoves) {
                this.stones = stones;
                this.allowedMoves = allowedMoves;
            }
        }

        public CompositeNim(List<NimPile> piles) {
            this.piles = piles;
        }

        /**
         * 计算整个局面的SG值
         * 每堆独立计算SG后异或
         */
        public int evaluate() {
            int totalXor = 0;
            for (NimPile pile : piles) {
                int maxN = pile.stones;
                int[] sgTable = computeSgFunction(maxN, pile.allowedMoves);
                totalXor ^= sgTable[maxN];
            }
            return totalXor;
        }
    }

完整可运行对战程序

    /**
     * 运行人机对战
     */
    public void playVsAI() {
        Scanner scanner = new Scanner(System.in);
        boolean playerTurn = true; // true=玩家先手

        System.out.println("=== Nim游戏 ===");
        System.out.println("初始石子堆: " + Arrays.toString(piles));
        System.out.println("初始Nim和: " + calculateNimSum());
        System.out.println();

        while (!isGameOver()) {
            System.out.println("当前石子堆: " + Arrays.toString(piles));

            if (playerTurn) {
                System.out.print("选择堆(1-" + piles.length + "): ");
                int pile = scanner.nextInt() - 1;
                System.out.print("取走后剩余数量: ");
                int target = scanner.nextInt();

                try {
                    int taken = makeMove(pile, target);
                    System.out.println("你取走了" + taken + "颗石子");
                } catch (Exception e) {
                    System.out.println("非法操作！" + e.getMessage());
                    continue;
                }
            } else {
                String action = aiMove();
                System.out.println("AI行动: " + action);
            }

            playerTurn = !playerTurn;
            System.out.println("Nim和: " + calculateNimSum());
            System.out.println();
        }

        System.out.println(playerTurn ? "AI获胜！" : "你获胜了！");
    }

    public static void main(String[] args) {
        // 经典局面：3堆石子 (3, 4, 5)
        // Nim和 = 3 XOR 4 XOR 5 = 2，为必胜态
        int[] initial = {3, 4, 5};
        NimGame game = new NimGame(initial);
        game.playVsAI();
    }
}

SG函数计算的可视化示例

以限制每次最多取3颗石子的Nim为例，SG值计算如下：

堆大小n	后继状态SG集合	mex运算	SG(n)
0	∅	mex(∅) = 0	0
1	{SG(0)} = {0}	mex({0}) = 1	1
2	{SG(1), SG(0)} = {1, 0}	mex({0,1}) = 2	2
3	{SG(2), SG(1), SG(0)} = {2, 1, 0}	mex({0,1,2}) = 3	3
4	{SG(3), SG(2), SG(1)} = {3, 2, 1}	mex({1,2,3}) = 0	0
5	{SG(4), SG(3), SG(2)} = {0, 3, 2}	mex({0,2,3}) = 1	1

可见SG值呈现周期为4的循环：$SG(n) = n \bmod 4$

算法复杂度分析

操作	时间复杂度	空间复杂度
Nim和计算	O(n)	O(1)
必胜策略查找	O(n)	O(1)
SG函数表构建	O(maxN × \|moves\|)	O(maxN)
多子游戏组合评估	O(k × maxN × \|moves\|)	O(k × maxN)

总结

Nim游戏是理解组合博弈论的绝佳入口。通过异或和判定胜负、SG函数刻画状态价值、Sprague-Grundy定理组合子游戏，我们构建了一套完整的博弈分析框架。Java实现中关键点在于：利用位运算高效计算nim-sum、通过mex运算构建SG函数表、将复杂局面分解为独立子问题后组合求解。这些思想不仅适用于Nim游戏，也是分析更复杂组合博弈（如Kayles、Grundy游戏）的基础工具。

Tagged with: Nim游戏 SG函数博弈论异或和组合游戏