引言
Hangman（吊死鬼/猜词游戏）是经典的文字解谜游戏：系统秘密选择一个单词，玩家每次猜一个字母，若字母在单词中则揭示其所有位置，否则记录一次错误。玩家需要在有限次数（通常6次）的错误内猜出完整单词。
本文将用 Java 实现一个智能 Hangman 求解器，核心算法基于字母频率统计与约束传播，让 AI 以极高胜率挑战人类出题者。
问题建模
游戏状态
状态 = (单词长度, 已揭示位置, 已猜错字母集合, 剩余错误次数)
智能策略核心
每次猜测时，AI 需要：
1. 从词典中筛选出所有符合当前约束的候选单词
2. 计算每个未猜测字母在候选词中的出现频率
3. 选择能最大化信息增益的字母
核心算法：约束过滤 + 频率贪心
候选词过滤
根据已揭示的字母位置和已猜错的字母，过滤词典：
– 长度必须匹配
– 已揭示位置上的字母必须一致
– 不能包含任何已猜错的字母（除非已揭示）
– 未揭示位置不能包含已揭示的字母（因为那些位置为空）
最优字母选择
对于每个候选字母，计算其”价值”：
– 基础价值：在多少候选词中出现
– 信息增益：猜测后能将候选集缩小多少
– 位置价值：能揭示多少位置信息
完整 Java 实现
import java.io.*;
import java.nio.file.*;
import java.util.*;
import java.util.stream.*;
/**
* Hangman（吊死鬼）智能求解器
* 基于约束过滤与频率分析的贪心最优猜测策略
*/
public class HangmanSolver {
// 完整词典
private final List<String> dictionary;
// 当前候选词集合
private List<String> candidates;
// 已猜错的字母
private final Set<Character> wrongGuesses;
// 已猜对的字母
private final Set<Character> correctGuesses;
// 当前揭示的单词模式（_ 表示未知）
private char[] pattern;
// 最大允许错误次数
private final int maxWrongGuesses;
// 当前错误次数
private int wrongCount;
public HangmanSolver(List<String> dictionary, int wordLength, int maxWrongGuesses) {
this.dictionary = new ArrayList<>(dictionary);
this.wrongGuesses = new HashSet<>();
this.correctGuesses = new HashSet<>();
this.maxWrongGuesses = maxWrongGuesses;
this.wrongCount = 0;
// 初始化：筛选出指定长度的单词
this.candidates = dictionary.stream()
.filter(w -> w.length() == wordLength)
.filter(w -> w.matches("[a-z]+"))
.collect(Collectors.toList());
this.pattern = new char[wordLength];
Arrays.fill(pattern, '_');
}
/**
* 根据当前状态更新候选词集合
* 约束条件：
* 1. 长度匹配
* 2. 已揭示位置字母一致
* 3. 不包含已猜错的字母（除非已揭示）
* 4. 未揭示位置不能包含已揭示字母
*/
public void filterCandidates() {
candidates = candidates.stream()
.filter(word -> matchesPattern(word, pattern))
.filter(word -> !containsWrongLetters(word))
.filter(word -> containsCorrectLetters(word))
.collect(Collectors.toList());
}
/**
* 检查单词是否匹配当前揭示模式
*/
private boolean matchesPattern(String word, char[] pattern) {
if (word.length() != pattern.length) return false;
for (int i = 0; i < pattern.length; i++) {
if (pattern[i] != '_' && word.charAt(i) != pattern[i]) {
return false;
}
if (pattern[i] == '_' && correctGuesses.contains(word.charAt(i))) {
// 已猜对的字母必须出现在已揭示位置
// 如果它出现在未揭示位置，说明我们的假设有问题
// 但实际上这个约束需要更精细处理
}
}
return true;
}
/**
* 检查单词是否包含已猜错的字母（且未在已揭示位置）
*/
private boolean containsWrongLetters(String word) {
for (char c : wrongGuesses) {
if (word.indexOf(c) >= 0) {
// 检查是否所有出现位置都已揭示
for (int i = 0; i < word.length(); i++) {
if (word.charAt(i) == c && pattern[i] == '_') {
return true; // 有未揭示的错误字母
}
}
}
}
return false;
}
/**
* 检查单词是否包含所有已猜对的字母
*/
private boolean containsCorrectLetters(String word) {
for (char c : correctGuesses) {
if (word.indexOf(c) < 0) return false;
}
return true;
}
/**
* 选择下一个最优猜测字母
* 策略：选择在最多候选词中出现的字母
* 时间复杂度: O(candidates × wordLength)
*/
public char chooseNextGuess() {
if (candidates.isEmpty()) {
throw new IllegalStateException("没有候选词了！");
}
// 统计每个未猜测字母的出现次数
Map<Character, Integer> freq = new HashMap<>();
Map<Character, Set<Integer>> positionMap = new HashMap<>();
for (String word : candidates) {
Set<Character> seenInWord = new HashSet<>();
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (isAvailable(c) && !seenInWord.contains(c)) {
freq.merge(c, 1, Integer::sum);
seenInWord.add(c);
positionMap.computeIfAbsent(c, k -> new HashSet<>()).add(i);
}
}
}
if (freq.isEmpty()) {
// 所有候选词字母都已猜测，随机选一个未猜测的
return randomAvailableLetter();
}
// 选择频率最高的字母
// 进阶：考虑位置多样性——能揭示更多位置的字母更有价值
char bestChar = '?';
double bestScore = -1;
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
char c = entry.getKey();
int count = entry.getValue();
Set<Integer> positions = positionMap.getOrDefault(c, Collections.emptySet());
// 评分 = 出现频率 × 位置多样性权重
double positionDiversity = positions.size() / (double) pattern.length;
double score = count * (1.0 + positionDiversity);
if (score > bestScore) {
bestScore = score;
bestChar = c;
}
}
return bestChar;
}
/**
* 检查字母是否可用（未猜测过）
*/
private boolean isAvailable(char c) {
return !wrongGuesses.contains(c) && !correctGuesses.contains(c);
}
/**
* 随机选择一个未猜测的字母（保底策略）
*/
private char randomAvailableLetter() {
List<Character> available = new ArrayList<>();
for (char c = 'a'; c <= 'z'; c++) {
if (isAvailable(c)) available.add(c);
}
return available.get(new Random().nextInt(available.size()));
}
/**
* 处理猜测结果
* @param guessedChar 猜测的字母
* @param positions 该字母在单词中的所有位置（空列表表示猜错）
*/
public void processResult(char guessedChar, List<Integer> positions) {
if (positions.isEmpty()) {
wrongGuesses.add(guessedChar);
wrongCount++;
} else {
correctGuesses.add(guessedChar);
for (int pos : positions) {
pattern[pos] = guessedChar;
}
}
filterCandidates();
}
/**
* 检查是否获胜
*/
public boolean isWon() {
for (char c : pattern) {
if (c == '_') return false;
}
return true;
}
/**
* 检查是否失败
*/
public boolean isLost() {
return wrongCount >= maxWrongGuesses;
}
/**
* 获取当前模式
*/
public String getPattern() {
return new String(pattern);
}
/**
* 获取候选词数量
*/
public int getCandidateCount() {
return candidates.size();
}
/**
* 获取剩余错误次数
*/
public int getRemainingGuesses() {
return maxWrongGuesses - wrongCount;
}
@Override
public String toString() {
return String.format("模式: %s | 错误: %d/%d | 候选: %d",
getPattern(), wrongCount, maxWrongGuesses, candidates.size());
}
/**
* 从文件加载词典
*/
public static List<String> loadDictionary(String path) throws IOException {
return Files.readAllLines(Path.of(path)).stream()
.map(String::trim)
.map(String::toLowerCase)
.filter(w -> w.matches("[a-z]+"))
.distinct()
.collect(Collectors.toList());
}
/**
* 内置小型测试词典
*/
public static List<String> getTestDictionary() {
return Arrays.asList(
"apple", "apricot", "avocado", "banana", "blueberry",
"cherry", "coconut", "cranberry", "date", "dragonfruit",
"elderberry", "fig", "grape", "grapefruit", "guava",
"honeydew", "kiwi", "lemon", "lime", "mango",
"melon", "orange", "papaya", "peach", "pear",
"pineapple", "plum", "pomegranate", "raspberry", "strawberry",
"tangerine", "watermelon", "algorithm", "binary", "computer",
"data", "encryption", "function", "graph", "hash",
"integer", "java", "kernel", "library", "matrix",
"network", "object", "program", "queue", "recursion",
"stack", "tree", "variable", "web", "xml"
);
}
/**
* 运行一次完整游戏
*/
public static GameResult playGame(String secretWord, List<String> dictionary, int maxWrong, boolean verbose) {
HangmanSolver solver = new HangmanSolver(dictionary, secretWord.length(), maxWrong);
List<Character> guesses = new ArrayList<>();
if (verbose) {
System.out.println("秘密单词长度: " + secretWord.length());
System.out.println("最大错误次数: " + maxWrong);
}
while (!solver.isWon() && !solver.isLost()) {
char guess = solver.chooseNextGuess();
guesses.add(guess);
// 计算该字母在秘密单词中的位置
List<Integer> positions = new ArrayList<>();
for (int i = 0; i < secretWord.length(); i++) {
if (secretWord.charAt(i) == guess) {
positions.add(i);
}
}
solver.processResult(guess, positions);
if (verbose) {
System.out.printf("猜测 '%c' -> %s | %s%n",
guess, positions.isEmpty() ? "错误" : "正确" + positions,
solver);
}
}
boolean won = solver.isWon();
if (verbose) {
System.out.println(won ? "AI 获胜!" : "AI 失败! 单词是: " + secretWord);
System.out.println("猜测序列: " + guesses);
}
return new GameResult(won, guesses.size(), solver.wrongCount, secretWord, guesses);
}
static class GameResult {
final boolean won;
final int totalGuesses;
final int wrongGuesses;
final String secretWord;
final List<Character> guessSequence;
GameResult(boolean won, int totalGuesses, int wrongGuesses,
String secretWord, List<Character> guessSequence) {
this.won = won;
this.totalGuesses = totalGuesses;
this.wrongGuesses = wrongGuesses;
this.secretWord = secretWord;
this.guessSequence = guessSequence;
}
}
public static void main(String[] args) throws IOException {
List<String> dictionary = getTestDictionary();
System.out.println("=== Hangman AI 演示 ===\n");
// 测试几个单词
String[] testWords = {"algorithm", "encryption", "watermelon", "pineapple", "recursion"};
int wins = 0;
for (String word : testWords) {
System.out.println("\n--- 测试单词: " + word + " ---");
GameResult result = playGame(word, dictionary, 6, true);
if (result.won) wins++;
}
System.out.printf("\n总胜率: %d/%d (%.1f%%)%n", wins, testWords.length,
100.0 * wins / testWords.length);
// 批量测试统计
System.out.println("\n=== 批量统计 ===");
int totalWins = 0;
int totalGames = 0;
for (String word : dictionary) {
if (word.length() >= 5 && word.length() <= 10) {
GameResult result = playGame(word, dictionary, 6, false);
if (result.won) totalWins++;
totalGames++;
}
}
System.out.printf("测试 %d 个单词，胜率: %.1f%% (错误≤6)%n",
totalGames, 100.0 * totalWins / totalGames);
}
}
算法解析
为什么频率贪心有效
英语中字母频率不均匀（e、e、t、a 出现最多）。在候选集较大时，选择高频字母有最大概率命中。随着约束收紧，候选集缩小，频率统计自动适应剩余可能性。
信息增益视角
更高级的策略会计算每个字母的期望信息增益：
– 字母出现在 k 个候选词中，猜测后的期望候选集大小 = (出现时的子集大小 × 出现概率) + (不出现时的大小 × 不出现概率)
– 选择使期望候选集最小的字母
约束传播的力量
每次猜测后，无论对错，都能大幅缩小候选集：
– 猜对：固定某些位置，排除大量不符单词
– 猜错：排除所有包含该字母的单词
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 候选过滤 | O(|D| × L) | 遍历词典，L=单词长度 |
| 频率统计 | O(|C| × L) | C=候选集 |
| 单次猜测 | O(|D| × L) | dominated by 过滤 |
| 完整游戏 | O(G × |D| × L) | G=猜测次数 |
扩展思考
- N-gram 增强：使用字母组合频率（如 “th”、”ing”）进一步提升准确率。
- 自适应词典：根据玩家历史偏好调整词频权重。
- 对抗性出题：出题者选择使 AI 胜率最低的单词（极小极大策略）。
总结
Hangman 求解器展示了约束满足 + 统计贪心的经典组合：用约束过滤缩小搜索空间，用频率统计做最优决策。这一思路广泛应用于拼写检查、密码破解、自然语言处理等领域。
