猜数字（Bulls and Cows，又称 Mastermind 的简化版本）是经典的逻辑推理游戏：系统随机生成一个不重复数字的秘密序列，玩家每次猜测后获得”位置数字都对（A）”和”数字对位置不对（B）”的反馈。本文用 Java 实现基于决策树的最优猜测策略，讲解信息熵计算、最优属性选择与决策树剪枝的核心思想，使平均猜测次数逼近理论下界。
一、问题分析与信息论建模
1.1 游戏规则与状态空间
以 4 位不重复数字（0-9）为例，秘密数字共有 P(10,4) = 5040 种可能。每次猜测后，根据反馈 (A,B) 可以将候选集合大幅缩小。最优策略的目标是：每次猜测后，无论得到什么反馈，剩余候选集合的期望大小最小。
1.2 信息熵与最优猜测
信息熵衡量系统的不确定性。对于候选集合 S，猜测 g 的信息增益为：
Entropy(S) = -Σ p(c) × log₂(p(c))
Gain(S, g) = Entropy(S) - Σ (|S_v| / |S|) × Entropy(S_v)
其中 S_v 是得到反馈 v 后的候选子集。最优猜测是使信息增益最大（或等价地，使期望剩余候选数最小）的那个猜测。
1.3 决策树构建
将每次猜测视为决策树的一个节点，每个分支对应一种反馈结果。决策树的深度即为猜测次数。构建最优决策树等价于在每一步选择信息熵最小的分割点。
二、Java 实现
2.1 核心数据结构与工具类
import java.util.*;
/**
* 猜数字游戏：决策树最优策略实现
* 规则：4位不重复数字，反馈格式为 xAyB
*/
public class GuessNumberGame {
private static final int NUM_DIGITS = 4;
private static final int NUM_CHOICES = 10; // 0-9
/**
* 表示一次猜测的反馈结果
*/
public static class Feedback {
final int bulls; // 位置和数字都对（A）
final int cows; // 数字对位置不对（B）
public Feedback(int bulls, int cows) {
this.bulls = bulls;
this.cows = cows;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Feedback)) return false;
Feedback other = (Feedback) o;
return bulls == other.bulls && cows == other.cows;
}
@Override
public int hashCode() {
return bulls * 10 + cows;
}
@Override
public String toString() {
return bulls + "A" + cows + "B";
}
}
/**
* 计算猜测 guess 对于秘密 secret 的反馈
*/
public static Feedback getFeedback(int[] secret, int[] guess) {
int bulls = 0, cows = 0;
boolean[] secretUsed = new boolean[NUM_DIGITS];
boolean[] guessUsed = new boolean[NUM_DIGITS];
// 先计算 bulls
for (int i = 0; i < NUM_DIGITS; i++) {
if (guess[i] == secret[i]) {
bulls++;
secretUsed[i] = true;
guessUsed[i] = true;
}
}
// 再计算 cows
for (int i = 0; i < NUM_DIGITS; i++) {
if (guessUsed[i]) continue;
for (int j = 0; j < NUM_DIGITS; j++) {
if (secretUsed[j]) continue;
if (guess[i] == secret[j]) {
cows++;
secretUsed[j] = true;
break;
}
}
}
return new Feedback(bulls, cows);
}
/**
* 生成所有可能的候选数字（4位不重复）
*/
public static List<int[]> generateAllCandidates() {
List<int[]> candidates = new ArrayList<>();
int[] digits = new int[NUM_DIGITS];
generateCandidatesHelper(candidates, digits, 0, new boolean[NUM_CHOICES]);
return candidates;
}
private static void generateCandidatesHelper(List<int[]> candidates, int[] digits, int pos, boolean[] used) {
if (pos == NUM_DIGITS) {
candidates.add(digits.clone());
return;
}
for (int d = 0; d < NUM_CHOICES; d++) {
if (used[d]) continue;
used[d] = true;
digits[pos] = d;
generateCandidatesHelper(candidates, digits, pos + 1, used);
used[d] = false;
}
}
/**
* 将数字数组转换为整数表示，便于显示
*/
public static int digitsToInt(int[] digits) {
int result = 0;
for (int d : digits) {
result = result * 10 + d;
}
return result;
}
public static void main(String[] args) {
// 测试反馈计算
int[] secret = {1, 2, 3, 4};
int[] guess1 = {1, 2, 3, 4};
int[] guess2 = {5, 6, 7, 8};
int[] guess3 = {1, 3, 2, 4};
System.out.println("秘密: 1234");
System.out.println("猜测 1234 -> " + getFeedback(secret, guess1));
System.out.println("猜测 5678 -> " + getFeedback(secret, guess2));
System.out.println("猜测 1324 -> " + getFeedback(secret, guess3));
}
}
2.2 信息熵最优策略引擎
import java.util.*;
/**
* 基于信息熵的最优猜测策略
* 每次选择使期望剩余候选集合最小的猜测
*/
public class EntropyStrategy {
private static final int NUM_DIGITS = 4;
private List<int[]> allCandidates;
private Random random;
public EntropyStrategy() {
this.allCandidates = GuessNumberGame.generateAllCandidates();
this.random = new Random();
System.out.println("候选空间大小: " + allCandidates.size());
}
/**
* 根据当前候选集合，计算每个可能猜测的信息熵
* 返回使期望剩余候选数最小的猜测
*/
public int[] findBestGuess(List<int[]> candidates) {
if (candidates.size() <= 1) {
return candidates.get(0);
}
double minExpectedSize = Double.MAX_VALUE;
int[] bestGuess = null;
int evaluated = 0;
// 评估所有可能的猜测（包括不在候选集中的猜测，称为"试探性猜测"）
List<int[]> guessPool = allCandidates;
for (int[] guess : guessPool) {
// 统计该猜测下各种反馈对应的候选子集大小
Map<GuessNumberGame.Feedback, Integer> feedbackCount = new HashMap<>();
for (int[] candidate : candidates) {
GuessNumberGame.Feedback fb = GuessNumberGame.getFeedback(candidate, guess);
feedbackCount.merge(fb, 1, Integer::sum);
}
// 计算期望剩余候选数
double expectedSize = 0;
for (int count : feedbackCount.values()) {
double p = (double) count / candidates.size();
expectedSize += p * count;
}
// 优先选择候选集中的猜测，若期望大小相同
boolean inCandidates = false;
for (int[] c : candidates) {
if (Arrays.equals(c, guess)) {
inCandidates = true;
break;
}
}
// 选择期望剩余候选数最小的猜测
// 若相同，优先选择仍在候选集中的猜测
if (expectedSize < minExpectedSize ||
(expectedSize == minExpectedSize && inCandidates)) {
minExpectedSize = expectedSize;
bestGuess = guess;
}
evaluated++;
}
return bestGuess;
}
/**
* 计算信息熵（用于分析）
*/
public double calculateEntropy(List<int[]> candidates) {
if (candidates.isEmpty()) return 0;
// 均匀分布的熵
return Math.log(candidates.size()) / Math.log(2);
}
/**
* 使用最优策略解决一局游戏
* @param secret 秘密数字（用于模拟）
* @return 猜测历史记录
*/
public List<String> solve(int[] secret) {
List<int[]> candidates = new ArrayList<>(allCandidates);
List<String> history = new ArrayList<>();
int attempts = 0;
final int MAX_ATTEMPTS = 10;
// 初始猜测：信息论研究表明 0123 是一个较好的初始猜测
int[] guess = {0, 1, 2, 3};
while (attempts < MAX_ATTEMPTS) {
attempts++;
GuessNumberGame.Feedback fb = GuessNumberGame.getFeedback(secret, guess);
history.add(String.format("第%d次: %04d -> %s (候选数: %d)",
attempts, GuessNumberGame.digitsToInt(guess), fb, candidates.size()));
if (fb.bulls == NUM_DIGITS) {
history.add("破解成功！共猜测 " + attempts + " 次");
break;
}
// 根据反馈过滤候选集合
List<int[]> newCandidates = new ArrayList<>();
for (int[] candidate : candidates) {
if (GuessNumberGame.getFeedback(candidate, guess).equals(fb)) {
newCandidates.add(candidate);
}
}
candidates = newCandidates;
// 选择下一个最优猜测
guess = findBestGuess(candidates);
}
return history;
}
/**
* 大规模统计：测试所有可能的秘密数字，计算平均猜测次数
*/
public void benchmark() {
int totalAttempts = 0;
int maxAttempts = 0;
Map<Integer, Integer> distribution = new TreeMap<>();
for (int[] secret : allCandidates) {
List<String> result = solve(secret);
int attempts = result.size() - 1; // 减去最后的成功消息
totalAttempts += attempts;
maxAttempts = Math.max(maxAttempts, attempts);
distribution.merge(attempts, 1, Integer::sum);
}
double average = (double) totalAttempts / allCandidates.size();
System.out.println("\n=== 策略性能统计 ===");
System.out.printf("平均猜测次数: %.3f%n", average);
System.out.println("最大猜测次数: " + maxAttempts);
System.out.println("猜测次数分布:");
for (Map.Entry<Integer, Integer> entry : distribution.entrySet()) {
System.out.printf(" %d 次: %d 个 (%.2f%%)%n",
entry.getKey(), entry.getValue(),
100.0 * entry.getValue() / allCandidates.size());
}
}
public static void main(String[] args) {
EntropyStrategy strategy = new EntropyStrategy();
// 演示一局
int[] secret = {5, 7, 2, 9};
System.out.println("秘密数字: " + GuessNumberGame.digitsToInt(secret));
System.out.println("\n解题过程:");
List<String> history = strategy.solve(secret);
for (String line : history) {
System.out.println(" " + line);
}
// 完整基准测试（可选，运行时间较长）
// strategy.benchmark();
}
}
2.3 决策树节点与可视化
import java.util.*;
/**
* 决策树节点：用于构建和展示最优猜测策略树
*/
public class DecisionTreeNode {
int[] guess; // 当前节点的猜测
GuessNumberGame.Feedback feedback; // 到达该节点的反馈（根节点为null）
List<DecisionTreeNode> children;
boolean isLeaf;
int[] answer; // 若是叶子节点，记录确定的答案
int depth; // 节点深度
public DecisionTreeNode(int[] guess, int depth) {
this.guess = guess;
this.depth = depth;
this.children = new ArrayList<>();
this.isLeaf = false;
}
/**
* 递归构建决策树
* @param candidates 当前候选集合
* @param allPossible 所有可能的数字组合
*/
public static DecisionTreeNode buildTree(List<int[]> candidates,
List<int[]> allPossible,
int depth) {
if (candidates.size() == 1) {
DecisionTreeNode leaf = new DecisionTreeNode(candidates.get(0), depth);
leaf.isLeaf = true;
leaf.answer = candidates.get(0);
return leaf;
}
// 使用信息熵策略选择最优猜测
EntropyStrategy strategy = new EntropyStrategy();
int[] bestGuess = strategy.findBestGuess(candidates);
DecisionTreeNode node = new DecisionTreeNode(bestGuess, depth);
// 按反馈分组
Map<GuessNumberGame.Feedback, List<int[]>> groups = new HashMap<>();
for (int[] candidate : candidates) {
GuessNumberGame.Feedback fb = GuessNumberGame.getFeedback(candidate, bestGuess);
groups.computeIfAbsent(fb, k -> new ArrayList<>()).add(candidate);
}
// 为每种反馈构建子树
for (Map.Entry<GuessNumberGame.Feedback, List<int[]>> entry : groups.entrySet()) {
DecisionTreeNode child = buildTree(entry.getValue(), allPossible, depth + 1);
child.feedback = entry.getKey();
node.children.add(child);
}
return node;
}
/**
* 打印决策树结构（简化版）
*/
public void printTree(String indent) {
if (isLeaf) {
System.out.println(indent + "[叶子] 答案: " + GuessNumberGame.digitsToInt(answer));
return;
}
System.out.println(indent + "[节点] 猜测: " + GuessNumberGame.digitsToInt(guess));
for (DecisionTreeNode child : children) {
System.out.println(indent + " -> 反馈 " + child.feedback + ":");
child.printTree(indent + " ");
}
}
/**
* 计算树的最大深度和平均深度
*/
public int getMaxDepth() {
if (isLeaf) return depth;
int max = 0;
for (DecisionTreeNode child : children) {
max = Math.max(max, child.getMaxDepth());
}
return max;
}
public static void main(String[] args) {
List<int[]> all = GuessNumberGame.generateAllCandidates();
// 构建完整的决策树需要大量内存和时间，这里仅演示小规模
List<int[]> subset = all.subList(0, 24);
System.out.println("构建决策树（24个候选的子集）...");
DecisionTreeNode root = DecisionTreeNode.buildTree(subset, all, 0);
System.out.println("树的最大深度: " + root.getMaxDepth());
System.out.println("\n决策树结构:");
root.printTree("");
}
}
三、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 生成候选空间 | O(P(10,4)) = O(5040) | O(5040) | 一次性预处理 |
| 计算反馈 | O(k²) = O(16) | O(1) | k=4 位数字 |
| 单次最优猜测 | O(|S| × 5040) | O(反馈种类数) | |S| 为当前候选数 |
| 完整解题 | O( attempts × |S| × 5040 ) | O(|S|) | 通常 attempts ≤ 7 |
| 构建完整决策树 | O(5040² × 5040) | O(树节点数) | 理论上，实际需剪枝优化 |
四、策略对比与优化
| 策略 | 平均猜测次数 | 最大猜测次数 | 计算开销 |
|---|---|---|---|
| 随机猜测 | ~5.2 | >10 | 极低 |
| 简单启发式 | ~4.8 | 8 | 低 |
| 信息熵最小化 | ~4.34 | 6-7 | 高 |
| 最小最大（Knuth） | ~4.47 | 5 | 极高 |
信息熵策略的平均表现最优，但最小最大策略能保证最坏情况下不超过 5 次猜测。实际工程中可根据场景在平均性能和最坏保证之间取舍。
五、总结
本文从信息论视角出发，将猜数字游戏建模为决策树构建问题。通过信息熵量化不确定性，每次选择使期望剩余候选集合最小的猜测，实现了接近理论最优的求解策略。Java 实现涵盖候选空间生成、反馈计算、信息熵评估和决策树递归构建等完整模块，读者可以在此基础上扩展到 5 位数字、含重复数字等变体场景，或引入并行计算加速大规模策略评估。
