每日算法 — 使用java实现猜数字：二分搜索与信息论最优猜测

猜数字（Bulls and Cows / Mastermind变体）是一款经典的逻辑推理游戏：系统生成一个不含重复数字的N位数，玩家每次猜测后会得到反馈——”A”表示数字和位置都正确，”B”表示数字正确但位置错误。本文用Java实现一个AI猜数字求解器，核心讲解如何利用二分搜索思想与信息论熵减策略，以最少次数猜中目标。

信息论建模

猜数字的本质是从候选解空间中寻找目标。对于4位不重复数字（0-9），候选空间大小为10×9×8×7=5040。每次猜测的反馈（如1A2B）将空间划分为多个子集，AI的目标是让每次猜测后剩余候选数最少——这正是信息增益最大化问题。

信息论告诉我们：最优猜测是让各种反馈结果尽可能均衡分布，从而使期望信息增益最大。Shannon熵定义为H = -Σpᵢlog₂(pᵢ)，均衡分布时熵最大，不确定性消除最多。

两种策略实现

策略一：最小最大（Knuth算法）

对每一个可能的猜测，模拟所有可能的反馈结果，计算最坏情况下剩余候选数的最大值，选择这个最大值最小的猜测。

策略二：熵最大化（信息论最优）

计算每个猜测的反馈分布熵，选择期望熵最大的猜测，让每次猜测平均消除最多的不确定性。

Java 实现

import java.util.*;

public class GuessNumberAI {
    private final int digits; // 数字位数
    private final boolean allowDuplicate;
    private List<String> candidates = new ArrayList<>();
    private Random rand = new Random();

    public GuessNumberAI(int digits, boolean allowDuplicate) {
        this.digits = digits;
        this.allowDuplicate = allowDuplicate;
        generateAllCandidates();
    }

    // 生成所有可能的候选解
    private void generateAllCandidates() {
        generateCandidates(new StringBuilder(), new boolean[10]);
    }

    private void generateCandidates(StringBuilder sb, boolean[] used) {
        if (sb.length() == digits) {
            candidates.add(sb.toString());
            return;
        }
        for (int d = 0; d <= 9; d++) {
            if (!allowDuplicate && used[d]) continue;
            sb.append(d);
            used[d] = true;
            generateCandidates(sb, used);
            used[d] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    // 计算猜测与目标的反馈 (A,B)
    public static int[] calculateFeedback(String guess, String target) {
        int a = 0, b = 0;
        boolean[] guessUsed = new boolean[digits];
        boolean[] targetUsed = new boolean[digits];

        // 先统计位置正确的A
        for (int i = 0; i < digits; i++) {
            if (guess.charAt(i) == target.charAt(i)) {
                a++; guessUsed[i] = targetUsed[i] = true;
            }
        }
        // 再统计数字正确但位置错误的B
        for (int i = 0; i < digits; i++) {
            if (guessUsed[i]) continue;
            for (int j = 0; j < digits; j++) {
                if (targetUsed[j]) continue;
                if (guess.charAt(i) == target.charAt(j)) {
                    b++; guessUsed[i] = targetUsed[j] = true; break;
                }
            }
        }
        return new int[]{a, b};
    }

    // 根据反馈过滤候选解
    public void filterCandidates(String guess, int a, int b) {
        List<String> filtered = new ArrayList<>();
        for (String c : candidates) {
            int[] fb = calculateFeedback(guess, c);
            if (fb[0] == a && fb[1] == b) filtered.add(c);
        }
        candidates = filtered;
    }

    // 最小最大策略：选择最坏情况下剩余候选数最少的猜测
    public String minmaxGuess() {
        String bestGuess = candidates.get(0);
        int minMaxRemaining = Integer.MAX_VALUE;

        for (String guess : candidates) {
            Map<String, Integer> distribution = new HashMap<>();
            for (String target : candidates) {
                int[] fb = calculateFeedback(guess, target);
                String key = fb[0] + "A" + fb[1] + "B";
                distribution.merge(key, 1, Integer::sum);
            }
            int maxRemaining = Collections.max(distribution.values());
            if (maxRemaining < minMaxRemaining) {
                minMaxRemaining = maxRemaining;
                bestGuess = guess;
            }
        }
        return bestGuess;
    }

    // 熵最大化策略：选择期望信息增益最大的猜测
    public String entropyGuess() {
        String bestGuess = candidates.get(0);
        double maxEntropy = -1;

        for (String guess : candidates) {
            Map<String, Integer> distribution = new HashMap<>();
            for (String target : candidates) {
                int[] fb = calculateFeedback(guess, target);
                String key = fb[0] + "A" + fb[1] + "B";
                distribution.merge(key, 1, Integer::sum);
            }
            double entropy = 0;
            int total = candidates.size();
            for (int count : distribution.values()) {
                double p = (double) count / total;
                entropy -= p * Math.log(p) / Math.log(2);
            }
            if (entropy > maxEntropy) {
                maxEntropy = entropy;
                bestGuess = guess;
            }
        }
        return bestGuess;
    }

    // 模拟AI猜测过程
    public int solve(String target, boolean useEntropy) {
        candidates.clear();
        generateAllCandidates();
        int steps = 0;
        String guess = "0123".substring(0, Math.min(digits, 4)); // 初始猜测
        if (digits == 4) guess = "0123"; // 经典4位猜数字优化初始值

        while (true) {
            steps++;
            int[] fb = calculateFeedback(guess, target);
            System.out.println("Step " + steps + ": guess " + guess + " -> " + fb[0] + "A" + fb[1] + "B");
            if (fb[0] == digits) break;

            filterCandidates(guess, fb[0], fb[1]);
            System.out.println("  Remaining candidates: " + candidates.size());

            guess = useEntropy ? entropyGuess() : minmaxGuess();
        }
        return steps;
    }

    public static void main(String[] args) {
        GuessNumberAI ai = new GuessNumberAI(4, false);
        String target = "5283"; // 目标数字

        System.out.println("=== Minimax Strategy ===");
        int steps1 = ai.solve(target, false);
        System.out.println("Solved in " + steps1 + " steps\n");

        System.out.println("=== Entropy Strategy ===");
        int steps2 = ai.solve(target, true);
        System.out.println("Solved in " + steps2 + " steps");
    }
}

复杂度分析

• 时间复杂度：每次猜测需要O(C²)计算所有候选对的反馈分布，C为当前候选数。4位数字通常5-6步内解决，每步最多5040²≈2500万次比较，实际可用哈希优化。
• 空间复杂度：O(C)存储候选解列表。

策略对比与最优性

对于标准4位猜数字（数字不重复）：

最小最大策略保证最坏情况最优（Knuth证明5步内必解），而熵最大化策略在平均表现上略优。两者均远优于人类玩家的直觉猜测。

扩展应用

猜数字的信息论框架可推广至：Wordle（5字母单词猜测）、Mastermind（颜色 peg 组合）、以及各类主动学习场景——AI通过提问逐步缩小假设空间，这在医学诊断、故障排查等决策系统中有着广泛应用。