每日算法 — 使用java实现Wordle：信息论熵计算与贪心最优猜测策略

引言

Wordle是一款风靡全球的猜词游戏：玩家在6次机会内猜出一个5字母英文单词，每次猜测后系统以颜色反馈每个字母的位置信息（绿色=位置正确、黄色=字母存在但位置错误、灰色=字母不存在）。要在最少次数内找到答案，信息论提供了数学上最优的策略——每次选择能最大化信息熵（Entropy）的猜测词，从而最快缩小候选词空间。

问题建模与信息论基础

设当前候选词集合为 $S$，一次猜测 $g$ 可能产生 $3^5 = 243$ 种反馈模式（每个位置3种状态，但实际受约束更少）。根据信息论，猜测 $g$ 的期望信息增益为：

$$H(g) = -\sum_{p} P(p) \cdot \log_2 P(p)$$

其中 $p$ 为反馈模式，$P(p) = \frac{|{w \in S : \text{feedback}(g, w) = p}|}{|S|}$。选择使 $H(g)$ 最大的猜测词即为贪心最优策略。

核心模块一：反馈模式计算

将猜测词 $g$ 与目标词 $w$ 比较，生成5位反馈编码（0=灰, 1=黄, 2=绿）。

import java.util.*;

/**
 * Wordle反馈模式计算器
 * 编码规则：2=绿色(位置正确), 1=黄色(字母存在但位置错), 0=灰色(字母不存在)
 */
public class WordleFeedback {

    /**
     * 计算猜测词对目标词的反馈模式
     * 算法要点：先标记所有绿色位置，再对剩余字母统计出现次数处理黄色
     * @param guess 猜测词，如 "crane"
     * @param target 目标词，如 "apple"
     * @return 5位整数数组，每位为 0/1/2
     */
    public static int[] computeFeedback(String guess, String target) {
        int[] feedback = new int[5];
        boolean[] targetUsed = new boolean[5]; // 标记目标词中已被匹配的字母

        // 第一轮：标记绿色（位置完全正确）
        for (int i = 0; i < 5; i++) {
            if (guess.charAt(i) == target.charAt(i)) {
                feedback[i] = 2;
                targetUsed[i] = true;
            }
        }

        // 第二轮：标记黄色（字母存在但位置不同）
        // 统计目标词中各字母的剩余可用次数
        int[] targetCounts = new int[26];
        for (int i = 0; i < 5; i++) {
            if (!targetUsed[i]) {
                targetCounts[target.charAt(i) - 'a']++;
            }
        }

        for (int i = 0; i < 5; i++) {
            if (feedback[i] == 2) continue; // 跳过已标记绿色的位置
            char c = guess.charAt(i);
            int idx = c - 'a';
            if (targetCounts[idx] > 0) {
                feedback[i] = 1;
                targetCounts[idx]--;
            } else {
                feedback[i] = 0;
            }
        }
        return feedback;
    }

    /**
     * 将反馈数组编码为字符串，便于作为HashMap的键
     */
    public static String encodeFeedback(int[] feedback) {
        StringBuilder sb = new StringBuilder();
        for (int f : feedback) sb.append(f);
        return sb.toString();
    }

    /**
     * 验证当前候选词是否与历史反馈一致
     * @param candidate 待验证候选词
     * @param guessHistory 历史猜测列表
     * @param feedbackHistory 对应的历史反馈列表
     * @return 是否一致
     */
    public static boolean isConsistent(String candidate, List<String> guessHistory, 
                                       List<int[]> feedbackHistory) {
        for (int i = 0; i < guessHistory.size(); i++) {
            int[] expected = computeFeedback(guessHistory.get(i), candidate);
            if (!Arrays.equals(expected, feedbackHistory.get(i))) {
                return false;
            }
        }
        return true;
    }
}

核心模块二：信息熵计算与最优猜测选择

/**
 * Wordle最优策略引擎：基于信息熵的贪心选择
 */
public class WordleStrategy {

    private final List<String> allWords; // 完整词库（含猜测词和答案词）
    private final List<String> solutionWords; // 仅答案词库

    public WordleStrategy(List<String> allWords, List<String> solutionWords) {
        this.allWords = allWords;
        this.solutionWords = solutionWords;
    }

    /**
     * 计算给定猜测词在候选集合上的期望信息熵
     * @param guess 猜测词
     * @param candidates 当前候选答案集合
     * @return 期望信息熵（比特）
     */
    public double computeEntropy(String guess, List<String> candidates) {
        // 按反馈模式分组统计
        Map<String, Integer> patternCount = new HashMap<>();
        for (String candidate : candidates) {
            int[] fb = WordleFeedback.computeFeedback(guess, candidate);
            String key = WordleFeedback.encodeFeedback(fb);
            patternCount.merge(key, 1, Integer::sum);
        }

        double entropy = 0.0;
        int total = candidates.size();
        for (int count : patternCount.values()) {
            if (count > 0) {
                double p = (double) count / total;
                entropy -= p * (Math.log(p) / Math.log(2));
            }
        }
        return entropy;
    }

    /**
     * 从完整词库中选择信息熵最大的猜测词
     * 优化：通常限制在答案词库内搜索即可达到接近最优效果，速度提升10倍+
     * @param candidates 当前候选答案集合
     * @param restrictToCandidates 是否仅在候选集中搜索（更快但可能略次优）
     * @return 最优猜测词及其熵值
     */
    public GuessResult findBestGuess(List<String> candidates, boolean restrictToCandidates) {
        List<String> searchSpace = restrictToCandidates ? candidates : allWords;
        String bestGuess = null;
        double bestEntropy = -1;

        for (String guess : searchSpace) {
            double entropy = computeEntropy(guess, candidates);
            if (entropy > bestEntropy) {
                bestEntropy = entropy;
                bestGuess = guess;
            }
        }
        return new GuessResult(bestGuess, bestEntropy);
    }

    /**
     * 根据反馈过滤候选集合
     */
    public List<String> filterCandidates(List<String> candidates, String guess, int[] feedback) {
        List<String> filtered = new ArrayList<>();
        for (String candidate : candidates) {
            int[] expected = WordleFeedback.computeFeedback(guess, candidate);
            if (Arrays.equals(expected, feedback)) {
                filtered.add(candidate);
            }
        }
        return filtered;
    }

    public static class GuessResult {
        public final String word;
        public final double entropy;
        public GuessResult(String word, double entropy) {
            this.word = word;
            this.entropy = entropy;
        }
        @Override
        public String toString() {
            return String.format("%s (entropy=%.3f bits)", word, entropy);
        }
    }
}

核心模块三：完整游戏引擎与自动求解演示

import java.io.*;
import java.nio.file.*;
import java.util.*;

/**
 * Wordle完整游戏引擎与自动求解器
 */
public class WordleGame {
    private List<String> allWords;
    private List<String> solutionWords;
    private WordleStrategy strategy;
    private Random random = new Random();

    /**
     * 从文件加载词库（每行一个5字母单词）
     */
    public void loadWords(String allWordsPath, String solutionsPath) throws IOException {
        allWords = Files.readAllLines(Paths.get(allWordsPath));
        solutionWords = Files.readAllLines(Paths.get(solutionsPath));
        strategy = new WordleStrategy(allWords, solutionWords);
        System.out.println("词库加载完成：总计 " + allWords.size() + " 词，答案库 " + solutionWords.size() + " 词");
    }

    /**
     * 自动求解演示：AI在隐藏目标词上进行 guess
     * @param target 目标词
     * @param verbose 是否打印每轮详情
     * @return 成功猜测所需轮数（失败返回-1）
     */
    public int autoSolve(String target, boolean verbose) {
        List<String> candidates = new ArrayList<>(solutionWords);
        List<String> guessHistory = new ArrayList<>();
        List<int[]> feedbackHistory = new ArrayList<>();

        // 第一轮固定使用预计算的最优开局词（如 "crane" 或 "soare"）
        // 实际可通过预计算确定全局最优开局词
        String guess = "crane"; // 经验上接近最优的开局词

        for (int turn = 1; turn <= 6; turn++) {
            int[] feedback = WordleFeedback.computeFeedback(guess, target);
            guessHistory.add(guess);
            feedbackHistory.add(feedback);

            if (verbose) {
                System.out.printf("第%d轮: %s -> %s%n", turn, guess, formatFeedback(feedback));
            }

            // 检查是否猜中（全绿）
            boolean allGreen = true;
            for (int f : feedback) if (f != 2) allGreen = false;
            if (allGreen) return turn;

            // 过滤候选集
            candidates = strategy.filterCandidates(candidates, guess, feedback);
            if (candidates.isEmpty()) {
                if (verbose) System.out.println("候选集为空，矛盾！");
                return -1;
            }

            // 选择下一轮最优猜测（限制在候选集内搜索以加速）
            WordleStrategy.GuessResult best = strategy.findBestGuess(candidates, true);
            guess = best.word;

            if (verbose) {
                System.out.printf("  候选词剩余 %d 个，最优猜测: %s%n", candidates.size(), best);
            }
        }
        return -1; // 6轮内未猜中
    }

    /**
     * 批量统计求解性能
     */
    public void benchmark(int sampleSize) {
        int[] distribution = new int[8]; // 索引1-6为轮数，7为失败
        double totalTurns = 0;

        for (int i = 0; i < sampleSize; i++) {
            String target = solutionWords.get(random.nextInt(solutionWords.size()));
            int turns = autoSolve(target, false);
            if (turns > 0) {
                distribution[turns]++;
                totalTurns += turns;
            } else {
                distribution[7]++;
            }
        }

        System.out.println("\n===== 求解性能统计 =====");
        for (int t = 1; t <= 6; t++) {
            System.out.printf("%d轮解决: %d (%.1f%%)%n", t, distribution[t], 
                100.0 * distribution[t] / sampleSize);
        }
        System.out.printf("失败: %d (%.1f%%)%n", distribution[7], 
            100.0 * distribution[7] / sampleSize);
        System.out.printf("平均轮数: %.2f%n", totalTurns / sampleSize);
    }

    private String formatFeedback(int[] feedback) {
        StringBuilder sb = new StringBuilder();
        for (int f : feedback) {
            sb.append(f == 2 ? "🟩" : f == 1 ? "🟨" : "⬜");
        }
        return sb.toString();
    }

    /**
     * 预计算全局最优开局词（离线运行一次即可）
     */
    public String precalculateBestOpening() {
        System.out.println("正在预计算最优开局词...");
        WordleStrategy.GuessResult best = strategy.findBestGuess(solutionWords, false);
        System.out.println("最优开局词: " + best);
        return best.word;
    }

    public static void main(String[] args) throws IOException {
        WordleGame game = new WordleGame();
        // 使用标准Wordle词库（需自行准备 valid_words.txt 和 solutions.txt）
        // game.loadWords("valid_words.txt", "solutions.txt");

        // 演示：使用内置小词库
        game.allWords = Arrays.asList("crane", "apple", "brain", "crate", "grape", "plate", 
            "skate", "stare", "trace", "orate", "adieu", "soare", "trace", "slate", "prate");
        game.solutionWords = new ArrayList<>(game.allWords);
        game.strategy = new WordleStrategy(game.allWords, game.solutionWords);

        // 演示自动求解
        System.out.println("===== 自动求解演示 =====");
        game.autoSolve("grape", true);
    }
}

熵计算示例

假设候选词集合为 {apple, apply, ample, amply}，猜测 "apply"：
– 若目标为 apple → 反馈 22000
– 若目标为 apply → 反馈 22222
– 若目标为 ample → 反馈 10020
– 若目标为 amply → 反馈 10022

每种反馈模式概率均为 $1/4$，信息熵 $H = -4 \times (0.25 \times \log_2 0.25) = 2$ 比特。若猜测 "xxxxx" 导致所有目标映射到同一反馈，则熵为0，完全无信息增益。

复杂度与优化策略

关键优化：将搜索空间限制在候选集内（而非完整词库），求解质量损失极小但速度提升10倍以上。Wordle的答案库约2300词，完整猜测库约13000词。

扩展方向

1. Minimax改进：用最小化最大剩余候选集代替最大化期望熵，在最坏情况下更稳健
2. Hard Mode适配：硬模式要求已揭示的绿/黄字母必须在后续猜测中使用，需调整过滤逻辑
3. 多语言扩展：将算法适配到中文成语Wordle或变长词版本
4. 对抗性目标：若目标词由对手自适应选择，需引入博弈论框架

总结

Wordle最优策略是信息论在趣味游戏中的绝佳应用。通过计算每次猜测的期望信息熵，AI能以平均约3.4轮解决标准Wordle，接近理论极限。核心代码仅百余行，却蕴含了模式匹配、概率分布、熵计算等丰富的算法思想。