每日算法 — 使用java实现Wordle：信息熵最优猜测策略与约束传播

可莉爸爸 AI算法

Wordle 是一款风靡全球的猜单词游戏，玩家需要在最多6次尝试内猜出一个5字母的隐藏单词。每次猜测后，系统会以颜色反馈每个字母的状态：绿色表示字母位置正确，黄色表示字母存在但位置错误，灰色表示字母不存在。本文将用 Java 实现一个带 AI 的 Wordle 求解器，核心算法包括信息熵驱动的最优猜测选择、约束传播过滤候选词空间，以及基于字母频率的辅助评估策略。

一、游戏机制与问题建模

Wordle 的状态空间由所有合法的5字母单词构成。每次猜测后，根据反馈模式（pattern）可以将候选集大幅缩小。一个反馈模式是5个位置的组合，每个位置有3种状态，共 3^5 = 243 种可能的模式。信息论告诉我们，最优的猜测应该最大化期望信息增益，即让反馈后的候选集尽可能小。

二、核心算法：信息熵与最优猜测

信息熵 H(X) = -Σ p(x) · log₂(p(x))。对于某个猜测单词，我们遍历所有可能的隐藏词，计算每种反馈模式出现的概率，进而计算该猜测的期望熵。选择期望熵最大的单词作为下一次猜测，可以在平均意义下最快缩小搜索空间。

三、约束传播机制

收到反馈后，需要根据颜色信息建立约束条件：
– 绿色约束：该位置必须是此字母
– 黄色约束：该字母必须出现在单词中，但不能在此位置
– 灰色约束：该字母不能出现在单词中（需注意重复字母的复杂情况）

约束传播通过过滤候选词列表实现，时间复杂度与候选集大小成线性关系。

四、Java 完整实现

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

/**
 * Wordle AI 求解器
 * 核心算法：信息熵最大化 + 约束传播
 */
public class WordleSolver {

    private List<String> allWords;      // 全部合法单词
    private List<String> candidates;    // 当前候选集
    private final Random random = new Random();

    public WordleSolver(String wordListPath) throws IOException {
        this.allWords = Files.readAllLines(Paths.get(wordListPath))
                             .stream()
                             .map(String::toLowerCase)
                             .filter(w -> w.length() == 5)
                             .filter(w -> w.matches("[a-z]{5}"))
                             .distinct()
                             .collect(Collectors.toList());
        this.candidates = new ArrayList<>(allWords);
        System.out.println("加载单词数: " + allWords.size());
    }

    /**
     * 计算两个单词的反馈模式
     * @param guess 猜测词
     * @param target 目标词
     * @return 模式数组：2=绿色, 1=黄色, 0=灰色
     */
    public int[] computePattern(String guess, String target) {
        int[] pattern = new int[5];
        boolean[] targetUsed = new boolean[5];

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

        // 第二遍：标记黄色（字母存在但位置错误）
        for (int i = 0; i < 5; i++) {
            if (pattern[i] == 2) continue;
            char c = guess.charAt(i);
            for (int j = 0; j < 5; j++) {
                if (!targetUsed[j] && target.charAt(j) == c) {
                    pattern[i] = 1;
                    targetUsed[j] = true;
                    break;
                }
            }
        }

        return pattern;
    }

    /**
     * 将模式编码为字符串，便于统计
     */
    private String encodePattern(int[] pattern) {
        StringBuilder sb = new StringBuilder();
        for (int p : pattern) sb.append(p);
        return sb.toString();
    }

    /**
     * 计算某个猜测的期望信息熵
     */
    public double computeEntropy(String guess, List<String> wordList) {
        Map<String, Integer> patternCount = new HashMap<>();
        int total = wordList.size();

        for (String target : wordList) {
            int[] pattern = computePattern(guess, target);
            String key = encodePattern(pattern);
            patternCount.merge(key, 1, Integer::sum);
        }

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

        return entropy;
    }

    /**
     * 从候选集中选择信息熵最大的猜测
     * 优化：优先从候选集中选，若候选集过大则采样
     */
    public String selectBestGuess(List<String> guessPool, List<String> candidatePool) {
        if (candidatePool.size() <= 2) {
            return candidatePool.get(0);
        }

        String bestGuess = null;
        double maxEntropy = -1;

        // 若候选池过大，只从候选池中选（保证猜对时直接胜利）
        List<String> poolToEvaluate = guessPool.size() > 5000 
            ? candidatePool 
            : guessPool;

        for (String guess : poolToEvaluate) {
            double entropy = computeEntropy(guess, candidatePool);
            if (entropy > maxEntropy) {
                maxEntropy = entropy;
                bestGuess = guess;
            }
        }

        return bestGuess;
    }

    /**
     * 根据反馈模式过滤候选集（约束传播）
     */
    public void filterCandidates(String guess, int[] pattern) {
        List<String> filtered = new ArrayList<>();

        for (String word : candidates) {
            if (matchesPattern(word, guess, pattern)) {
                filtered.add(word);
            }
        }

        candidates = filtered;
    }

    /**
     * 判断某单词是否符合反馈模式
     */
    private boolean matchesPattern(String word, String guess, int[] pattern) {
        // 检查绿色约束
        for (int i = 0; i < 5; i++) {
            if (pattern[i] == 2 && word.charAt(i) != guess.charAt(i)) {
                return false;
            }
        }

        // 检查黄色和灰色约束
        for (int i = 0; i < 5; i++) {
            char c = guess.charAt(i);
            if (pattern[i] == 0) {
                // 灰色：该字母不能出现，除非该字母在其他位置是绿色或黄色
                int requiredCount = 0;
                for (int j = 0; j < 5; j++) {
                    if (guess.charAt(j) == c && pattern[j] > 0) {
                        requiredCount++;
                    }
                }
                int actualCount = 0;
                for (int j = 0; j < 5; j++) {
                    if (word.charAt(j) == c) actualCount++;
                }
                if (actualCount != requiredCount) return false;
            } else if (pattern[i] == 1) {
                // 黄色：字母必须存在，但不在此位置
                if (word.charAt(i) == c) return false;
                int requiredCount = 0;
                for (int j = 0; j < 5; j++) {
                    if (guess.charAt(j) == c && pattern[j] > 0) {
                        requiredCount++;
                    }
                }
                int actualCount = 0;
                for (int j = 0; j < 5; j++) {
                    if (word.charAt(j) == c) actualCount++;
                }
                if (actualCount < requiredCount) return false;
            }
        }

        return true;
    }

    /**
     * 执行一次完整求解
     * @param target 目标单词（用于模拟）
     * @param verbose 是否打印过程
     * @return 猜测次数，失败返回 -1
     */
    public int solve(String target, boolean verbose) {
        candidates = new ArrayList<>(allWords);
        target = target.toLowerCase();

        if (verbose) System.out.println("目标单词: " + target);

        for (int attempt = 1; attempt <= 6; attempt++) {
            String guess = selectBestGuess(allWords, candidates);
            if (guess == null) return -1;

            int[] pattern = computePattern(guess, target);

            if (verbose) {
                System.out.printf("第%d次: %s -> ", attempt, guess);
                printPattern(pattern);
                System.out.printf(" (候选集大小: %d)%n", candidates.size());
            }

            if (guess.equals(target)) {
                if (verbose) System.out.println("成功猜出!");
                return attempt;
            }

            filterCandidates(guess, pattern);
            if (candidates.isEmpty()) return -1;
        }

        return -1;
    }

    private void printPattern(int[] pattern) {
        for (int p : pattern) {
            if (p == 2) System.out.print("🟩");
            else if (p == 1) System.out.print("🟨");
            else System.out.print("⬜");
        }
    }

    /**
     * 批量测试求解性能
     */
    public void benchmark(int testCount) {
        int[] distribution = new int[7]; // 1-6次成功 + 失败

        for (int i = 0; i < testCount; i++) {
            String target = allWords.get(random.nextInt(allWords.size()));
            int attempts = solve(target, false);
            if (attempts == -1) distribution[6]++;
            else distribution[attempts - 1]++;
        }

        System.out.println("\n===  benchmark 结果 (测试 " + testCount + " 个单词) ===");
        for (int i = 0; i < 6; i++) {
            System.out.printf("%d次猜中: %d (%.2f%%)%n", 
                i + 1, distribution[i], 100.0 * distribution[i] / testCount);
        }
        System.out.printf("失败: %d (%.2f%%)%n", 
            distribution[6], 100.0 * distribution[6] / testCount);

        double avg = 0;
        for (int i = 0; i < 6; i++) avg += (i + 1) * distribution[i];
        avg /= (testCount - distribution[6]);
        System.out.printf("平均猜测次数(成功): %.2f%n", avg);
    }

    /**
     * 生成初始推荐词（基于全体单词的信息熵预计算）
     */
    public List<Map.Entry<String, Double>> getTopStartingWords(int n) {
        Map<String, Double> entropyMap = new HashMap<>();
        for (String word : allWords) {
            entropyMap.put(word, computeEntropy(word, allWords));
        }
        return entropyMap.entrySet().stream()
            .sorted(Map.Entry.<String, Double>comparingByValue().reversed())
            .limit(n)
            .collect(Collectors.toList());
    }

    public static void main(String[] args) throws IOException {
        // 需要一个5字母单词列表文件，每行一个单词
        WordleSolver solver = new WordleSolver("wordlist.txt");

        // 查看最佳开局词
        System.out.println("=== 最佳开局词 (Top 10) ===");
        var topWords = solver.getTopStartingWords(10);
        for (var entry : topWords) {
            System.out.printf("%s: %.4f bits%n", entry.getKey(), entry.getValue());
        }

        // 单次求解演示
        System.out.println("\n=== 单次求解演示 ===");
        solver.solve("crane", true);

        // 性能测试
        System.out.println("\n=== 批量测试 ===");
        solver.benchmark(100);
    }
}

五、复杂度分析

操作 时间复杂度 空间复杂度
计算反馈模式 O(5²) = O(1) O(1)
计算单次猜测熵 O(|W| × 1) = O(|W|) O(243)
选择最优猜测 O(|G| × |W|) O(1)
约束传播过滤 O(|W|) O(|W|)
单次完整求解 O(6 × |G| × |W|) O(|W|)

其中 |W| 为候选集大小，|G| 为猜测池大小。通过将猜测池限制为候选集，可将复杂度降为 O(6 × |W|²)。

六、算法优化技巧

  1. 缓存模式计算：对 (guess, target) 组合的结果进行缓存，避免重复计算
  2. 并行化熵计算：使用 Java Stream parallel() 并行计算多个猜测的熵值
  3. 预计算开局词：最佳开局词对所有目标都通用，可离线预计算
  4. 双重评估：当信息熵相同时，优先选择也在候选集中的词（猜对即胜利）

七、总结

Wordle 求解器展示了信息论在实际问题中的强大威力。通过将猜测问题建模为信息增益最大化，我们可以在平均约 3.5 次猜测内解决绝大多数 Wordle 谜题。约束传播机制则确保了每次反馈后搜索空间的高效缩减。这套框架也可推广到其他类似的信息反馈类猜谜游戏。

Tagged with: