每日算法 — 使用java实现Mastermind：Knuth最小最大算法与信息论最优猜测

Mastermind（色彩密码）是一款经典的逻辑推理桌游：一方设置一个由4个彩色 peg 组成的秘密代码，另一方通过有限次数的猜测来破解它。每次猜测后，会获得两种反馈——黑色 peg（颜色和位置都正确）和白色 peg（颜色正确但位置错误）。1977年，Donald Knuth 证明了该游戏可以在最多5次猜测内解决。本文将用Java实现 Mastermind 的AI求解器，深入讲解 Knuth 的最小最大算法与信息论视角下的最优猜测策略。

一、游戏规则与状态空间

秘密代码由4个位置组成，每个位置可以是6种颜色之一（允许重复）。总状态空间为 6⁴ = 1296 种可能。

public class MastermindConfig {
    public static final int CODE_LENGTH = 4;
    public static final int NUM_COLORS = 6;
    public static final char[] COLORS = {'R', 'G', 'B', 'Y', 'W', 'K'}; // 红绿蓝黄白黑
}

二、反馈计算

对于猜测代码 G 和秘密代码 S，反馈 (black, white) 的计算逻辑如下：

public class Feedback {
    private final int black; // 位置颜色都正确
    private final int white; // 颜色正确位置错误

    public static Feedback evaluate(char[] guess, char[] secret) {
        int black = 0;
        int white = 0;
        boolean[] guessUsed = new boolean[CODE_LENGTH];
        boolean[] secretUsed = new boolean[CODE_LENGTH];

        // 先统计 black（位置和颜色都匹配）
        for (int i = 0; i < CODE_LENGTH; i++) {
            if (guess[i] == secret[i]) {
                black++;
                guessUsed[i] = true;
                secretUsed[i] = true;
            }
        }

        // 再统计 white（颜色匹配但位置不同）
        for (int i = 0; i < CODE_LENGTH; i++) {
            if (guessUsed[i]) continue;
            for (int j = 0; j < CODE_LENGTH; j++) {
                if (secretUsed[j]) continue;
                if (guess[i] == secret[j]) {
                    white++;
                    secretUsed[j] = true;
                    break;
                }
            }
        }

        return new Feedback(black, white);
    }
}

三、Knuth 最小最大算法

Knuth 算法的核心思想是：每次猜测后，根据反馈将所有可能的秘密代码划分为若干等价类。选择能够将最大等价类最小化的猜测，从而保证无论得到什么反馈，剩余的可能性都尽可能少。

public class KnuthSolver {
    private List<char[]> possibleCodes; // 当前所有可能的秘密代码
    private List<char[]> allCodes;      // 全部1296种代码

    public KnuthSolver() {
        allCodes = generateAllCodes();
        possibleCodes = new ArrayList<>(allCodes);
    }

    public char[] makeGuess() {
        if (possibleCodes.size() == 1) {
            return possibleCodes.get(0); // 唯一解
        }

        // 特殊情况：第一次猜测固定为 AABC 模式（最优首猜）
        if (possibleCodes.size() == allCodes.size()) {
            return new char[]{'R', 'R', 'G', 'B'}; // 1123 模式
        }

        char[] bestGuess = null;
        int minMaxSize = Integer.MAX_VALUE;

        // 遍历所有可能的猜测（不仅限于 possibleCodes，也包括已排除的代码）
        for (char[] guess : allCodes) {
            // 计算该猜测下，各种反馈对应的等价类大小
            Map<Feedback, Integer> partitionSizes = new HashMap<>();

            for (char[] possible : possibleCodes) {
                Feedback fb = Feedback.evaluate(guess, possible);
                partitionSizes.merge(fb, 1, Integer::sum);
            }

            // 最小最大准则：关注最大等价类的大小
            int maxPartition = partitionSizes.values().stream()
                .max(Integer::compare)
                .orElse(0);

            // 优先选择可能解空间内的猜测，其次才选非可能解的猜测
            boolean isPossible = isInPossibleCodes(guess);

            // 更新最优猜测
            if (maxPartition < minMaxSize || 
                (maxPartition == minMaxSize && isPossible && !isInPossibleCodes(bestGuess))) {
                minMaxSize = maxPartition;
                bestGuess = guess.clone();
            }
        }

        return bestGuess;
    }

    public void update(Feedback feedback, char[] guess) {
        // 根据反馈过滤可能的秘密代码
        possibleCodes.removeIf(code -> !Feedback.evaluate(guess, code).equals(feedback));
    }
}

四、信息论视角：熵最大化策略

除了最小最大准则，还可以从信息论角度选择每次猜测——最大化期望信息增益（即最小化条件熵）。

public char[] makeEntropyGuess() {
    char[] bestGuess = null;
    double maxEntropy = -1;

    for (char[] guess : allCodes) {
        Map<Feedback, Integer> partition = new HashMap<>();
        for (char[] possible : possibleCodes) {
            Feedback fb = Feedback.evaluate(guess, possible);
            partition.merge(fb, 1, Integer::sum);
        }

        // 计算该猜测的期望信息增益（熵）
        double entropy = 0.0;
        int total = possibleCodes.size();
        for (int count : partition.values()) {
            if (count > 0) {
                double p = (double) count / total;
                entropy -= p * Math.log(p) / Math.log(2);
            }
        }

        if (entropy > maxEntropy) {
            maxEntropy = entropy;
            bestGuess = guess.clone();
        }
    }

    return bestGuess;
}

五、求解器主循环

public class MastermindGame {
    public static void solve(char[] secret) {
        KnuthSolver solver = new KnuthSolver();
        int attempts = 0;

        while (true) {
            char[] guess = solver.makeGuess();
            attempts++;

            Feedback fb = Feedback.evaluate(guess, secret);
            System.out.printf("Attempt %d: %s -> %s%n", 
                attempts, new String(guess), fb);

            if (fb.getBlack() == MastermindConfig.CODE_LENGTH) {
                System.out.println("Solved in " + attempts + " attempts!");
                break;
            }

            solver.update(fb, guess);
        }
    }
}

六、性能对比

Knuth 的最小最大算法保证在5步内解决，而熵最大化策略平均步数更少但最坏情况略差。

七、总结

Mastermind 求解器展示了约束传播与信息论在组合搜索中的威力。Knuth 的最小最大算法通过系统性地评估每个猜测的”最坏情况表现”来保证求解效率，而熵最大化策略则在平均意义上更优。两种方法的核心都是将庞大的状态空间通过反馈逐步缩小，这与现代约束满足问题（CSP）的求解思路一脉相承。