每日算法 — 使用java实现猜单词：信息熵最优字母选择与频率统计

猜单词（Hangman）是一款经典的文字益智游戏。玩家需要在有限的猜测次数内，根据已揭示的字母位置推断出隐藏的单词。本文用Java实现一个智能猜单词AI，讲解如何利用信息熵理论进行最优字母选择，结合英语字母频率统计提升猜测效率，包含完整代码与复杂度分析。

游戏机制与问题建模

在标准猜单词游戏中，系统随机选择一个目标单词，玩家每次猜一个字母。若该字母存在于单词中，则揭示所有出现位置；否则扣除一次生命。玩家需在生命耗尽前猜出完整单词。

将问题抽象为信息论模型：每次猜测的本质是从26个字母中选择一个，使得该猜测能够最大程度地缩小可能的单词集合。信息熵正是衡量”不确定性减少程度”的数学工具。

信息熵理论

香农信息熵定义为：

$$H(X) = -\sum_{i} p(x_i) \log_2 p(x_i)$$

在猜单词场景中，将候选单词集合 $S$ 按照字母 $c$ 的出现模式划分为若干子集。例如，对于5字母单词和字母’a’，可能的模式包括：”不出现在任何位置”、”出现在第1位”、”出现在第2位”等。每种模式对应一个子集 $S_i$，其概率 $p_i = |S_i| / |S|$。

字母 $c$ 的期望信息增益（即条件熵减少量）为：

$$Gain(c) = H(S) – \sum_{i} p_i \cdot H(S_i)$$

选择使 $Gain(c)$ 最大的字母作为下一次猜测。

工程实现架构

整体采用三层架构：
– 词典层：加载并维护候选单词集合，支持按长度和已知模式过滤
– 策略层：实现多种猜测策略（信息熵、字母频率、随机等）
– 游戏层：处理游戏状态流转、胜负判定与人机交互

核心算法实现

import java.util.*;
import java.util.stream.*;

/**
 * 猜单词智能AI - 基于信息熵的最优字母选择
 */
public class HangmanSolver {

    private List<String> dictionary;      // 完整词典
    private List<String> candidates;      // 当前候选集合
    private Set<Character> guessed;       // 已猜测字母
    private String pattern;               // 当前已揭示模式，如 "A__LE"
    private int wordLength;

    public HangmanSolver(List<String> dict, int length) {
        this.dictionary = new ArrayList<>(dict);
        this.wordLength = length;
        this.guessed = new HashSet<>();
        // 筛选指定长度的单词
        this.candidates = dictionary.stream()
            .filter(w -> w.length() == length)
            .filter(w -> w.chars().allMatch(Character::isLetter))
            .map(String::toUpperCase)
            .collect(Collectors.toList());
        this.pattern = "_".repeat(length);
    }

    /**
     * 信息熵策略：选择期望信息增益最大的字母
     */
    public char entropyBasedGuess() {
        if (candidates.isEmpty()) return randomGuess();

        double bestGain = -1;
        char bestChar = '?';

        for (char c = 'A'; c <= 'Z'; c++) {
            if (guessed.contains(c)) continue;

            // 按字母c的出现模式对候选集分组
            Map<String, List<String>> groups = new HashMap<>();
            for (String word : candidates) {
                String mask = getMask(word, c);
                groups.computeIfAbsent(mask, k -> new ArrayList<>()).add(word);
            }

            // 计算期望信息增益
            double expectedEntropy = 0;
            int total = candidates.size();
            for (List<String> group : groups.values()) {
                double p = (double) group.size() / total;
                expectedEntropy -= p * Math.log(p) / Math.log(2);
            }

            // 信息增益 = 当前熵 - 期望条件熵
            double currentEntropy = Math.log(total) / Math.log(2);
            double gain = currentEntropy - expectedEntropy;

            if (gain > bestGain) {
                bestGain = gain;
                bestChar = c;
            }
        }
        return bestChar;
    }

    /**
     * 频率策略：选择在候选集中出现频率最高的字母
     */
    public char frequencyBasedGuess() {
        int[] freq = new int[26];
        for (String word : candidates) {
            Set<Character> unique = new HashSet<>();
            for (char c : word.toCharArray()) unique.add(c);
            for (char c : unique) freq[c - 'A']++;
        }

        char best = '?';
        int maxFreq = -1;
        for (char c = 'A'; c <= 'Z'; c++) {
            if (!guessed.contains(c) && freq[c - 'A'] > maxFreq) {
                maxFreq = freq[c - 'A'];
                best = c;
            }
        }
        return best;
    }

    /**
     * 获取单词在目标字母下的位置掩码
     * 例如 getMask("APPLE", 'P') -> "_PP__"
     */
    private String getMask(String word, char target) {
        StringBuilder sb = new StringBuilder();
        for (char c : word.toCharArray()) {
            sb.append(c == target ? target : '_');
        }
        return sb.toString();
    }

    /**
     * 更新游戏状态：根据猜测结果过滤候选集
     * @param letter 猜测的字母
     * @param positions 该字母出现的所有位置（空表示未出现）
     */
    public void updateState(char letter, List<Integer> positions) {
        guessed.add(letter);

        if (positions.isEmpty()) {
            // 字母不存在：过滤掉包含该字母的候选
            candidates.removeIf(w -> w.indexOf(letter) >= 0);
        } else {
            // 字母存在：只保留在对应位置出现该字母的候选
            candidates.removeIf(w -> {
                for (int pos : positions) {
                    if (w.charAt(pos) != letter) return true;
                }
                // 确保该字母只出现在这些位置
                for (int i = 0; i < wordLength; i++) {
                    if (!positions.contains(i) && w.charAt(i) == letter) return true;
                }
                return false;
            });
            // 更新已揭示模式
            char[] pat = pattern.toCharArray();
            for (int pos : positions) pat[pos] = letter;
            pattern = new String(pat);
        }
    }

    public boolean isSolved() {
        return !pattern.contains("_");
    }

    public String getPattern() { return pattern; }
    public int getCandidateCount() { return candidates.size(); }

    // 随机猜测兜底
    private char randomGuess() {
        List<Character> available = new ArrayList<>();
        for (char c = 'A'; c <= 'Z'; c++) if (!guessed.contains(c)) available.add(c);
        return available.get(new Random().nextInt(available.size()));
    }
}

/**
 * 游戏主控与交互
 */
public class HangmanGame {
    private static final int MAX_LIVES = 6;
    private String target;
    private int lives;
    private HangmanSolver solver;

    public HangmanGame(String word, List<String> dictionary) {
        this.target = word.toUpperCase();
        this.lives = MAX_LIVES;
        this.solver = new HangmanSolver(dictionary, word.length());
    }

    /**
     * AI自动玩一局
     */
    public boolean playAuto() {
        System.out.println("目标单词长度: " + target.length());
        while (lives > 0 && !solver.isSolved()) {
            char guess = solver.entropyBasedGuess();
            List<Integer> positions = new ArrayList<>();
            for (int i = 0; i < target.length(); i++) {
                if (target.charAt(i) == guess) positions.add(i);
            }

            boolean hit = !positions.isEmpty();
            solver.updateState(guess, positions);

            System.out.printf("猜测: %c | %s | 候选集: %d | 模式: %s%n",
                guess, hit ? "命中" : "未命中(-1生命)",
                solver.getCandidateCount(), solver.getPattern());

            if (!hit) lives--;
        }
        System.out.println(solver.isSolved() ? "AI获胜!" : "AI失败，目标: " + target);
        return solver.isSolved();
    }

    public static void main(String[] args) {
        // 示例词典（实际应加载更大词典）
        List<String> dict = Arrays.asList(
            "APPLE", "APPLY", "ABOUT", "ABOVE", "ALERT", "ALBUM", "ALIVE",
            "BRAVE", "BRAIN", "BREAD", "BREAK", "BRING", "BROWN", "BUILD",
            "CANDY", "CARRY", "CATCH", "CAUSE", "CHAIN", "CHAIR", "CHART",
            "DANCE", "DAILY", "DEATH", "DEPTH", "DOUBT", "DREAM", "DRIVE",
            "EARTH", "EARLY", "EIGHT", "ENJOY", "ENTER", "EQUAL", "EVERY",
            "FAITH", "FAULT", "FIELD", "FIGHT", "FINAL", "FIRST", "FOCUS",
            "GLASS", "GLOBAL", "GRAND", "GRANT", "GRASS", "GREAT", "GREEN",
            "HEART", "HEAVY", "HORSE", "HOTEL", "HOUSE", "HUMAN", "HAPPY",
            "IMAGE", "INDEX", "INNER", "INPUT", "ISSUE", "IDEAL", "IRONY",
            "JUDGE", "JOINT", "JUICE", "JUMPY"
        );

        HangmanGame game = new HangmanGame("APPLE", dict);
        game.playAuto();
    }
}

算法复杂度分析

信息熵计算：对于候选集大小 $n$、单词长度 $m$，每次猜测需要遍历26个字母，对每个字母遍历 $n$ 个候选词并计算掩码。时间复杂度 $O(26 \cdot n \cdot m) = O(n \cdot m)$。

候选集过滤：每次更新需要遍历候选集并逐字符比对，复杂度 $O(n \cdot m)$。

空间复杂度：存储候选集需要 $O(n \cdot m)$ 空间。

策略对比与优化

实际工程中可采用混合策略：前期用信息熵快速缩小范围，候选集小于阈值后切换至频率策略以降低计算开销。

扩展方向

1. N-gram语言模型：利用字母组合条件概率进一步优化候选排序
2. 多单词并行猜测：同时维护多个可能目标的后验概率分布
3. 自适应词典：根据用户历史行为动态调整先验概率

总结

本文通过信息熵理论为猜单词游戏构建了最优决策框架。核心思想是将每次猜测转化为对候选集合的划分问题，选择使期望熵减最大的字母。Java实现中通过掩码分组和集合过滤高效维护游戏状态，为文字类益智游戏的AI设计提供了通用范式。