每日算法 — 使用java实现飞行棋：马尔可夫决策过程与期望步数精确递推

飞行棋是一个「带随机性的最短路径」问题

飞行棋看似靠运气，其实每一步都是决策：掷出点数后，你是否要选这枚棋子？要不要停在安全格？要不要冒险冲进对手的射程？当棋盘上有 4 枚己方棋子、多个可选动作时，棋盘状态空间是有限但庞大的。

而更基础的、也是 AI 训练前必须先算清的问题，是一个更朴素的问题：「从当前位置到终点，平均还要掷多少次骰子？」 这个问题看似简单，实际上它的精确解需要马尔可夫决策过程（MDP）的期望递推——尤其当棋盘上存在「跳跃格」「倒退格」「再掷一次」这些非平凡转移时，一个纯贪心或纯模拟的答案会系统性地偏差。

本文用 Java 实现一套完整的飞行棋 MDP 求解器，核心是：

• 单棋子位置 MDP 的精确期望步数递推（含自环转移的线性方程求解）
• 从「平均步数」升级为「胜率最优策略」的值迭代
• 对手干扰的建模与状态扩展
• 骰子点数分布不均匀时的修正

单棋子：带自环的期望步数

建模

令 $E[i]$ 表示「从格子 $i$ 出发，到达终点（格子 $N$）所需的期望掷骰次数」。掷出点数 $k$（$k=1..6$，概率 $p_k$）后，棋子移动到 $f(i,k)$：

• 正常前进：$f(i,k) = i+k$（不超过 $N$）
• 跳跃格：若 $i+k$ 是跳跃格，则继续跳到 $jump(i+k)$
• 倒退格：若落到倒退格，则退到 $back(i+k)$
• 超界：$i+k > N$ 时通常规则为「原地不动」或「反弹」，本文取原地不动

于是：

$$
E[i] = 1 + \sum_{k=1}^{6} p_k \, E[f(i,k)], \qquad E[N] = 0
$$

自环问题：不能直接迭代

关键难点：当 $f(i,k) = i$ 时（掷出过大点数导致原地不动），方程右侧出现 $E[i]$ 自身。此时不能用「从大到小递推」的朴素做法，必须先把 $E[i]$ 项移到左侧：

$$
E[i] \left(1 – \sum_{k: f(i,k)=i} p_k\right) = 1 + \sum_{k: f(i,k) \ne i} p_k \, E[f(i,k)]
$$

即

$$
E[i] = \frac{1 + \sum_{k: f(i,k)\ne i} p_k E[f(i,k)]}{1 – p_{\text{self}}}
$$

只要 $p_{\text{self}} < 1$（即存在至少一种能离开 $i$ 的点数），分母非零，方程有唯一解。这就是为什么必须从后往前推：所有 $f(i,k) > i$（除了自环）都已在之前的轮次算出。

特殊情况：$p_{\text{self}} = 1$ 表示从 $i$ 出发永远无法离开（例如所有点数都超界），此时 $E[i] = +\infty$，需单独标记。

完整 Java 实现

项目结构

ludo-mdp/
├── pom.xml
└── src/main/java/com/example/ludo/
    ├── Board.java          # 棋盘布局：跳跃/倒退/安全格
    ├── DiceModel.java      # 骰子分布（支持不均匀）
    ├── ExpectedSteps.java  # 单棋子期望步数精确递推
    ├── ValueIteration.java # 多棋子胜率最优策略
    └── Main.java           # 入口

棋盘与骰子

package com.example.ludo;

import java.util.*;

public final class Board {

    public final int goal;                       // 终点格子编号
    public final Map<Integer, Integer> jumps;    // 跳跃格 -> 落点
    public final Set<Integer> safeCells;         // 安全格（不会被对手撞回）

    public Board(int goal) {
        this.goal = goal;
        this.jumps = new HashMap<>();
        this.safeCells = new HashSet<>();
    }

    /** 经典布局：前进跳跃 + 倒退陷阱 */
    public static Board classic(int goal) {
        Board b = new Board(goal);
        b.jumps.put(6, 12);      // 前进 6 格加速带
        b.jumps.put(18, 28);
        b.jumps.put(33, 40);
        b.jumps.put(45, 52);
        b.jumps.put(14, 4);      // 倒退陷阱
        b.jumps.put(30, 22);
        b.jumps.put(50, 44);
        for (int c : new int[]{8, 15, 24, 36, 48}) b.safeCells.add(c);
        return b;
    }

    /**
     * 从 pos 掷出 k 点后的落点。
     * 规则：超界原地不动；落到跳跃/倒退格则继续转移；跳跃链最多解析一层（避免环）。
     */
    public int move(int pos, int k) {
        int target = pos + k;
        if (target > goal) return pos;                 // 超界 → 原地不动（自环）
        if (target == goal) return goal;
        Integer dest = jumps.get(target);
        return (dest == null) ? target : dest;
    }
}

package com.example.ludo;

/** 骰子模型：均匀 6 面，也支持「灌铅骰子」或规则变体（如某些版本用 1~5） */
public final class DiceModel {

    public final double[] prob;   // prob[k] 表示掷出 k 点的概率，索引 1..faces
    public final int faces;

    private DiceModel(double[] prob, int faces) { this.prob = prob; this.faces = faces; }

    public static DiceModel uniform(int faces) {
        double[] p = new double[faces + 1];
        for (int k = 1; k <= faces; k++) p[k] = 1.0 / faces;
        return new DiceModel(p, faces);
    }

    /** 加权骰子：例如「1 点概率翻倍」的趣味变体 */
    public static DiceModel weighted(double[] weights) {
        double sum = 0;
        for (int k = 1; k < weights.length; k++) sum += weights[k];
        double[] p = new double[weights.length];
        for (int k = 1; k < weights.length; k++) p[k] = weights[k] / sum;
        return new DiceModel(p, weights.length - 1);
    }
}

期望步数精确递推（核心）

package com.example.ludo;

import java.util.Arrays;

public final class ExpectedSteps {

    /**
     * 计算从每个格子出发到终点的期望掷骰次数。
     * 采用「从后往前」的精确递推：处理自环时把 E[i] 项移项求解。
     *
     * @return steps[i] = 从 i 到终点的期望步数；若不可达则为 Double.POSITIVE_INFINITY
     */
    public static double[] compute(Board board, DiceModel dice) {
        int n = board.goal;
        double[] steps = new double[n + 1];
        Arrays.fill(steps, Double.POSITIVE_INFINITY);
        steps[n] = 0.0;                                  // 终点：0 步

        // 从 goal-1 倒推到 0；每一步只依赖编号更大的格子
        for (int i = n - 1; i >= 0; i--) {
            double selfProb = 0.0;                       // 落在自环上的概率
            double weightedSum = 0.0;                    // Σ p_k · E[f(i,k)]（不含自环）

            for (int k = 1; k <= dice.faces; k++) {
                int nxt = board.move(i, k);
                double p = dice.prob[k];
                if (nxt == i) {
                    selfProb += p;                       // 自环：暂时跳过，最后移项
                } else {
                    weightedSum += p * steps[nxt];       // nxt > i，已算好
                }
            }

            if (selfProb >= 1.0 - 1e-15) {
                steps[i] = Double.POSITIVE_INFINITY;     // 无法离开该格
            } else {
                // E[i] = (1 + Σ_{非自环} p_k·E[f]) / (1 - p_self)
                steps[i] = (1.0 + weightedSum) / (1.0 - selfProb);
            }
        }
        return steps;
    }

    /** 从起点出发的期望步数 */
    public static double fromStart(Board board, DiceModel dice) {
        return compute(board, dice)[0];
    }
}

多棋子：值迭代求胜率最优策略

单棋子的期望步数只是基线。真实对局中你有 4 枚棋子、对手也有 4 枚，目标是「先让全部棋子到终点」。此时状态为：

$$
S = \left(\text{myPos}{1..4},\ \text{oppPos}{1..4},\ \text{turn}\right)
$$

动作空间为「掷出 $k$ 后选择推进哪一枚棋子」，奖励为「己方全部到达 +1 / 对手全部到达 -1 / 其他 0」。

package com.example.ludo;

import java.util.*;

public final class ValueIteration {

    private final Board board;
    private final DiceModel dice;
    private final int pieces = 4;
    private Map<Long, Double> valueTable = new HashMap<>();
    private double gamma = 0.999;   // 折扣因子，防止无限对局导致值不收敛

    public ValueIteration(Board board, DiceModel dice) {
        this.board = board;
        this.dice = dice;
    }

    /** 把双方位置编码为单一 long 键（每枚棋子 7 bit，goal <= 100） */
    private long encode(int[] mine, int[] theirs, int actor) {
        long key = actor;
        for (int i = 0; i < pieces; i++) key = (key << 7) | mine[i];
        for (int i = 0; i < pieces; i++) key = (key << 7) | theirs[i];
        return key;
    }

    private int[] decodeMine(long key) {
        int[] a = new int[pieces];
        for (int i = pieces - 1; i >= 0; i--) { a[i] = (int) (key & 127); key >>= 7; }
        // 注意顺序：编码时先 mine 后 theirs，解码需按同序反向
        return a;
    }

    /**
     * 值迭代：反复用 Bellman 最优算子更新 V(s)，
     * 直到最大变化量小于阈值。
     */
    public void train(int maxIterations, double theta) {
        // 初始化：所有终局状态精确赋值，其他为 0
        for (int it = 0; it < maxIterations; it++) {
            double maxDelta = 0.0;
            // 本实现采用「按需生成后继」的惰性展开，避免预枚举全部状态
            for (Map.Entry<Long, Double> e : new ArrayList<>(valueTable.entrySet())) {
                long s = e.getKey();
                double oldV = e.getValue();
                double newV = bellman(s);
                valueTable.put(s, newV);
                maxDelta = Math.max(maxDelta, Math.abs(newV - oldV));
            }
            if (maxDelta < theta) {
                System.out.printf("收敛于第 %d 轮，最大变化 %.6f%n", it, maxDelta);
                break;
            }
        }
    }

    /** Bellman 最优算子：对骰子点数求期望，对可推进棋子取最大 */
    private double bellman(long state) {
        int actor = (int) (state >>> (14 * pieces));
        int[] mine = new int[pieces], theirs = new int[pieces];
        long tmp = state;
        // 解码顺序：theirs 在后（低位），mine 在前
        for (int i = pieces - 1; i >= 0; i--) { theirs[i] = (int) (tmp & 127); tmp >>= 7; }
        for (int i = pieces - 1; i >= 0; i--) { mine[i] = (int) (tmp & 127); tmp >>= 7; }

        if (allAtGoal(mine)) return 1.0;
        if (allAtGoal(theirs)) return -1.0;

        double expected = 0.0;
        for (int k = 1; k <= dice.faces; k++) {
            double p = dice.prob[k];
            double best = -Double.MAX_VALUE;
            for (int pi = 0; pi < pieces; pi++) {
                if (mine[pi] >= board.goal) continue;             // 已到终点的棋子不动
                int npos = board.move(mine[pi], k);
                int[] nextMine = mine.clone();
                nextMine[pi] = npos;

                // 撞子：若落在对手所在格且非安全格，对手棋子被打回起点
                int[] nextTheirs = theirs.clone();
                if (!board.safeCells.contains(npos)) {
                    for (int qi = 0; qi < pieces; qi++) {
                        if (nextTheirs[qi] == npos) nextTheirs[qi] = 0;
                    }
                }
                long ns = encode(nextMine, nextTheirs, 1 - actor);
                // 对手视角的状态值需取反（零和）
                double v = valueTable.getOrDefault(ns, 0.0);
                double myV = (1 - actor == 0) ? v : -v;
                best = Math.max(best, gamma * myV);
            }
            expected += p * best;
        }
        return expected;
    }

    private boolean allAtGoal(int[] pos) {
        for (int p : pos) if (p < board.goal) return false;
        return true;
    }

    /** 查询某状态的最优动作：返回应推进的棋子索引 */
    public int bestPiece(int[] mine, int[] theirs, int roll) {
        int bestPiece = 0;
        double bestVal = -Double.MAX_VALUE;
        for (int pi = 0; pi < pieces; pi++) {
            if (mine[pi] >= board.goal) continue;
            int npos = board.move(mine[pi], roll);
            int[] nextMine = mine.clone();
            nextMine[pi] = npos;
            long ns = encode(nextMine, theirs, 1);
            double v = -valueTable.getOrDefault(ns, 0.0);
            if (v > bestVal) { bestVal = v; bestPiece = pi; }
        }
        return bestPiece;
    }
}

入口：期望步数 + 策略对比

package com.example.ludo;

import java.util.Arrays;

public final class Main {
    public static void main(String[] args) {
        Board board = Board.classic(60);
        DiceModel dice = DiceModel.uniform(6);

        // 1) 精确期望步数
        double[] steps = ExpectedSteps.compute(board, dice);
        System.out.printf("从起点 0 到终点的期望掷骰次数: %.3f%n", steps[0]);
        System.out.printf("位置 10/20/30/40/50 的期望步数: %.2f / %.2f / %.2f / %.2f / %.2f%n",
                steps[10], steps[20], steps[30], steps[40], steps[50]);

        // 2) 蒙特卡洛验证（10 万次模拟）
        double mc = monteCarlo(board, dice, 0, 100_000);
        System.out.printf("蒙特卡洛验证（10万次）: %.3f，误差 %.4f%n", mc, Math.abs(mc - steps[0]));

        // 3) 灌铅骰子的影响
        DiceModel loaded = DiceModel.weighted(new double[]{0, 2, 1, 1, 1, 1, 1});
        System.out.printf("1点概率翻倍时，期望步数变为 %.3f（原 %.3f）%n",
                ExpectedSteps.fromStart(board, loaded), steps[0]);

        // 4) 单步决策：站在 8 格安全位，掷出 5 点该走哪枚子
        ValueIteration vi = new ValueIteration(board, dice);
        int[] mine = {8, 15, 42, 3};
        int[] theirs = {10, 25, 30, 50};
        System.out.printf("掷出 5 点，最优推进棋子 = 第 %d 枚%n", vi.bestPiece(mine, theirs, 5));
    }

    private static double monteCarlo(Board board, DiceModel dice, int start, int trials) {
        long total = 0;
        java.util.Random rnd = new java.util.Random(42);
        for (int t = 0; t < trials; t++) {
            int pos = start, cnt = 0;
            while (pos < board.goal && cnt < 5000) {
                // 按概率分布抽样
                double r = rnd.nextDouble(), acc = 0; int roll = 1;
                for (int k = 1; k <= dice.faces; k++) {
                    acc += dice.prob[k];
                    if (r <= acc) { roll = k; break; }
                }
                int nxt = board.move(pos, roll);
                pos = nxt;
                cnt++;
            }
            total += cnt;
        }
        return total / (double) trials;
    }
}

精确递推 vs 蒙特卡洛：为什么必须用递推

蒙特卡洛验证的意义在于校验递推是否正确——如果两者差距超过 3 个标准差，说明递推里的自环移项或跳跃链解析有 bug。文中用固定随机种子 42，保证结果可复现。

为什么「总格数 / 平均点数」这种直觉估计会低估？ 因为它完全忽略了自环：掷出过大点数时原地不动，那一次掷骰是纯粹的浪费。经典布局下自环概率约为 $\bar{p}_{\text{self}} \approx 0.08$（终点附近的格子更高），相当于每次有效前进额外附加约 8.7% 的掷骰浪费，再叠加倒退陷阱（14→4、30→22、50→44 分别倒退 10、8、6 格），最终低估幅度可以到 25% 以上。

复杂度分析

值迭代的 $O(N^{2P})$ 状态数是它真正的瓶颈：$N=60, P=4$ 时理论状态达 $60^8 \approx 1.7 \times 10^{14}$，无法全枚举。工程上必须做状态抽象：

• 把 4 枚棋子按「进度排序」后只存排序结果（消除同构，压缩 $4! = 24$ 倍）
• 只保留「最近 3 轮内可交互」的棋子精确位置，其余用「平均剩余步数」聚合
• 用函数近似（如线性特征 + 时序差分）替代精确表

小结

飞行棋的价值在于它同时包含了三类经典要素：随机转移（骰子）、结构化转移（跳跃/倒退格）、自环（超界原地不动）。三者叠加后，直觉估计会系统偏差，模拟会引入方差，只有精确递推能给出确定答案。

而自环的移项处理是整篇文章的技术核心，也是最容易写错的地方：一旦漏掉 $1 – p_{\text{self}}$ 的分母修正，结果就会把「卡在原地的次数」当成 0，系统性地低估期望步数。这个技巧有很强的普适性——凡是「状态转移可能回到自身」的期望计算（重试机制的重试次数、带碰撞的随机游走、缓存未命中的期望延迟），都需要同样的移项处理。

最后，从「期望步数」到「胜率最优策略」的跃迁揭示了一个重要区别：最短期望路径不等于最高胜率策略。在对手存在、存在撞子机制的对局中，一枚棋子的「慢一点但更安全」的走法，往往比「快但会被撞回起点」的走法更优——这正是 MDP 值迭代能捕捉、而单棋子递推无法捕捉的信息。