色彩密码（Mastermind，又称 Bulls and Cows）是一款经典的逻辑推理桌游。游戏规则简洁：一方设定一个由若干颜色组成的秘密序列，另一方通过逐轮猜测并接收反馈来破解它。每次反馈告知猜测中有多少个颜色位置完全正确（公牛），以及有多少个颜色正确但位置错误（奶牛）。本文将用 Java 完整实现这一游戏，并重点讲解 Donald Knuth 提出的最小最大算法（Minimax Algorithm），以及基于信息熵的最优猜测策略。
一、游戏规则与问题建模
在标准色彩密码中，假设有 6 种不同颜色，秘密序列长度为 4，且颜色允许重复。所有可能的秘密序列总数为：
$$
6^4 = 1296
$$
每次猜测后，系统返回一个 (bulls, cows) 反馈：
– bulls（公牛）：颜色和位置都正确的数量
– cows（奶牛）：颜色正确但位置错误的数量
例如，秘密序列是 [红, 蓝, 绿, 黄]，猜测为 [红, 绿, 蓝, 黄]，则反馈为 bulls=2（红和黄位置对），cows=2（蓝和绿颜色对但位置错）。
核心算法问题
给定当前所有可能的候选答案集合，如何选择下一轮的最优猜测，使得在最坏情况下所需的猜测次数最少？这正是 Knuth 最小最大算法要解决的核心问题。
二、Knuth 最小最大算法原理
Knuth 于 1976 年在《计算机科学与博弈论》中证明：对于标准 6 色 4 位的 Mastermind，存在一个确定性策略，保证在 5 次猜测内破解任何秘密序列。
算法思想
设当前候选集为 $S$（所有尚未被排除的可能秘密）。对于每一个可能的猜测 $g$（通常遍历全部 $1296$ 种组合，不限于候选集），我们模拟：如果真实秘密是 $S$ 中的某个元素，对猜测 $g$ 会产生什么反馈？根据反馈，$S$ 会被划分为若干子集。算法选择使得最大子集最小的猜测 $g$。
形式化描述：
$$
g^* = \arg\min_{g} \max_{(bulls, cows)} |S_{(bulls, cows)}^g|
$$
其中 $S_{(bulls, cows)}^g$ 表示候选集 $S$ 中，对猜测 $g$ 产生反馈 $(bulls, cows)$ 的所有秘密。
与信息熵的联系
最小最大算法侧重于最坏情况优化。另一个视角是信息论：每次猜测应最大化期望信息增益（即最小化反馈的不确定性）。Shannon 信息熵定义为：
$$
H = -\sum_{i} p_i \log_2 p_i
$$
选择猜测 $g$ 使得反馈分布的熵最大，意味着平均而言每次猜测获得的信息量最多。实际工程中，熵策略往往比纯最小最大策略的平均步数更优，但最小最大策略能保证最坏情况下步数的上界。
三、核心算法模块设计
我们采用模块化设计，将游戏拆分为以下核心组件：
Code：表示一个颜色序列，提供 Bulls/Cows 计算Feedback：封装反馈结果KnuthSolver：核心求解器，实现最小最大算法MastermindGame：游戏主控，串联人机交互
3.1 颜色序列与反馈计算
计算 Bulls 和 Cows 是算法的基础。关键在于正确处理重复颜色：先统计位置完全匹配的 Bulls，再对剩余颜色统计 Cows。
/**
* 表示一个色彩密码序列
*/
public class Code {
private final int[] colors; // 颜色编码，0~5 分别代表六种颜色
private final int length;
private final int colorRange;
public Code(int[] colors, int colorRange) {
this.colors = colors.clone();
this.length = colors.length;
this.colorRange = colorRange;
}
/**
* 计算当前序列与目标序列的 Bulls 和 Cows
* bulls: 位置和颜色都正确
* cows: 颜色正确但位置错误
*/
public Feedback compareTo(Code other) {
int bulls = 0;
int cows = 0;
int[] freqSelf = new int[colorRange];
int[] freqOther = new int[colorRange];
// 第一轮：统计 bulls
for (int i = 0; i < length; i++) {
if (this.colors[i] == other.colors[i]) {
bulls++;
} else {
freqSelf[this.colors[i]]++;
freqOther[other.colors[i]]++;
}
}
// 第二轮：统计 cows（取两种颜色剩余数量的最小值）
for (int c = 0; c < colorRange; c++) {
cows += Math.min(freqSelf[c], freqOther[c]);
}
return new Feedback(bulls, cows);
}
public int[] getColors() {
return colors.clone();
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
String[] colorNames = {"红", "橙", "黄", "绿", "蓝", "紫"};
for (int i = 0; i < length; i++) {
sb.append(colorNames[colors[i]]);
if (i < length - 1) sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
/**
* 封装猜测反馈结果
*/
public class Feedback {
public final int bulls;
public final int cows;
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 this.bulls == other.bulls && this.cows == other.cows;
}
@Override
public int hashCode() {
return bulls * 31 + cows;
}
@Override
public String toString() {
return String.format("(bulls=%d, cows=%d)", bulls, cows);
}
}
3.2 Knuth 最小最大求解器
求解器维护一个候选集 candidates，每次根据反馈过滤不可能的答案，然后用最小最大原则选择下一轮最优猜测。
import java.util.*;
/**
* Knuth 最小最大算法求解器
* 核心思想：选择使得最坏情况下剩余候选数最少的猜测
*/
public class KnuthSolver {
private final int codeLength; // 序列长度（默认 4）
private final int colorRange; // 颜色种类（默认 6）
private List<Code> allCodes; // 所有可能的序列（6^4 = 1296）
private List<Code> candidates; // 当前候选集
public KnuthSolver(int codeLength, int colorRange) {
this.codeLength = codeLength;
this.colorRange = colorRange;
generateAllCodes();
this.candidates = new ArrayList<>(allCodes);
}
/**
* 生成所有可能的色彩序列
* 使用递归回溯生成笛卡尔积
*/
private void generateAllCodes() {
allCodes = new ArrayList<>();
int[] current = new int[codeLength];
backtrack(0, current);
}
private void backtrack(int pos, int[] current) {
if (pos == codeLength) {
allCodes.add(new Code(current.clone(), colorRange));
return;
}
for (int c = 0; c < colorRange; c++) {
current[pos] = c;
backtrack(pos + 1, current);
}
}
/**
* 根据猜测和反馈过滤候选集
* 仅保留那些对当前猜测能产生相同反馈的秘密序列
*/
public void filterCandidates(Code guess, Feedback feedback) {
List<Code> newCandidates = new ArrayList<>();
for (Code candidate : candidates) {
if (candidate.compareTo(guess).equals(feedback)) {
newCandidates.add(candidate);
}
}
candidates = newCandidates;
}
/**
* 使用最小最大算法选择最优猜测
* 对每个可能的猜测，计算在所有反馈下最坏情况的剩余候选数
* 选择使该最大值最小的猜测
*/
public Code findBestGuess() {
if (candidates.size() == 1) {
return candidates.get(0);
}
Code bestGuess = null;
int minMaxRemaining = Integer.MAX_VALUE;
// 遍历所有可能的猜测（不限于候选集，Knuth 证明这更优）
for (Code guess : allCodes) {
// 按反馈分组，统计每组的大小
Map<Feedback, Integer> feedbackCount = new HashMap<>();
for (Code candidate : candidates) {
Feedback fb = candidate.compareTo(guess);
feedbackCount.merge(fb, 1, Integer::sum);
}
// 找出最坏情况（最大分组）
int maxRemaining = 0;
for (int count : feedbackCount.values()) {
maxRemaining = Math.max(maxRemaining, count);
}
// 平局优先策略：
// 1. 优先选择 maxRemaining 更小的
// 2. 若相同，优先选择属于候选集的猜测
// 3. 若仍相同，保持第一个
boolean isInCandidates = candidates.contains(guess);
boolean better = false;
if (maxRemaining < minMaxRemaining) {
better = true;
} else if (maxRemaining == minMaxRemaining) {
if (bestGuess == null) {
better = true;
} else {
boolean bestInCandidates = candidates.contains(bestGuess);
if (isInCandidates && !bestInCandidates) {
better = true;
}
}
}
if (better) {
minMaxRemaining = maxRemaining;
bestGuess = guess;
}
}
return bestGuess;
}
/**
* 基于信息熵的策略：选择使反馈熵最大的猜测
* 信息熵越大，平均每次猜测获得的信息量越多
*/
public Code findBestGuessByEntropy() {
if (candidates.size() == 1) {
return candidates.get(0);
}
Code bestGuess = null;
double maxEntropy = -1.0;
for (Code guess : allCodes) {
Map<Feedback, Integer> feedbackCount = new HashMap<>();
for (Code candidate : candidates) {
Feedback fb = candidate.compareTo(guess);
feedbackCount.merge(fb, 1, Integer::sum);
}
// 计算熵: H = -sum(p_i * log2(p_i))
double entropy = 0.0;
int total = candidates.size();
for (int count : feedbackCount.values()) {
if (count > 0) {
double p = (double) count / total;
entropy -= p * (Math.log(p) / Math.log(2));
}
}
boolean isInCandidates = candidates.contains(guess);
boolean better = false;
if (entropy > maxEntropy + 1e-9) {
better = true;
} else if (Math.abs(entropy - maxEntropy) < 1e-9) {
if (bestGuess == null || (isInCandidates && !candidates.contains(bestGuess))) {
better = true;
}
}
if (better) {
maxEntropy = entropy;
bestGuess = guess;
}
}
return bestGuess;
}
public List<Code> getCandidates() {
return candidates;
}
public void reset() {
this.candidates = new ArrayList<>(allCodes);
}
}
3.3 游戏主控与自动破解演示
import java.util.*;
/**
* Mastermind 游戏主控类
* 支持人机对战和 AI 自动破解两种模式
*/
public class MastermindGame {
private static final int CODE_LENGTH = 4;
private static final int COLOR_RANGE = 6;
private static final String[] COLOR_NAMES = {"红", "橙", "黄", "绿", "蓝", "紫"};
public static void main(String[] args) {
System.out.println("=== 色彩密码 (Mastermind) ===");
System.out.println("颜色: 红(0) 橙(1) 黄(2) 绿(3) 蓝(4) 紫(5)");
System.out.println("规则: 猜一个 4 位颜色序列，颜色可重复");
System.out.println();
// 演示模式：AI 自动破解随机生成的秘密序列
demoAutoSolve(10);
}
/**
* 演示 AI 自动破解多个随机秘密
*/
private static void demoAutoSolve(int rounds) {
Random random = new Random(42); // 固定种子保证可复现
KnuthSolver solver = new KnuthSolver(CODE_LENGTH, COLOR_RANGE);
int totalSteps = 0;
int maxSteps = 0;
System.out.println("--- AI 自动破解演示 ---\n");
for (int r = 0; r < rounds; r++) {
// 生成随机秘密
int[] secretColors = new int[CODE_LENGTH];
for (int i = 0; i < CODE_LENGTH; i++) {
secretColors[i] = random.nextInt(COLOR_RANGE);
}
Code secret = new Code(secretColors, COLOR_RANGE);
solver.reset();
System.out.printf("第 %d 轮 - 秘密序列: %s%n", r + 1, secret);
int steps = autoSolve(solver, secret);
totalSteps += steps;
maxSteps = Math.max(maxSteps, steps);
System.out.println();
}
System.out.println("--- 统计 ---");
System.out.printf("总轮数: %d%n", rounds);
System.out.printf("平均步数: %.2f%n", (double) totalSteps / rounds);
System.out.printf("最大步数: %d%n", maxSteps);
System.out.println("(Knuth 算法保证在 5 步内破解任何序列)");
}
/**
* AI 自动破解指定秘密，返回所用步数
*/
private static int autoSolve(KnuthSolver solver, Code secret) {
int steps = 0;
Code guess;
// 经典开局：选择两个颜色各重复两次的序列，信息量大
// 如 [红, 红, 橙, 橙]，这在 Knuth 算法中通常会被自动选中
while (true) {
guess = solver.findBestGuess();
steps++;
Feedback fb = secret.compareTo(guess);
System.out.printf(" 第 %d 步: 猜测 %s -> 反馈 %s", steps, guess, fb);
if (fb.bulls == CODE_LENGTH) {
System.out.println(" ✅ 破解成功!");
break;
} else {
System.out.printf(" (剩余候选: %d)%n", solver.getCandidates().size());
}
solver.filterCandidates(guess, fb);
}
return steps;
}
/**
* 交互模式：人类设密，AI 破解
*/
private static void interactiveMode() {
Scanner scanner = new Scanner(System.in);
KnuthSolver solver = new KnuthSolver(CODE_LENGTH, COLOR_RANGE);
System.out.println("请在心里想一个 4 位颜色序列（如: 0 1 2 3 表示 [红, 橙, 黄, 绿]）");
System.out.println("每次我会猜测，你输入反馈: 公牛数 奶牛数（如: 1 2）");
System.out.println();
int steps = 0;
while (true) {
Code guess = solver.findBestGuess();
steps++;
System.out.printf("第 %d 步猜测: %s%n", steps, guess);
System.out.print("请输入反馈 (公牛 奶牛): ");
int bulls = scanner.nextInt();
int cows = scanner.nextInt();
if (bulls == CODE_LENGTH) {
System.out.println("破解成功！");
break;
}
solver.filterCandidates(guess, new Feedback(bulls, cows));
if (solver.getCandidates().isEmpty()) {
System.out.println("候选集为空，请检查反馈是否输入正确！");
break;
}
}
}
}
四、算法复杂度分析
时间复杂度
设颜色种类为 $C$，序列长度为 $L$，总组合数为 $N = C^L$。
- 生成所有代码：$O(N \times L)$，即 $O(C^L \times L)$
- 单次 Bulls/Cows 计算：$O(L + C)$，使用频率数组优化后
- 单次最小最大评估：对 $N$ 个猜测，每个猜测需要与 $|S|$ 个候选比较，共 $O(N \times |S| \times L)$
- 完整求解：最坏情况下每轮都需重新计算，总体约为 $O(k \times N^2 \times L)$，其中 $k$ 是步数（标准 Mastermind 中 $k \leq 5$）
对于标准参数 $C=6, L=4$，$N=1296$，单次选 guess 约需 $1296 \times 1296 \times 4 \approx 670$ 万次操作，在现代 CPU 上毫秒级完成。
空间复杂度
- 存储所有代码：$O(N \times L)$
- 候选集：最坏 $O(N \times L)$
- 反馈分组映射：$O(K)$，$K$ 是不同反馈组合数（标准 Mastermind 中 $K \leq 14$）
五、扩展与优化方向
-
熵策略对比实验：实现两种策略（最小最大 vs 信息熵），对全部 1296 个秘密做批量测试，统计平均步数和最坏步数。通常熵策略的平均步数更优（约 4.1 步），但最小最大策略的最坏步数更优（保证 5 步）。
-
更大规模问题：当颜色数 $C$ 或长度 $L$ 增大时，$C^L$ 指数增长。此时可采用蒙特卡洛采样缩小候选评估范围，或使用遗传算法近似求解最优 guess。
-
人类心理模型：如果对手并非均匀随机选秘密，可以引入贝叶斯更新，根据历史数据调整先验分布，使猜测更贴合对手偏好。
六、总结
色彩密码是一个将组合数学、信息论与博弈论完美融合的经典问题。Knuth 最小最大算法的精妙之处在于：它不是在猜测”最可能”的答案，而是在系统地缩小可能性空间。每一次选择都在问：”如果我的运气最差，哪种猜测能让我剩下的工作最少？”这种最坏情况最优化的思想，在密码学、决策树设计和对抗性 AI 中都有广泛应用。
通过本文的 Java 实现，你可以看到：
– 如何用频率数组高效计算 Bulls/Cows
– 如何用候选集过滤实现确定性的状态空间搜索
– 如何用最小最大原则做出最优决策
– 如何用信息熵量化一次猜测的信息价值
完整代码可直接编译运行，尝试修改 COLOR_RANGE 和 CODE_LENGTH，观察算法在不同规模问题上的表现。
