每日算法 — 使用java实现大话骰：贝叶斯概率更新与期望叫价决策

大话骰（Liar’s Dice，酒吧里也叫”骰盅”）是一款典型的不完全信息博弈：每人一个骰盅扣住 5 枚骰子，轮流叫”全场至少有多少个某点数”，可以质疑上家。你只能看见自己的骰子，其余全靠概率推断和对手行为建模。

这款游戏的算法内核非常干净：一是在”已知自己骰子”的条件下计算全场点数的二项分布，二是根据对手的叫价序列做贝叶斯后验更新，三是用期望收益最大化决定”该叫多少”还是”该开”。

本文用 Java 实现一个可运行的大话骰 AI，包含概率计算、贝叶斯更新、叫价决策三层，并做完整复杂度分析。

一、规则与建模要点

标准规则（以 5 骰 1 点万能为例）：

• 每人 5 枚六面骰，摇完后只看自己的；
• 叫价形式为 (数量, 点数)，例如”4 个 5″，表示”全场至少有 4 枚骰子点数为 5″；
• 后叫者必须加价：要么提高数量，要么数量不变但点数提高；
• 1 点（幺）是万能点，可代替任意点数，但一旦有人叫过 1 点，万能规则关闭；
• 任何玩家可以”开”（质疑），若实际数量达到叫价则质疑者输，否则叫价者输。

把状态抽象出来只有几个变量：自己的骰子向量、当前叫价、总人数、是否已叫过幺。这是一个状态极小、但信息不完全的博弈，非常适合用概率方法处理。

二、概率核心：给定自己骰子后的后验分布

设总人数 P，每人 5 枚骰，则全场共 N = 5P 枚。你自己有 k 枚是点数 f，那么剩余 M = N - 5 枚未知骰子中，点数 f 的个数 X ~ Binomial(M, 1/6)。

于是”全场至少 b 个 f“的概率为：

P(总数 ≥ b) = P(X ≥ b - k) = Σ_{x=b-k}^{M} C(M,x) (1/6)^x (5/6)^(M-x)

/** 大话骰概率核心：给定自己骰子后的二项分布计算 */
public class DiceProbability {
    private static final double P_HIT = 1.0 / 6.0;   // 单个骰子命中指定点数的概率
    private static final double P_MISS = 5.0 / 6.0;

    /** 预计算组合数，避免重复计算阶乘溢出 */
    private final double[][] binom;

    public DiceProbability(int maxN) {
        binom = new double[maxN + 1][maxN + 1];
        for (int i = 0; i <= maxN; i++) {
            binom[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                binom[i][j] = binom[i - 1][j - 1] + (j <= i - 1 ? binom[i - 1][j] : 0);
            }
        }
    }

    /**
     * 计算「全场点数 f 的总数 ≥ need」的概率。
     * @param totalDice  全场骰子总数 N
     * @param myCount    自己手上点数 f 的个数 k
     * @param need       叫价要求的数量 b
     */
    public double atLeast(int totalDice, int myCount, int need) {
        int unknown = totalDice - 5;          // 别人的骰子总数 M
        int required = need - myCount;        // 还需要在别人手里凑出多少个
        if (required <= 0) return 1.0;        // 自己已经够了
        if (required > unknown) return 0.0;   // 别人全中也不够

        double prob = 0.0;
        for (int x = required; x <= unknown; x++) {
            prob += binom[unknown][x]
                  * Math.pow(P_HIT, x)
                  * Math.pow(P_MISS, unknown - x);
        }
        return Math.min(1.0, prob);
    }

    /** 计算「全场点数 f 的总数恰好等于 need」的概率 */
    public double exactly(int totalDice, int myCount, int need) {
        int unknown = totalDice - 5;
        int required = need - myCount;
        if (required < 0 || required > unknown) return 0.0;
        return binom[unknown][required]
             * Math.pow(P_HIT, required)
             * Math.pow(P_MISS, unknown - required);
    }
}

为什么用二项分布而不是正态近似

当 M = 15（4 人局）时，二项分布相当”扁”，尾部概率不可忽略。用正态近似去算 P(总数 ≥ 6)，精确值 0.0274、近似值 0.0188，绝对误差不到 1 个百分点，但相对误差超过 30%；算 P(总数 ≥ 7) 时精确 0.0066、近似 0.0028，相对误差翻倍。这类”尾部概率算歪一倍”的误差会直接让 AI 做出错误的”开”决策。而 M 只有 15，直接累加公式反而更快更准——这是“能精确就别近似”的典型场景。

三、贝叶斯更新：从对手叫价中榨取信息

对手的叫价本身携带信息。一个理性玩家叫”4 个 5″，说明他手上极可能真的有 5（否则凭什么敢叫这个价）。我们可以用贝叶斯公式反推他的骰子分布。

设对手手上有 Y 个点数 f，先验 Y ~ Binomial(5, 1/6)。观察到”他叫了 (b, f)“这一事件 E，则：

P(Y = y | E) ∝ P(E | Y = y) · P(Y = y)

关键在于建模似然 P(E | Y = y)：手上 y 个 f 的玩家，叫出 (b, f) 的倾向性。这里用一个单调递增的软性似然：手里越多，越可能叫高价。

/** 贝叶斯推理器：从对手叫价反推其手牌分布 */
public class BayesianBidder {
    private final int totalDice;
    /** rel 为叫价可靠度：越大表示对手越倾向"有牌才叫"，越小表示越爱虚张声势 */
    private final double rel;
    /** C(5, y) 的二项系数，5 枚骰子的先验只需要这一组常数 */
    private static final double[] BINOM5 = {1, 5, 10, 10, 5, 1};

    public BayesianBidder(int totalDice, double rel) {
        this.totalDice = totalDice;
        this.rel = rel;
    }

    /** 精确先验：5 骰中恰好 y 个指定点数 */
    private static double priorExactly(int y) {
        return BINOM5[y] * Math.pow(1.0 / 6.0, y) * Math.pow(5.0 / 6.0, 5 - y);
    }

    /**
     * 计算观察到叫价 (bidCount, face) 之后，
     * 对手手上点数 face 的个数的后验分布。
     * @return 长度为 6 的数组，post[y] = P(对手有 y 个 face | 观察到该叫价)
     */
    public double[] posterior(int bidCount, int face) {
        double[] post = new double[6];
        double norm = 0.0;

        for (int y = 0; y <= 5; y++) {
            double prior = priorExactly(y);
            double likelihood = likelihoodOf(y, bidCount);
            post[y] = prior * likelihood;
            norm += post[y];
        }
        if (norm > 0) {
            for (int y = 0; y <= 5; y++) post[y] /= norm;   // 归一化
        }
        return post;
    }

    /**
     * 似然模型：手中有 y 个 face 的玩家叫出 bidCount 的相对倾向。
     * 采用 logistic 形状：手牌越接近叫价，越可能这样叫。
     */
    private double likelihoodOf(int y, int bidCount) {
        // 期望：自己 y 个 + 别人平均产出
        double expectedOthers = (totalDice - 5) / 6.0;
        double confidence = (y + expectedOthers) / bidCount;
        // logistic：confidence 越接近 1 或以上，倾向越强
        return 1.0 / (1.0 + Math.exp(-rel * (confidence - 1.0) * 4));
    }

    /** 用后验修正「全场至少 b 个 face」的概率 */
    public double correctedAtLeast(int myCount, int bidCount, int face) {
        double[] post = posterior(bidCount, face);
        double total = 0.0;
        for (int y = 0; y <= 5; y++) {
            // 对手手上 y 个，剩余 (totalDice - 10) 枚骰子按均匀分布补齐
            int rest = totalDice - 10;
            int stillNeed = bidCount - myCount - y;
            double p = (stillNeed <= 0) ? 1.0 : atLeastBinomial(rest, stillNeed);
            total += post[y] * p;
        }
        return total;
    }

    /** 二项分布尾部：rest 枚骰子中至少 need 个命中的概率 */
    private static double atLeastBinomial(int rest, int need) {
        double sum = 0.0, c = 1.0;
        for (int x = need; x <= rest; x++) {
            sum += c * Math.pow(1.0 / 6.0, x) * Math.pow(5.0 / 6.0, rest - x);
            c = c * (rest - x) / (x + 1);     // 递推更新组合数 C(rest, x)
        }
        return Math.min(1.0, sum);
    }
}

这段实现的关键在于把”先验—似然—归一化”三步拆开，并且用递推更新组合数（c = c * (rest - x) / (x + 1)）而不是算阶乘，避免 20! 早就溢出 long 的问题。这是二项分布实现里最容易被忽略的工程细节。

贝叶斯更新的实际作用

举一个数值示例（4 人局，全场 20 枚骰子），对手叫”5 个 5″，你自己手上有 k 个 5。纯频率估计与两种风格的贝叶斯修正结果如下（rel 为叫价可靠度，越大表示对手越倾向”有牌才叫”）：

读表时注意三件事：

1. 修正方向永远是抬高。因为”观察到有人这么叫”本身就是一个证据，它提升了”真的存在 5 个 5″的可能性。这是贝叶斯更新最容易被误解的地方——它不是”打折”，而是在先验上加信息。
2. 风格只影响抬高的幅度。rel=2.0 的对手，后验均值被推到约 E[y] ≈ 1.83（他手上平均有 1.83 个 5），所以 k=2 时概率直接从 0.4678 蹿到 0.7421；而 rel=0.5 的爱吹牛对手，后验均值只有 E[y] ≈ 1.02，概率只从 0.4678 微调到 0.5201。
3. 决策边界会被推翻。k=1 这个格子最关键：纯频率下 P = 0.2315 < 0.5，evOpen = 1 - 2p = 0.537 > 0，应该开；但面对”有牌才叫”的对手，修正后 P = 0.4785，evOpen = 0.043，几乎归零，实战中就该放弃质疑、转而加价。同一手牌、同一个叫价，最优动作因为对手风格而反转。

四、决策层：期望收益最大化

大话骰的决策空间只有两类动作：叫价 与 开（质疑）。用期望收益来统一比较：

• 若选择”开”，赢的概率就是 1 - P(全场 ≥ b)，收益 +1；输的概率 P(全场 ≥ b)，收益 -1。
• 若选择叫 (b', f')，需要估计”下一个玩家会开我的概率” q，则期望为 (1-q)·V_继续 + q·(2·P(全场 ≥ b') - 1)。

/** 决策器：在「开」与「叫」之间做期望最大化选择 */
public class BidDecision {
    private final DiceProbability prob;
    private final int totalDice;
    private final BayesianBidder bayes;
    private final int myDiceCount = 5;

    public BidDecision(DiceProbability prob, int totalDice, BayesianBidder bayes) {
        this.prob = prob;
        this.totalDice = totalDice;
        this.bayes = bayes;
    }

    /**
     * 对当前叫价做出决策。
     * @param myDice   自己的 5 枚骰子点数
     * @param bidCount 当前叫价的数量
     * @param bidFace  当前叫价的点数
     * @return 决策描述，例如 "OPEN" 或 "BID 5 6"
     */
    public String decide(int[] myDice, int bidCount, int bidFace) {
        int mine = count(myDice, bidFace, false);
        double pTrue = prob.atLeast(totalDice, mine, bidCount);

        // 方案 A：开牌，期望收益 1 - 2p
        double evOpen = 1.0 - 2.0 * pTrue;

        // 方案 B：加价到最小合法叫价，比较期望
        double bestEv = evOpen;
        String bestAction = "OPEN";

        for (int face = 1; face <= 6; face++) {
            for (int cnt = bidCount; cnt <= totalDice; cnt++) {
                if (cnt == bidCount && face <= bidFace) continue; // 必须加价
                if (cnt > bidCount && face < bidFace) continue;   // 数量加时点数不可降
                if (cnt > bidCount + 2) break;                    // 只考虑小幅加价，避免自杀式叫价

                int own = count(myDice, face, false);
                double p = prob.atLeast(totalDice, own, cnt);
                // 加价被开的概率：p 越低，对手越可能开我
                double qOpen = 1.0 - p;
                // 若没被开，粗略用「保持局面」的中性收益 0.1 近似
                double ev = qOpen * (2.0 * p - 1.0) + (1.0 - qOpen) * 0.1;

                if (ev > bestEv) {
                    bestEv = ev;
                    bestAction = "BID " + cnt + " " + face;
                }
            }
        }
        return bestAction;
    }

    private static int count(int[] dice, int face, boolean wildAsOne) {
        int c = 0;
        for (int d : dice) {
            if (d == face) c++;
            else if (wildAsOne && d == 1 && face != 1) c++;
        }
        return c;
    }
}

决策边界的解析形式

把 evOpen 与”加价期望”相等的位置解出来，可以得到一条简洁的决策边界。忽略后续博弈项，仅比较 evOpen = 1 - 2p 与加价方案被开时的 2p' - 1：

• p > 0.5 时 evOpen < 0，说明这个叫价大概率是真的，不该开，应加价；
• p < 0.5 时 evOpen > 0，开牌是正期望；
• 临界点就在 p = 0.5，即”叫价恰好一半概率为真”。

这就是大话骰的核心直觉的数学表达：永远只在”叫价期望为假”时开牌。而贝叶斯更新的作用，是把 p 从”纯频率估计”修正为”考虑对手风格后的估计”。

五、万能与幺点：规则细节的位运算处理

1 点万能规则会让计数变复杂。用位掩码把”已叫过幺”这个开关，以及”哪些点数已被叫过”打包，可以一次判断合法性：

/** 叫价合法性判定：用位掩码编码历史叫价 */
public class BidValidator {
    /** bit i 表示点数 i 已经被叫过（i=1..6） */
    private int calledMask = 0;
    /** 是否已进入「幺点被叫」阶段，万能规则关闭 */
    private boolean aceCalled = false;

    public boolean isValid(int newCount, int newFace, int oldCount, int oldFace) {
        if (newCount < oldCount) return false;
        if (newCount == oldCount && newFace <= oldFace) return false;
        // 叫 1 点时数量要求减半（常见房规）
        if (newFace == 1 && !aceCalled && oldFace != 1) {
            return newCount >= Math.max(1, oldCount / 2);
        }
        return true;
    }

    public void commit(int cnt, int face) {
        calledMask |= (1 << face);
        if (face == 1) aceCalled = true;
    }
}

用 calledMask 的好处是：判断”全场 6 个点数是否都被叫过”只需 Integer.bitCount(calledMask) == 6，为后续的策略统计（比如”某个点数已被反复叫价，说明大家在抢”）提供 O(1) 的查询。

六、完整工程结构与运行

liars-dice-ai/
├── src/main/java/com/example/dice/
│   ├── DiceProbability.java     二项分布概率核心
│   ├── BayesianBidder.java      贝叶斯后验更新
│   ├── BidDecision.java         期望最大化决策
│   ├── BidValidator.java        叫价合法性（位掩码）
│   └── Main.java                蒙特卡洛对比 20000 局
└── pom.xml

Main 里做一次蒙特卡洛对比，验证”带贝叶斯的 AI”是否真的比”纯频率 AI”更强：

public class Main {
    private static final int PLAYERS = 4;
    private static final int TOTAL_DICE = PLAYERS * 5;   // 20

    public static void main(String[] args) {
        DiceProbability prob = new DiceProbability(TOTAL_DICE);
        // 保守型对手（有牌才叫，可靠度高）与激进型对手（爱虚张声势，可靠度低）
        BayesianBidder conservative = new BayesianBidder(TOTAL_DICE, 2.0);
        BayesianBidder aggressive   = new BayesianBidder(TOTAL_DICE, 0.5);

        Random rnd = new Random(42);
        int winsRaw = 0, winsBayes = 0, rounds = 20000;

        for (int i = 0; i < rounds; i++) {
            int[] myDice = roll(rnd);
            // 场景：上家叫「5 个 4」，我们手里有 mineCount 个 4
            int mineCount = countOf(myDice, 4);
            int bidCount = 5;

            // 纯频率决策：p < 0.5 就开
            if (prob.atLeast(TOTAL_DICE, mineCount, bidCount) < 0.5) winsRaw++;

            // 贝叶斯决策：用修正后的概率
            boolean aggressor = rnd.nextBoolean();
            BayesianBidder model = aggressor ? aggressive : conservative;
            double p = model.correctedAtLeast(mineCount, bidCount, 4);
            if (p < 0.5) winsBayes++;
        }
        System.out.printf("纯频率 AI 开牌率 = %.2f%%%n", winsRaw * 100.0 / rounds);
        System.out.printf("贝叶斯 AI 开牌率 = %.2f%%%n", winsBayes * 100.0 / rounds);
    }

    private static int[] roll(Random r) {
        int[] d = new int[5];
        for (int i = 0; i < 5; i++) d[i] = 1 + r.nextInt(6);
        return d;
    }

    private static int countOf(int[] dice, int face) {
        int c = 0;
        for (int d : dice) if (d == face) c++;
        return c;
    }
}

跑出来会看到一个有意思的现象：纯频率 AI 的开牌率约 96.5%，而两个贝叶斯 AI 都降到约 80%——因为修正后的概率普遍被抬高，p < 0.5 的情形变少了。同时留意那个 mineCount == 1 的分档：纯频率给出 0.2315 的”果断开”，面对高可靠度对手却被修正到 0.4785 的”临界不敢开”。概率方向一致，但决策信心完全不同——这正是贝叶斯方法在实战中的价值：它不改变结论的方向，改变的是你敢不敢下注。

七、复杂度分析

值得注意的是：这个算法的时间复杂度几乎为零，真正的成本全部在”信息质量”上——贝叶斯似然函数的形状（rel 可靠度参数）是否准确，比任何性能优化都重要。

八、小结与延伸

大话骰把三个经典算法串成一条链：

1. 二项分布给出”给定自己手牌时，全场状况的概率”——这是所有不完全信息博弈的起点；
2. 贝叶斯更新把对手的行为变成信息，用一个可调的风格参数（激进/保守）来修正先验；
3. 期望最大化把概率转成动作：当且仅当 p < 0.5 时开牌是正期望。

这套”概率—更新—决策”的三段式结构，可以平移到德州扑克、拍卖竞价、广告出价等一切信息不对称场景。下一篇文章我们换一个完全不同的方向：从概率博弈回到纯逻辑推理，用约束传播来解 Hitori（数壹）谜题。