阿瓦隆是典型的”不完全信息 + 有限发言”推理游戏：好人只能看到自己的身份，坏人互相认识，所有人都要靠投票记录推断阵营。本文用 Java 把这件事形式化为约束满足问题：把每一条投票与每一句发言翻译成逻辑约束，用弧一致性（AC-3）逐步收敛候选世界集，再用信息熵挑选最有判别力的任务分配方案，给出可运行的推理引擎与收敛性分析。
一、把”我相信谁”变成一道数学题
人类玩阿瓦隆靠的是”感觉”：谁投了反对票、谁坚持要带自己去任务、谁在第 3 轮突然改口。但这些”感觉”背后其实都是可以形式化的约束：
- 规则约束：5 人局中 2 名坏人（莫甘娜、刺客）彼此认识；梅林知道所有坏人；派西维尔看到梅林和莫甘娜但分不清。
- 行为约束：如果某玩家是好人，他投反对票多半因为怀疑队伍里有坏人；如果他是坏人，他投反对票可能只是为了让任务失败。
- 发言约束：说”我认为 X 是坏人”的玩家，在后续轮次里的投票行为必须与其声明一致，否则产生矛盾。
关键在于：约束不是绝对的，而是概率性的。好人也会误判，坏人也会伪装。所以不能简单地做逻辑演绎，而要在”候选世界”（每种可能的身份分配 + 每条信息）上做贝叶斯更新。
本文的实现分三层：
- 世界生成：枚举所有合法的身份分配（5 人局只有 20 种左右）
- 约束过滤：用 AC-3 剔除与已观测行为矛盾的世界
- 熵驱动决策：选择能让剩余世界集”对半分裂”最快的任务分配
二、身份分配的世界表示
阿瓦隆 5 人基础局的角色集合是固定的：梅林、派西维尔、2 名坏人（莫甘娜 + 刺客）、1 名忠臣。世界就是一个把角色映射到玩家编号的数组。
public final class AvalonSolver {
public static final int N = 5;
/** 角色编码 */
static final int MERLIN = 0, PERCIVAL = 1, ASSASSIN = 2, MORGANA = 3, LOYAL = 4;
/** 一个世界：world[player] = role */
record World(int[] world) {
boolean isEvil(int p) { return world[p] == ASSASSIN || world[p] == MORGANA; }
}
/** 枚举所有合法身份分配（角色互不相同，坏人可互换 → 去重后仅需固定坏人集合） */
static List<World> enumerateWorlds() {
List<World> out = new ArrayList<>();
for (int merlin = 0; merlin < N; merlin++) {
for (int percival = 0; percival < N; percival++) {
if (percival == merlin) continue;
for (int a = 0; a < N; a++) {
if (a == merlin || a == percival) continue;
for (int m = 0; m < N; m++) {
if (m == merlin || m == percival || m == a) continue;
int loyal = 0;
while (loyal == merlin || loyal == percival || loyal == a || loyal == m) loyal++;
int[] w = new int[N];
w[merlin] = MERLIN; w[percival] = PERCIVAL;
w[a] = ASSASSIN; w[m] = MORGANA; w[loyal] = LOYAL;
out.add(new World(w));
}
}
}
}
return out; // 5 × 4 × 3 × 2 = 120，但刺客/莫甘娜互换是同一"坏人集合"
}
}
为什么 120 种而不是 20 种。 刺客和莫甘娜是两个不同角色，但他们的”可见信息”几乎对称（都是坏人、都认识对方），唯一区别是刺客在最后有刺杀权。所以推理阶段应当把两人视为同一类，只在最终刺杀决策时区分——这是减少 6 倍搜索量的关键简化。
/** 按"坏人集合"去重，得到等价类代表 */
static List<World> collapseEvilPairs(List<World> worlds) {
Map<String, World> rep = new LinkedHashMap<>();
for (World w : worlds) {
String key = evilSetKey(w); // 仅由两名坏人编号决定
rep.putIfAbsent(key, w);
}
return new ArrayList<>(rep.values());
}
三、观测建模：每次投票都是一条约束
一次任务投票的观测包含：队伍成员 team、投票者 voter、投票结果 approve/deny、以及任务是否失败。把这些塞进一个观测记录：
record Vote(int[] team, int voter, boolean approve, int round, boolean questFailed) {}
record Speech(int speaker, int target, boolean claimsEvil, int round) {}
然后定义”某个世界与某个观测的一致性分数”。这里走软约束（概率化）而非硬过滤，因为硬过滤会很快把所有世界都杀掉：
/** 返回世界 w 解释观测 o 的似然（0~1），越大越合理 */
double likelihood(World w, Vote o) {
boolean voterEvil = w.isEvil(o.voter());
boolean teamHasEvil = false;
for (int p : o.team()) if (w.isEvil(p)) teamHasEvil = true;
if (!voterEvil) {
// 好人：队伍里有坏人 → 更可能反对（但不是必然，好人也会误判）
double pDeny = teamHasEvil ? 0.75 : 0.20;
return o.approve() ? 1 - pDeny : pDeny;
} else {
// 坏人：队伍里有队友做任务 → 倾向赞成（想混进去破坏）
// 队伍全是好人 → 倾向反对（不想让好人顺利通过）
double pDeny = teamHasEvil ? 0.20 : 0.80;
return o.approve() ? 1 - pDeny : pDeny;
}
}
四个 0.75 / 0.20 / 0.20 / 0.80 是这套模型的核心参数。它们不能随便写：好人反对的概率必须显著高于随机（否则模型无法区分阵营），但也不能设成 0.99（否则一次误判就把真实世界权重清零，模型变脆）。
发言约束更微妙。玩家说”我认为 X 是坏人”时，用同样的软约束建模：
double likelihood(World w, Speech o) {
boolean spkEvil = w.isEvil(o.speaker());
boolean tgtEvil = w.isEvil(o.target());
if (!spkEvil && tgtEvil) return 0.7; // 好人说对了
if (!spkEvil && !tgtEvil) return 0.4; // 好人误判
if (spkEvil && !tgtEvil) return 0.65; // 坏人甩锅好人（最常见）
if (spkEvil && tgtEvil) return 0.5; // 坏人指认同伙（双簧），也可能发生
return 0.5;
}
注意最后一行：坏人指认坏人并非不可能（”双簧”是经典骗术）。如果把它设成 0，模型就会被一次双簧彻底骗过去。
四、AC-3 式的约束传播
有了软约束，逐世界累乘似然就够了。但真实对局里观测会很多（5 轮 × 5 人投票 + 若干发言），逐轮重算全部 120 个世界 × 全部观测是 O(120 × 观测数)，虽然不算大，但有一个更好的做法：只重算受影响的子集。
这就是 AC-3 的思想移植：每当观测 o 到来，只有那些”对 o 的似然不为常数”的世界需要更新权重。对于一个”好人投了反对票”的观测，只有涉及 team 成员身份的世界才有不同似然。
final class BeliefState {
private final List<World> worlds;
private final double[] weight; // 归一化后的后验
/** 增量更新：只重算 affected 集合里的世界 */
void observe(Predicate<World> affected, Function<World, Double> lik) {
double sum = 0;
for (int i = 0; i < worlds.size(); i++) {
if (affected.test(worlds.get(i))) {
weight[i] *= lik.apply(worlds.get(i));
}
sum += weight[i];
}
if (sum <= 0) { renormalizeAll(); return; }
for (int i = 0; i < weight.length; i++) weight[i] /= sum;
}
}
sum <= 0 的兜底是必须的：软约束的连乘在长对局后会下溢到 0（20 条观测 × 0.2 的似然已是 1e-14，再加几条就碰 double 下限附近）。应对办法是每次更新后做一次归一化，并且在权重差异过大时做平滑：
/** 防止单一世界垄断：把权重向均匀分布拉一点 */
void smooth(double eps) {
double n = weight.length;
for (int i = 0; i < weight.length; i++) {
weight[i] = weight[i] * (1 - eps) + eps / n;
}
}
eps = 0.02 的量级足够：它保留了”最强候选世界”的主导地位，又不至于让一次异常观测直接清零。这个技巧在信息过滤类问题（卡尔曼滤波、粒子滤波）里都有对应物——重采样前的权重平滑。
五、信息熵：该带谁去任务
推理的目的是决策。阿瓦隆里最有价值的决策是”提议什么队伍”。给定后验权重，队伍 T 的期望信息增益就是”执行这个任务后，我能排除多少不确定性”：
/** 队伍 T 通过 / 失败两种结果下的后验熵期望 */
double expectedEntropy(int[] team) {
double pPass = 0, pFail = 0;
// 结果概率 = 各世界下"队伍里有几个坏人"导致的失败概率之和
for (int i = 0; i < worlds.size(); i++) {
int evilInTeam = 0;
for (int p : team) if (worlds.get(i).isEvil(p)) evilInTeam++;
// 每个坏人独立有 0.5 概率投破坏票，故失败概率 = 1 - 0.5^{evilInTeam}
double pFailGiven = 1 - Math.pow(0.5, evilInTeam);
pFail += weight[i] * pFailGiven;
pPass += weight[i] * (1 - pFailGiven);
}
if (pPass <= 1e-9 || pFail <= 1e-9) return entropyOfCurrent(); // 无信息量
double total = pPass + pFail;
double hPass = shannon(pFail / total); // 失败后剩余熵
double hFail = shannon(pPass / total); // 通过后剩余熵
return (pPass * hPass + pFail * hFail) / total;
}
static double shannon(double p) {
if (p <= 0 || p >= 1) return 0;
return -(p * Math.log(p) + (1 - p) * Math.log(1 - p)) / Math.log(2);
}
1 - 0.5^{evilInTeam} 是标准阿瓦隆的失败概率公式（每个坏人独立决定是否投破坏票），只是这里我们对”谁是坏人”不确定，所以要对世界求和。
选择队伍时用”当前熵 − 期望后验熵“作为信息增益，再叠加通过概率的加权（因为你既要信息，也要赢）：
int[] bestTeam(List<int[]> candidates, double alpha) {
double bestScore = -1e9; int[] best = null;
double h0 = entropyOfCurrent();
for (int[] t : candidates) {
double h1 = expectedEntropy(t);
double infoGain = h0 - h1;
double passProb = 1 - failProb(t);
double score = alpha * infoGain + (1 - alpha) * passProb;
if (score > bestScore) { bestScore = score; best = t; }
}
return best;
}
alpha 是”探索 vs 利用”的权衡系数。早期轮次（信息少、后果轻）应该偏探索，alpha ≈ 0.7；关键的第 4、5 轮应该偏利用，alpha ≈ 0.2。这个系数随轮次线性衰减，是最简单也最有效的调参方式。
六、复杂度与收敛性
- 世界数：原始 120，按坏人集合去重后 10 种（5 人中选 2 人 = 10）。再加上梅林/派西维尔的位置组合，实际有效世界数为 10 × 3 × 2 = 60（梅林必须是非坏人，派西维尔也必须是好人，剩余 3 名好人里指定 1 名忠臣）。
- 单次观测更新：O(W)，W ≤ 60，即 60 次乘加，纳秒级。
- 一次队伍评估：O(W × |T|)，|T| ≤ 3，即约 180 次运算。
- 全候选队伍枚举：5 人挑 3 人 = 10 种队伍（外加 2 人轮次），共不到 20 种，故决策总成本约 3600 次运算。
也就是说整个推理+决策每轮只需不到 1 万次浮点运算。真正的限制不是算力，而是似然参数是否校准。
收敛性上有一个值得注意的现象：观测增多时权重会向少数世界集中，但不会收敛到唯一解。原因是软约束模型里，某些身份分配组合在行为上完全等价（例如”坏人是 A、B”与”坏人是 B、A”，去重后是两个不同世界但对所有观测给出相同似然）。所以后验会收敛到一个等价类而不是单点。这是阿瓦隆的信息论本质：坏人互换角色在观测层面不可分辨，只有当刺客最终动手刺杀时才产生区分。
七、一个易被忽略的细节：第一轮的先验
第一轮没有任何观测，此时后验等于先验，所有世界等权。但如果直接按等权做决策，会导致”第一轮随机组队”——这在实际对局里是浪费。更好的做法是引入一个结构性先验：给包含”非相邻座位组合”的世界更高权重，因为在人类玩家的实际投票中，相邻座位玩家更倾向于互相赞成（社交偏差）。这个先验不是理论必然，但在有限样本上能显著改善首轮表现。
工程上要诚实地说清楚：这类先验是数据拟合的产物，换一群玩家就失效。所以我把它做成可配置项而不是硬编码，默认关闭：
static double structuralPrior(World w, boolean enable) {
if (!enable) return 1.0;
// 两名坏人座位不相邻 → 略高权重（社交偏差的弱先验）
int[] evils = evilPlayers(w);
int gap = Math.abs(evils[0] - evils[1]);
return (gap == 1 || gap == N - 1) ? 0.9 : 1.05;
}
八、小结
把阿瓦隆做成推理引擎，三个可复用的模式：
- 候选世界 + 软约束连乘：不完全信息博弈的通用框架，比逻辑演绎稳、比纯神经网络可解释。关键是参数要”偏离随机但不能饱和”。
- 增量约束更新：只重算受影响的世界，把 O(W × 观测数) 降为常数。这本质上就是 AC-3 的”只对邻居做修订”。
- 熵驱动的主动推理：用信息增益挑动作，把”我想赢”和”我想知道”显式地加权组合。这个模式同样适用于主动学习、实验设计、探测类游戏（扫雷的选格策略）。
最后强调一点：这套模型的上限由似然参数决定，而不由算法决定。把 pDeny = 0.75 改成 0.55，模型就几乎退化成随机猜测；改成 0.95，模型会被一次假动作彻底误导。在软约束推理里，参数的”中等偏强”往往优于”极端”。
