每日算法 — 使用java实现谁是卧底：逻辑推理与信息熵最优提问策略

引言

“谁是卧底”是一款考验语言表达与逻辑推理的社交游戏：多数玩家拿到相同的平民词，少数卧底拿到相似但不同的词。玩家轮流描述自己的词，每轮投票淘汰最可疑的人，卧底需隐藏身份，平民需找出卧底。本文将用Java实现一个AI玩家，核心算法包括词向量相似度计算、贝叶斯概率更新与信息熵最优提问策略，让AI能够像人类一样进行推理和发言。

核心算法一：词向量相似度与语义空间建模

AI首先需要理解词语之间的语义关系。采用简化的字符特征向量方法：将词语映射到特征空间，通过特征重叠度衡量语义相似性。

特征提取策略

1. 字符级特征：词语包含的汉字集合
2. 语义类别特征：通过预定义词库标注类别（动物、食物、职业等）
3. 属性特征：通过外部知识库获取的属性标签（大小、颜色、用途等）

import java.util.*;

/**
 * 词语语义特征向量
 */
class WordFeature {
    String word;
    Set<String> chars;           // 字符集合
    Set<String> categories;      // 语义类别
    Set<String> attributes;      // 属性标签
    Map<String, Double> embedding; // 简化的特征权重向量

    public WordFeature(String word) {
        this.word = word;
        this.chars = new HashSet<>();
        this.categories = new HashSet<>();
        this.attributes = new HashSet<>();
        this.embedding = new HashMap<>();
        extractChars(word);
    }

    private void extractChars(String w) {
        for (char c : w.toCharArray()) {
            chars.add(String.valueOf(c));
        }
    }

    public void addCategory(String cat) { categories.add(cat); }
    public void addAttribute(String attr) { attributes.add(attr); }

    /**
     * 设置特征权重（用于TF-IDF风格的加权）
     */
    public void setFeatureWeight(String feature, double weight) {
        embedding.put(feature, weight);
    }
}

/**
 * 语义相似度计算器
 */
class SemanticSimilarity {

    /**
     * Jaccard相似度：特征集合的交集/并集
     */
    public static double jaccard(Set<String> a, Set<String> b) {
        if (a.isEmpty() && b.isEmpty()) return 1.0;
        Set<String> intersection = new HashSet<>(a);
        intersection.retainAll(b);
        Set<String> union = new HashSet<>(a);
        union.addAll(b);
        return (double) intersection.size() / union.size();
    }

    /**
     * 综合语义相似度：融合字符、类别、属性三层特征
     */
    public static double computeSimilarity(WordFeature w1, WordFeature w2) {
        double charSim = jaccard(w1.chars, w2.chars);
        double catSim = jaccard(w1.categories, w2.categories);
        double attrSim = jaccard(w1.attributes, w2.attributes);

        // 加权融合：类别相似度权重最高，属性次之，字符最低
        return charSim * 0.2 + catSim * 0.5 + attrSim * 0.3;
    }

    /**
     * 余弦相似度（用于稠密向量）
     */
    public static double cosineSimilarity(Map<String, Double> v1,
                                           Map<String, Double> v2) {
        double dot = 0, norm1 = 0, norm2 = 0;
        Set<String> allKeys = new HashSet<>(v1.keySet());
        allKeys.addAll(v2.keySet());

        for (String key : allKeys) {
            double a = v1.getOrDefault(key, 0.0);
            double b = v2.getOrDefault(key, 0.0);
            dot += a * b;
            norm1 += a * a;
            norm2 += b * b;
        }
        if (norm1 < 1e-9 || norm2 < 1e-9) return 0;
        return dot / (Math.sqrt(norm1) * Math.sqrt(norm2));
    }
}

核心算法二：贝叶斯概率推理

AI需要根据其他玩家的发言不断更新对每个玩家身份的置信度。设 $H_i$ 表示”玩家i是卧底”的假设，$D$ 表示观测到的发言数据，则根据贝叶斯定理：

$$P(H_i | D) = \frac{P(D | H_i) \cdot P(H_i)}{P(D)}$$

似然函数设计

观测到玩家 $j$ 的发言 $s_j$ 后，计算该发言来自平民词 $w_{civilian}$ 或卧底词 $w_{undercover}$ 的可能性：

$$P(s_j | \text{player j is civilian}) \propto \text{sim}(s_j, w_{civilian})$$
$$P(s_j | \text{player j is undercover}) \propto \text{sim}(s_j, w_{undercover})$$

其中 $\text{sim}$ 为发言内容与词语的语义相似度。

/**
 * 玩家状态与概率模型
 */
class Player {
    int id;
    String role; // "CIVILIAN" or "UNDERCOVER" or "UNKNOWN"
    boolean alive;
    List<String> statements; // 历史发言记录
    double undercoverProb;   // 当前被判定为卧底的后验概率

    public Player(int id) {
        this.id = id;
        this.role = "UNKNOWN";
        this.alive = true;
        this.statements = new ArrayList<>();
        this.undercoverProb = 0.5; // 先验概率
    }
}

/**
 * 贝叶斯推理引擎
 */
class BayesianReasoner {
    private WordFeature civilianWord;
    private WordFeature undercoverWord;
    private List<Player> players;
    private int undercoverCount;

    public BayesianReasoner(String civilian, String undercover,
                            int playerCount, int undercoverCount) {
        this.civilianWord = new WordFeature(civilian);
        this.undercoverWord = new WordFeature(undercover);
        this.undercoverCount = undercoverCount;
        this.players = new ArrayList<>();
        for (int i = 0; i < playerCount; i++) {
            players.add(new Player(i));
        }
        // 设置初始先验
        double prior = (double) undercoverCount / playerCount;
        for (Player p : players) {
            p.undercoverProb = prior;
        }
    }

    /**
     * 添加语义知识到词特征
     */
    public void enrichWordKnowledge(String word, String category,
                                     String... attributes) {
        WordFeature target = word.equals(civilianWord.word) ?
                             civilianWord : undercoverWord;
        target.addCategory(category);
        for (String attr : attributes) {
            target.addAttribute(attr);
        }
    }

    /**
     * 处理一轮新发言，更新所有玩家的概率
     * @param speakerId 发言玩家ID
     * @param statement 发言内容
     */
    public void processStatement(int speakerId, String statement) {
        Player speaker = players.get(speakerId);
        speaker.statements.add(statement);

        // 计算该发言与两个词的相似度
        WordFeature stmtFeature = new WordFeature(statement);
        double simCivilian = SemanticSimilarity.computeSimilarity(
            stmtFeature, civilianWord);
        double simUndercover = SemanticSimilarity.computeSimilarity(
            stmtFeature, undercoverWord);

        // 计算似然比
        double likelihoodRatio = (simUndercover + 0.1) / (simCivilian + 0.1);

        // 贝叶斯更新：P(卧底|发言) ∝ P(发言|卧底) * P(卧底)
        double prior = speaker.undercoverProb;
        double posterior = likelihoodRatio * prior;
        // 归一化（简化处理：限制在合理范围）
        speaker.undercoverProb = Math.max(0.01, Math.min(0.99,
            posterior / (posterior + (1 - prior))));

        // 传播约束：如果某玩家概率极低，将剩余概率质量分配给其他玩家
        normalizeProbabilities();
    }

    /**
     * 归一化概率，使其满足卧底人数约束
     */
    private void normalizeProbabilities() {
        double totalProb = 0;
        int aliveCount = 0;
        for (Player p : players) {
            if (p.alive) {
                totalProb += p.undercoverProb;
                aliveCount++;
            }
        }
        if (aliveCount == 0) return;

        double expectedTotal = undercoverCount *
            ((double) aliveCount / players.size());
        if (Math.abs(totalProb - expectedTotal) < 0.1) return;

        // 线性缩放使总和接近期望值
        double scale = expectedTotal / Math.max(totalProb, 0.001);
        for (Player p : players) {
            if (p.alive) {
                p.undercoverProb = Math.max(0.01, Math.min(0.95,
                    p.undercoverProb * scale));
            }
        }
    }

    /**
     * 获取当前最可疑的玩家
     */
    public int getMostSuspiciousPlayer() {
        int bestId = -1;
        double maxProb = -1;
        for (Player p : players) {
            if (p.alive && p.undercoverProb > maxProb) {
                maxProb = p.undercoverProb;
                bestId = p.id;
            }
        }
        return bestId;
    }

    public List<Player> getPlayers() { return players; }
}

核心算法三：信息熵最优提问策略

AI作为发言者时，需要生成既能帮助队友识别卧底、又不暴露自己身份的描述。采用信息增益最大化策略：选择能够最大程度区分平民词与卧底词的特征进行描述。

信息熵计算

特征 $f$ 的信息增益：

$$IG(f) = H(Y) – H(Y | f)$$

其中 $H(Y)$ 为当前身份分布的熵，$H(Y|f)$ 为观察到特征 $f$ 后的条件熵。

/**
 * 信息熵驱动的发言生成器
 */
class StatementGenerator {
    private WordFeature myWord;
    private WordFeature otherWord; // 另一个候选词（AI不知道自己是平民还是卧底）
    private List<String> usedFeatures; // 已用过的特征（避免重复）

    public StatementGenerator(String myWord, String otherWord) {
        this.myWord = new WordFeature(myWord);
        this.otherWord = new WordFeature(otherWord);
        this.usedFeatures = new ArrayList<>();
    }

    /**
     * 生成最优描述特征
     * @return 推荐的发言描述
     */
    public String generateOptimalStatement() {
        // 候选特征池
        List<String> candidateFeatures = new ArrayList<>();
        candidateFeatures.addAll(myWord.categories);
        candidateFeatures.addAll(myWord.attributes);

        String bestFeature = null;
        double maxInfoGain = -1;

        for (String feature : candidateFeatures) {
            if (usedFeatures.contains(feature)) continue;

            // 计算该特征的信息增益
            double ig = calculateInfoGain(feature);
            if (ig > maxInfoGain) {
                maxInfoGain = ig;
                bestFeature = feature;
            }
        }

        if (bestFeature != null) {
            usedFeatures.add(bestFeature);
            return constructStatement(bestFeature);
        }
        //  fallback：给出模糊描述
        return "这是一种常见的事物";
    }

    /**
     * 计算某特征的信息增益
     * 高信息增益 = 该特征强烈区分两个词
     */
    private double calculateInfoGain(String feature) {
        boolean hasInMine = myWord.categories.contains(feature) ||
                            myWord.attributes.contains(feature);
        boolean hasInOther = otherWord.categories.contains(feature) ||
                             otherWord.attributes.contains(feature);

        // 理想特征：一个词有，另一个词没有
        if (hasInMine && !hasInOther) return 2.0;  // 强烈指向自己是平民
        if (!hasInMine && hasInOther) return -1.0; // 危险！会暴露自己是卧底
        if (hasInMine && hasInOther) return 0.1;   // 两个词都有，信息量低
        return 0.0; // 两个词都没有
    }

    /**
     * 将特征构造为自然语言描述
     */
    private String constructStatement(String feature) {
        Map<String, String> templates = new HashMap<>();
        templates.put("动物", "这是一种动物");
        templates.put("食物", "可以吃的东西");
        templates.put("职业", "这是一种工作");
        templates.put("大型", "体型比较大");
        templates.put("小型", "体型小巧");
        templates.put("水生", "生活在水里");
        templates.put("陆地", "生活在陆地上");
        templates.put("飞行", "可以在天上飞");
        templates.put("哺乳动物", "是哺乳动物");
        templates.put("家禽", "属于家禽类");

        return templates.getOrDefault(feature,
            "这和" + feature + "有关");
    }

    /**
     * 投票策略：基于贝叶斯推理结果投票给最可疑玩家
     */
    public int vote(BayesianReasoner reasoner, int myId) {
        int target = reasoner.getMostSuspiciousPlayer();
        if (target == myId) {
            // 如果自己最可疑，投票给第二可疑的（自保）
            double secondMax = -1;
            int secondTarget = -1;
            for (Player p : reasoner.getPlayers()) {
                if (p.alive && p.id != myId &&
                    p.undercoverProb > secondMax) {
                    secondMax = p.undercoverProb;
                    secondTarget = p.id;
                }
            }
            return secondTarget;
        }
        return target;
    }
}

完整游戏流程与AI决策

/**
 * 谁是卧底游戏主控
 */
public class UndercoverGame {
    private List<Player> players;
    private BayesianReasoner reasoner;
    private StatementGenerator aiGenerator;
    private String civilianWord;
    private String undercoverWord;
    private int aiPlayerId;

    public UndercoverGame(int playerCount, int undercoverCount,
                          String civWord, String ucWord, int aiId) {
        this.civilianWord = civWord;
        this.undercoverWord = ucWord;
        this.aiPlayerId = aiId;
        this.reasoner = new BayesianReasoner(civWord, ucWord,
                                              playerCount, undercoverCount);
        this.aiGenerator = new StatementGenerator(civWord, ucWord);
        this.players = reasoner.getPlayers();

        // 预加载语义知识（实际应用中可对接词库/知识图谱）
        reasoner.enrichWordKnowledge(civWord, "动物", "大型", "陆地", "哺乳动物");
        reasoner.enrichWordKnowledge(ucWord, "动物", "小型", "陆地", "家禽");
    }

    /**
     * 执行一轮发言与投票
     */
    public void playRound() {
        System.out.println("=== 新一轮开始 ===");

        // 1. 每位存活玩家发言
        for (Player p : players) {
            if (!p.alive) continue;

            String statement;
            if (p.id == aiPlayerId) {
                statement = aiGenerator.generateOptimalStatement();
                System.out.println("AI玩家" + p.id + "发言：\"" + statement + "\"");
            } else {
                // 模拟人类玩家发言（简化：随机生成）
                statement = simulateHumanStatement(p.id);
                System.out.println("玩家" + p.id + "发言：\"" + statement + "\"");
            }

            // 所有玩家（包括AI）根据此发言更新概率
            for (int observerId = 0; observerId < players.size(); observerId++) {
                if (players.get(observerId).alive) {
                    reasoner.processStatement(p.id, statement);
                }
            }
        }

        // 2. 显示当前概率分布
        System.out.println("\n当前嫌疑概率：");
        for (Player p : players) {
            if (p.alive) {
                System.out.printf("  玩家%d: %.2f%%\n", p.id,
                    p.undercoverProb * 100);
            }
        }

        // 3. 投票淘汰
        Map<Integer, Integer> votes = new HashMap<>();
        for (Player p : players) {
            if (!p.alive) continue;
            int voteTarget;
            if (p.id == aiPlayerId) {
                voteTarget = aiGenerator.vote(reasoner, aiPlayerId);
            } else {
                voteTarget = reasoner.getMostSuspiciousPlayer();
                if (voteTarget == p.id) {
                    // 人类玩家不自投，随机选其他
                    for (Player other : players) {
                        if (other.alive && other.id != p.id) {
                            voteTarget = other.id;
                            break;
                        }
                    }
                }
            }
            votes.merge(voteTarget, 1, Integer::sum);
            System.out.println("玩家" + p.id + "投票给玩家" + voteTarget);
        }

        // 淘汰得票最高者
        int maxVotes = -1;
        int eliminated = -1;
        for (Map.Entry<Integer, Integer> e : votes.entrySet()) {
            if (e.getValue() > maxVotes) {
                maxVotes = e.getValue();
                eliminated = e.getKey();
            }
        }
        if (eliminated >= 0) {
            players.get(eliminated).alive = false;
            System.out.println("\n玩家" + eliminated + "被淘汰！");
        }

        // 4. 检查游戏结束
        checkGameOver();
    }

    private String simulateHumanStatement(int playerId) {
        // 简化模拟：70%概率说与平民词相关的特征
        String[] civFeatures = {"这是动物", "比较大", "有四条腿", "哺乳动物"};
        String[] ucFeatures = {"会飞", "比较小", "家禽", "有两条腿"};
        boolean isUndercover = (playerId % 3 == 0); // 简化：假设部分玩家是卧底
        String[] pool = isUndercover ? ucFeatures : civFeatures;
        return pool[(int)(Math.random() * pool.length)];
    }

    private void checkGameOver() {
        int aliveCivilians = 0;
        int aliveUndercover = 0;
        for (Player p : players) {
            if (!p.alive) continue;
            // 简化：根据初始设定判断（实际应跟踪真实身份）
            if (p.id % 3 != 0) aliveCivilians++;
            else aliveUndercover++;
        }
        if (aliveUndercover == 0) {
            System.out.println("平民胜利！");
        } else if (aliveUndercover >= aliveCivilians) {
            System.out.println("卧底胜利！");
        }
    }

    public static void main(String[] args) {
        // 示例：平民词"大象"，卧底词"公鸡"，6人局1卧底，AI为玩家0
        UndercoverGame game = new UndercoverGame(6, 1,
            "大象", "公鸡", 0);
        for (int i = 0; i < 5; i++) {
            game.playRound();
            System.out.println();
        }
    }
}

算法复杂度分析

扩展思路

1. 深度词向量：对接预训练中文词向量（如Word2Vec、BERT），替代手工特征工程
2. 图神经网络：将玩家发言构建为异构图，用GNN推理隐藏关系
3. 多轮对话记忆：引入LSTM/Transformer编码长程发言上下文，捕捉矛盾陈述
4. 对抗训练：训练两个AI互相对抗，一个隐藏身份，一个推理识别

总结

本文实现了一个”谁是卧底”AI玩家，核心算法包括：
– 多层语义相似度，融合字符、类别、属性三层特征评估词语关联
– 贝叶斯概率更新，根据每轮发言动态修正玩家身份的后验概率
– 信息增益最大化发言策略，选择最能区分两个词的特征进行描述

该框架是不完全信息博弈的典型实践，其概率推理机制可迁移至狼人杀、剧本杀等同类社交推理游戏的AI设计中。