一、游戏简介与算法目标
狼人杀（Werewolf/Mafia）是一款经典的多人社交推理游戏，通常由4-12名玩家参与，分为狼人阵营和好人阵营。游戏白天玩家通过发言和投票放逐疑似狼人的玩家，夜晚狼人秘密击杀好人。好人阵营的目标是找出并放逐所有狼人，狼人阵营的目标是在人数上压倒好人。
本文的核心算法目标包括：
1. 贝叶斯概率推理：根据每轮的发言、投票和死亡信息，更新每个玩家是狼人的后验概率
2. 逻辑约束传播：利用已知的角色信息和游戏逻辑规则，推导其他玩家的身份约束
3. 最优决策策略：基于概率模型选择最有价值的查验目标和投票对象
二、核心算法原理
2.1 贝叶斯概率更新
设玩家i是狼人的先验概率为 P(W_i)，观察到证据E后，后验概率为：
P(W_i | E) = P(E | W_i) × P(W_i) / P(E)
证据类型包括：
– 死亡信息：某玩家夜晚被杀，杀手大概率是狼人
– 投票模式：狼人倾向于保护同伴、嫁祸好人
– 发言一致性：狼人发言可能出现逻辑矛盾
2.2 逻辑约束传播
建立约束系统：
– 互斥约束：两个玩家不能同时为狼人（当狼人数量上限确定时）
– 团队约束：若A保护B，则A和B同阵营的概率提升
– 击杀约束：狼人必须每晚击杀一名好人
2.3 最优查验策略
预言家每晚可查验一名玩家。最优策略是选择当前信息熵最大的玩家（即最不确定的玩家）进行查验，以最大化信息增益。
三、Java完整实现
import java.util.*;
/**
* 狼人杀AI：贝叶斯概率推理与逻辑约束传播
* 核心算法：贝叶斯更新、信息熵计算、约束传播
*/
public class WerewolfAI {
// 玩家角色枚举
enum Role {
WEREWOLF, // 狼人
VILLAGER, // 平民
SEER, // 预言家
WITCH, // 女巫
HUNTER // 猎人
}
// 玩家状态
static class Player {
int id;
String name;
Role actualRole; // 真实角色（对AI不可见）
boolean alive; // 是否存活
// 概率模型（对AI可见）
double werewolfProb; // 是狼人的概率
double seerProb; // 是预言家的概率
// 行为记录
List<Integer> votedFor; // 投票记录
List<Integer> protectedPlayers; // 保护/辩护过的玩家
List<String> claims; // 身份声明
Player(int id, String name) {
this.id = id;
this.name = name;
this.alive = true;
this.werewolfProb = 0.3; // 初始先验：假设约30%玩家是狼人
this.seerProb = 0.1;
this.votedFor = new ArrayList<>();
this.protectedPlayers = new ArrayList<>();
this.claims = new ArrayList<>();
}
}
// 游戏状态
static class GameState {
List<Player> players;
int totalWerewolves; // 狼人总数
int aliveWerewolves; // 存活狼人数
int aliveVillagers; // 存活好人数
int day; // 当前天数
List<Integer> deathLog; // 死亡记录
Map<Integer, Boolean> seerResults; // 预言家查验结果
GameState(int playerCount, int werewolfCount) {
this.players = new ArrayList<>();
this.totalWerewolves = werewolfCount;
this.aliveWerewolves = werewolfCount;
this.aliveVillagers = playerCount - werewolfCount;
this.day = 1;
this.deathLog = new ArrayList<>();
this.seerResults = new HashMap<>();
}
}
private GameState state;
private Random random;
private int myId; // AI自身的玩家ID
public WerewolfAI(int playerCount, int werewolfCount, int myId) {
this.state = new GameState(playerCount, werewolfCount);
this.random = new Random();
this.myId = myId;
initializePlayers(playerCount);
}
private void initializePlayers(int count) {
for (int i = 0; i < count; i++) {
state.players.add(new Player(i, "Player" + i));
}
}
/**
* 贝叶斯概率更新核心算法
* 根据新证据更新某玩家是狼人的概率
* @param playerId 目标玩家
* @param evidence 证据类型："vote_protect", "vote_betray", "killed", "seer_check"
* @param likelihood 在该证据下是狼人的似然度(0-1)
*/
public void bayesianUpdate(int playerId, String evidence, double likelihood) {
Player p = state.players.get(playerId);
double prior = p.werewolfProb;
// 贝叶斯公式: P(W|E) = P(E|W) * P(W) / P(E)
// P(E) = P(E|W)*P(W) + P(E|~W)*P(~W)
double pEvidenceGivenWolf = likelihood;
double pEvidenceGivenNotWolf = 1.0 - likelihood;
double pEvidence = pEvidenceGivenWolf * prior
+ pEvidenceGivenNotWolf * (1 - prior);
if (pEvidence < 1e-10) pEvidence = 1e-10; // 避免除零
double posterior = (pEvidenceGivenWolf * prior) / pEvidence;
// 限制概率范围
p.werewolfProb = Math.max(0.01, Math.min(0.99, posterior));
System.out.printf("贝叶斯更新: %s 因[%s] 概率 %.3f -> %.3f%n",
p.name, evidence, prior, p.werewolfProb);
}
/**
* 处理投票证据
* 狼人倾向于：保护同伴（不投同伴）、嫁祸好人（集中投好人）
*/
public void processVote(int voterId, int targetId) {
Player voter = state.players.get(voterId);
Player target = state.players.get(targetId);
voter.votedFor.add(targetId);
// 如果投的是已经被高度怀疑是狼人的玩家，投票者是好人的概率上升
if (target.werewolfProb > 0.6) {
// 这是好人行为：帮助找出狼人
bayesianUpdate(voterId, "vote_betray", 0.3);
}
// 如果投的是被高度怀疑是好人的玩家，投票者是狼人的概率上升
else if (target.werewolfProb < 0.3) {
// 这是狼人行为：嫁祸好人
bayesianUpdate(voterId, "vote_protect", 0.7);
}
// 更新被投玩家的概率：被多人集中投票可能是狼人
long votesAgainst = state.players.stream()
.filter(p -> p.alive && p.votedFor.contains(targetId))
.count();
if (votesAgainst >= 2) {
bayesianUpdate(targetId, "multi_votes", 0.6);
}
}
/**
* 处理夜晚死亡信息
* 狼人通常杀他们认为威胁最大的好人（如跳预言家的）
*/
public void processNightKill(int victimId) {
state.deathLog.add(victimId);
state.players.get(victimId).alive = false;
// 被杀的玩家几乎不可能是狼人（狼人不会自杀，除非特殊规则）
bayesianUpdate(victimId, "killed", 0.05);
// 如果受害者之前被高度怀疑是狼人，说明狼人在做"狼踩狼"的高级操作
Player victim = state.players.get(victimId);
if (victim.werewolfProb > 0.5) {
// 找出其他狼人嫌疑高的玩家，提升其概率
for (Player p : state.players) {
if (p.id != victimId && p.alive && p.werewolfProb > 0.4) {
bayesianUpdate(p.id, "wolf_on_wolf", 0.65);
}
}
}
}
/**
* 处理预言家查验结果
* @param checkedId 被查验玩家
* @param isWerewolf true表示是狼人
*/
public void processSeerResult(int checkedId, boolean isWerewolf) {
state.seerResults.put(checkedId, isWerewolf);
Player p = state.players.get(checkedId);
if (isWerewolf) {
p.werewolfProb = 0.95; // 预言家查验为狼人
} else {
p.werewolfProb = 0.05; // 预言家查验为好人
}
System.out.printf("预言家查验: %s 是%s%n", p.name, isWerewolf ? "狼人" : "好人");
}
/**
* 信息熵计算
* H(X) = -Σ p(x) * log2(p(x))
* 熵越大表示不确定性越高，是优先查验的目标
*/
public double calculateEntropy(Player p) {
double pWolf = p.werewolfProb;
double pNotWolf = 1 - pWolf;
// 避免log(0)
if (pWolf < 1e-10 || pNotWolf < 1e-10) return 0;
return -(pWolf * Math.log(pWolf) / Math.log(2)
+ pNotWolf * Math.log(pNotWolf) / Math.log(2));
}
/**
* 最优查验目标选择（信息熵最大）
*/
public int selectBestSeerTarget() {
double maxEntropy = -1;
int bestTarget = -1;
for (Player p : state.players) {
if (p.id == myId || !p.alive || state.seerResults.containsKey(p.id)) {
continue; // 跳过自己、死者和已查验的
}
double entropy = calculateEntropy(p);
if (entropy > maxEntropy) {
maxEntropy = entropy;
bestTarget = p.id;
}
}
return bestTarget;
}
/**
* 约束传播：根据已知信息推导其他玩家的身份约束
* 核心约束：狼人总数固定，若已确定k个狼人，则剩余狼人在其他玩家中
*/
public void propagateConstraints() {
// 统计已确定/高度怀疑的狼人
List<Player> confirmedWolves = new ArrayList<>();
List<Player> confirmedVillagers = new ArrayList<>();
for (Player p : state.players) {
if (!p.alive) continue;
if (p.werewolfProb > 0.85) confirmedWolves.add(p);
else if (p.werewolfProb < 0.15) confirmedVillagers.add(p);
}
int remainingWolves = state.totalWerewolves - confirmedWolves.size();
int uncertainPlayers = state.players.size() - confirmedWolves.size()
- confirmedVillagers.size();
if (uncertainPlayers > 0 && remainingWolves >= 0) {
// 剩余不确定玩家中，每个是狼人的基础概率
double baseProb = (double) remainingWolves / uncertainPlayers;
for (Player p : state.players) {
if (!p.alive || p.werewolfProb > 0.85 || p.werewolfProb < 0.15) {
continue;
}
// 向基础概率靠拢（约束传播平滑更新）
p.werewolfProb = 0.7 * p.werewolfProb + 0.3 * baseProb;
p.werewolfProb = Math.max(0.05, Math.min(0.95, p.werewolfProb));
}
}
System.out.printf("约束传播: 已确定狼人%d个，剩余狼人%d个，不确定玩家%d个%n",
confirmedWolves.size(), remainingWolves, uncertainPlayers);
}
/**
* 最优投票决策：投当前狼人概率最高且存活的玩家
*/
public int selectBestVoteTarget() {
double maxProb = -1;
int bestTarget = -1;
for (Player p : state.players) {
if (p.id == myId || !p.alive) continue;
if (p.werewolfProb > maxProb) {
maxProb = p.werewolfProb;
bestTarget = p.id;
}
}
return bestTarget;
}
/**
* 打印当前概率分布
*/
public void printProbabilities() {
System.out.println("\n=== 当前玩家概率分布 ===");
System.out.printf("%-10s %-8s %-10s %-12s %-15s%n",
"玩家", "状态", "狼人概率", "信息熵", "投票记录");
System.out.println("-".repeat(60));
for (Player p : state.players) {
String status = p.alive ? "存活" : "死亡";
double entropy = calculateEntropy(p);
String votes = p.votedFor.isEmpty() ? "无" :
p.votedFor.toString();
System.out.printf("%-10s %-8s %-10.3f %-12.3f %-15s%n",
p.name, status, p.werewolfProb, entropy, votes);
}
System.out.println();
}
/**
* 模拟一局游戏的推理过程
*/
public void simulateGame() {
System.out.println("=== 狼人杀AI概率推理模拟 ===");
System.out.printf("玩家数: %d，狼人数: %d，AI编号: Player%d%n%n",
state.players.size(), state.totalWerewolves, myId);
// 初始概率
printProbabilities();
// 模拟第1天：Player2被杀
System.out.println("【第1夜】Player2被狼人击杀");
processNightKill(2);
propagateConstraints();
printProbabilities();
// AI是预言家，查验Player3
int seerTarget = selectBestSeerTarget();
System.out.println("【第1夜】AI预言家查验 Player" + seerTarget);
processSeerResult(seerTarget, true); // 假设查验结果为狼人
propagateConstraints();
printProbabilities();
// 白天投票
System.out.println("【第1天白天】玩家投票");
processVote(1, 3);
processVote(4, 3);
processVote(5, 1);
propagateConstraints();
printProbabilities();
// 第2夜
System.out.println("【第2夜】Player5被狼人击杀");
processNightKill(5);
propagateConstraints();
printProbabilities();
// 最终决策
int voteTarget = selectBestVoteTarget();
System.out.println("【AI决策】最优投票目标: Player" + voteTarget
+ " (狼人概率: " + String.format("%.3f",
state.players.get(voteTarget).werewolfProb) + ")");
int nextSeer = selectBestSeerTarget();
if (nextSeer != -1) {
System.out.println("【AI决策】下次查验目标: Player" + nextSeer
+ " (信息熵: " + String.format("%.3f",
calculateEntropy(state.players.get(nextSeer))) + ")");
}
}
public static void main(String[] args) {
WerewolfAI ai = new WerewolfAI(6, 2, 0); // 6人局，2狼人，AI是Player0
ai.simulateGame();
}
}
四、算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 贝叶斯更新 | O(1) | O(1) | 单玩家概率更新 |
| 约束传播 | O(n) | O(1) | n为玩家数 |
| 信息熵计算 | O(1) | O(1) | 单玩家熵值 |
| 最优查验选择 | O(n) | O(1) | 遍历所有存活玩家 |
| 最优投票选择 | O(n) | O(1) | 遍历所有存活玩家 |
| 每轮完整推理 | O(n²) | O(n) | 包含所有更新和约束传播 |
五、扩展思考
- 更复杂的似然模型：可引入玩家历史行为模式、发言情感分析等特征，训练逻辑回归或神经网络模型替代固定的似然值。
- 多轮信息累积：引入时间衰减因子，较早的投票行为对当前概率的影响逐渐降低。
- 联盟检测：狼人倾向于形成隐性联盟，可用图论方法检测投票网络中的异常聚类。
- 反侦察策略：狼人AI可学习”深水狼”策略——故意表现像好人，甚至牺牲同伴换取信任。
六、总结
本文通过狼人杀游戏讲解了贝叶斯概率推理、信息熵计算和逻辑约束传播三个核心算法。Java实现构建了一个可运行的AI推理系统，能够根据游戏事件动态更新玩家身份概率，并基于信息论原则做出最优决策。该框架可扩展至更复杂的社交推理和不确定信息决策场景。
