引言
猜数字是一款经典的逻辑推理游戏：一方心里想一个数字，另一方通过有限的猜测次数将其找出。每次猜测后会得到”太大”或”太小”的反馈。看似简单的游戏背后，蕴含着信息论、二分搜索与最优决策的深刻数学原理。本文用Java实现带AI的猜数字游戏，让计算机用最优策略猜测。
算法原理
1. 二分搜索基础
若数字范围为[1, N]，每次猜测中间的数字，可将搜索空间减半。最坏情况下需要⌈log₂N⌉次猜测。
2. 信息熵视角
每次猜测相当于一次信息获取。设当前候选集合为S，猜测数字g将S划分为：
– S₁ = {x ∈ S | x < g}
– S₂ = {x ∈ S | x = g}
– S₃ = {x ∈ S | x > g}
最优猜测应使三个子集的大小尽可能均衡，从而最大化信息增益（最小化熵）。
3. 最优策略
标准二分搜索在均匀分布假设下已是最优。若数字分布非均匀，可用加权中位数替代普通中位数。
Java实现
import java.util.*;
/**
* 猜数字游戏AI实现
* 包含二分搜索、信息熵计算与最优策略分析
*/
public class GuessNumber {
// 游戏配置
private final int minRange;
private final int maxRange;
private final int secretNumber;
private int guessCount;
public GuessNumber(int minRange, int maxRange) {
this.minRange = minRange;
this.maxRange = maxRange;
this.secretNumber = minRange + (int)(Math.random() * (maxRange - minRange + 1));
this.guessCount = 0;
}
/**
* 获取对一次猜测的反馈
* @return -1: 太大, 0: 正确, 1: 太小
*/
public int feedback(int guess) {
guessCount++;
if (guess == secretNumber) return 0;
return guess < secretNumber ? 1 : -1;
}
/**
* 二分搜索AI策略
*/
public int[] binarySearchAI() {
int low = minRange, high = maxRange;
List<Integer> history = new ArrayList<>();
while (low <= high) {
int mid = low + (high - low) / 2;
history.add(mid);
int result = feedback(mid);
if (result == 0) break;
else if (result < 0) high = mid - 1;
else low = mid + 1;
}
return history.stream().mapToInt(Integer::intValue).toArray();
}
/**
* 信息熵最优策略：选择使剩余候选集熵最小的猜测
*/
public int[] entropyOptimalAI() {
List<Integer> candidates = new ArrayList<>();
for (int i = minRange; i <= maxRange; i++) candidates.add(i);
List<Integer> history = new ArrayList<>();
while (candidates.size() > 1) {
int bestGuess = candidates.get(0);
double minEntropy = Double.MAX_VALUE;
for (int guess : candidates) {
// 计算以guess为猜测时的期望熵
int smaller = 0, equal = 0, larger = 0;
for (int cand : candidates) {
if (cand < guess) smaller++;
else if (cand == guess) equal++;
else larger++;
}
double entropy = 0;
int total = candidates.size();
if (smaller > 0) {
double p = (double) smaller / total;
entropy -= p * Math.log(p) / Math.log(2);
}
if (equal > 0) {
double p = (double) equal / total;
entropy -= p * Math.log(p) / Math.log(2);
}
if (larger > 0) {
double p = (double) larger / total;
entropy -= p * Math.log(p) / Math.log(2);
}
if (entropy < minEntropy) {
minEntropy = entropy;
bestGuess = guess;
}
}
history.add(bestGuess);
int result = feedback(bestGuess);
if (result == 0) break;
final int g = bestGuess;
candidates.removeIf(c ->
(result < 0 && c >= g) || (result > 0 && c <= g)
);
}
if (candidates.size() == 1 && guessCount == 0) {
history.add(candidates.get(0));
feedback(candidates.get(0));
}
return history.stream().mapToInt(Integer::intValue).toArray();
}
/**
* 计算理论最小猜测次数（信息论下界）
*/
public static double informationTheoreticLowerBound(int n) {
return Math.ceil(Math.log(n) / Math.log(2));
}
/**
* 批量模拟比较两种策略
*/
public static void simulate(int minRange, int maxRange, int trials) {
int totalBinary = 0, totalEntropy = 0;
int binaryWins = 0, entropyWins = 0;
for (int t = 0; t < trials; t++) {
GuessNumber game1 = new GuessNumber(minRange, maxRange);
GuessNumber game2 = new GuessNumber(minRange, maxRange);
// 确保两者目标数字相同
int secret = game1.secretNumber;
game2.secretNumber = secret;
int[] binaryResult = game1.binarySearchAI();
int[] entropyResult = game2.entropyOptimalAI();
totalBinary += binaryResult.length;
totalEntropy += entropyResult.length;
if (binaryResult.length < entropyResult.length) binaryWins++;
else if (entropyResult.length < binaryResult.length) entropyWins++;
}
int n = maxRange - minRange + 1;
System.out.println("===== 猜数字策略对比 =====");
System.out.printf("范围: [%d, %d], 共%d个数%n", minRange, maxRange, n);
System.out.printf("信息论下界: %.0f次%n", informationTheoreticLowerBound(n));
System.out.printf("二分搜索平均: %.2f次%n", (double) totalBinary / trials);
System.out.printf("熵最优策略平均: %.2f次%n", (double) totalEntropy / trials);
System.out.printf("二分搜索获胜: %d次%n", binaryWins);
System.out.printf("熵最优获胜: %d次%n", entropyWins);
}
// 需要允许修改secretNumber用于对比实验
int secretNumber;
public static void main(String[] args) {
simulate(1, 100, 1000);
System.out.println();
simulate(1, 10000, 100);
}
}
复杂度分析
- 二分搜索：时间O(log N)，空间O(1)
- 熵最优策略：每次需遍历所有候选计算熵，时间O(N²)，但仅用于教学演示
- 信息论下界：⌈log₂N⌉，任何确定性算法都无法突破
扩展方向
- Mastermind变体：若反馈变为”A个位置正确、B个数字正确但位置错误”，问题变为NP难问题，可用遗传算法或约束传播求解
- 非均匀先验：若数字服从某种分布（如正态分布），可用贝叶斯更新替代二分搜索
- 双人博弈：若对手可以撒谎有限次数，引入容错机制
总结
本文从信息熵角度重新诠释了猜数字游戏，证明二分搜索在均匀分布下即为最优策略。通过Java实现对比了经典二分搜索与显式熵最小化策略，验证了理论下界的紧性。
