每日算法 — 使用java实现飞行棋：概率模型与期望步数分析

游戏背景与问题建模

飞行棋是一款经典棋盘游戏，玩家掷骰子前进，遇到梯子可向上攀升，遇到蛇则滑落回低处。首个到达终点的玩家获胜。游戏表面依赖运气，但深层蕴含着丰富的概率论与期望值计算。

本文用Java实现飞行棋的概率模型，重点分析：掷骰子的概率分布、到达各格子的期望步数、以及最优策略决策。

核心算法设计

1. 马尔可夫链状态建模

将棋盘每个格子视为一个状态，掷骰子作为状态转移。设棋盘有 $N$ 个格子，骰子面数为 $M$：

• 状态空间：$S = {0, 1, 2, …, N}$，0 为起点，N 为终点
• 从状态 $i$ 转移到 $i+k$ 的概率为 $\frac{1}{M}$（$1 \le k \le M$，且 $i+k \le N$）
• 若 $i+k$ 位置有梯子到 $j$，则实际到达 $j$；若有蛇到 $j$，则滑落到 $j$

2. 期望步数计算

设 $E[i]$ 为从格子 $i$ 到达终点的期望步数，则有递推方程：

$$E[i] = 1 + \frac{1}{M} \sum_{k=1}^{M} E[next(i+k)]$$

其中 $next(x)$ 表示经过梯子/蛇调整后的实际到达位置。边界条件 $E[N] = 0$。

3. 获胜概率模拟

对于多玩家游戏，通过蒙特卡洛模拟估算先手优势与各位置的获胜概率。

Java实现

package flightchess;

import java.util.*;

/**
 * 飞行棋概率模型与期望步数分析系统
 * 核心算法：马尔可夫链 + 动态规划期望值计算 + 蒙特卡洛模拟
 */
public class FlightChessAnalyzer {

    private final int boardSize;       // 棋盘格子数
    private final int diceFaces;       // 骰子面数
    private final Map<Integer, Integer> snakes;  // 蛇：起点 -> 终点
    private final Map<Integer, Integer> ladders; // 梯子：起点 -> 终点

    // 缓存期望步数
    private double[] expectedSteps;
    private boolean expectedComputed = false;

    public FlightChessAnalyzer(int boardSize, int diceFaces) {
        this.boardSize = boardSize;
        this.diceFaces = diceFaces;
        this.snakes = new HashMap<>();
        this.ladders = new HashMap<>();
    }

    /**
     * 添加蛇：从高处滑落到低处
     */
    public void addSnake(int head, int tail) {
        if (head > tail) snakes.put(head, tail);
    }

    /**
     * 添加梯子：从低处攀爬到高处
     */
    public void addLadder(int bottom, int top) {
        if (top > bottom) ladders.put(bottom, top);
    }

    /**
     * 计算经过蛇或梯子后的实际位置
     */
    private int getActualPosition(int pos) {
        if (pos > boardSize) return boardSize;  // 超过终点则停在终点
        if (snakes.containsKey(pos)) return snakes.get(pos);
        if (ladders.containsKey(pos)) return ladders.get(pos);
        return pos;
    }

    /**
     * 动态规划计算从每个格子到达终点的期望步数
     * E[i] = 1 + (1/M) * sum(E[next(i+k)]) for k in 1..M
     * 使用高斯-赛德尔迭代法求解方程组
     */
    public double[] computeExpectedSteps() {
        expectedSteps = new double[boardSize + 1];
        expectedSteps[boardSize] = 0;  // 终点期望为0

        // 迭代求解，直到收敛
        double epsilon = 1e-9;
        int maxIterations = 100000;

        for (int iter = 0; iter < maxIterations; iter++) {
            double maxDiff = 0;

            // 倒序更新（从终点向起点）
            for (int i = boardSize - 1; i >= 0; i--) {
                double oldValue = expectedSteps[i];
                double sum = 0;
                int validMoves = 0;

                for (int k = 1; k <= diceFaces; k++) {
                    int nextPos = getActualPosition(i + k);
                    if (nextPos <= boardSize) {
                        sum += expectedSteps[nextPos];
                        validMoves++;
                    }
                }

                if (validMoves > 0) {
                    expectedSteps[i] = 1.0 + sum / validMoves;
                }

                maxDiff = Math.max(maxDiff, Math.abs(expectedSteps[i] - oldValue));
            }

            if (maxDiff < epsilon) {
                System.out.println("期望步数收敛于第 " + (iter + 1) + " 次迭代");
                break;
            }
        }

        expectedComputed = true;
        return expectedSteps;
    }

    /**
     * 计算到达每个格子的精确概率分布（经过n步后）
     * 使用动态规划：dp[n][i] 表示第n步位于格子i的概率
     */
    public double[][] computeProbabilityDistribution(int maxSteps) {
        double[][] dp = new double[maxSteps + 1][boardSize + 1];
        dp[0][0] = 1.0;  // 第0步在起点

        for (int step = 1; step <= maxSteps; step++) {
            for (int pos = 0; pos <= boardSize; pos++) {
                if (dp[step - 1][pos] == 0) continue;

                // 从pos掷骰子移动到各个位置
                for (int k = 1; k <= diceFaces; k++) {
                    int nextPos = getActualPosition(pos + k);
                    if (nextPos <= boardSize) {
                        dp[step][nextPos] += dp[step - 1][pos] / diceFaces;
                    }
                }
            }
        }

        return dp;
    }

    /**
     * 蒙特卡洛模拟：估算多玩家游戏的获胜概率
     * @param numPlayers 玩家数量
     * @param numSimulations 模拟次数
     * @return 各玩家获胜概率
     */
    public double[] simulateWinProbability(int numPlayers, int numSimulations) {
        Random rand = new Random(42);  // 固定种子保证可重复
        int[] wins = new int[numPlayers];

        for (int sim = 0; sim < numSimulations; sim++) {
            int[] positions = new int[numPlayers];
            boolean[] finished = new boolean[numPlayers];
            int remaining = numPlayers;

            while (remaining > 0) {
                for (int p = 0; p < numPlayers; p++) {
                    if (finished[p]) continue;

                    // 掷骰子
                    int roll = rand.nextInt(diceFaces) + 1;
                    positions[p] = getActualPosition(positions[p] + roll);

                    if (positions[p] >= boardSize) {
                        positions[p] = boardSize;
                        finished[p] = true;
                        remaining--;

                        // 记录获胜者（按到达顺序）
                        if (wins[p] == 0 && remaining == numPlayers - 1) {
                            // 第一个到达的获得额外权重
                        }
                    }
                }
            }

            // 记录最先到达的玩家
            for (int p = 0; p < numPlayers; p++) {
                if (finished[p]) {
                    wins[p]++;
                    break;  // 只记录第一名
                }
            }
        }

        double[] probabilities = new double[numPlayers];
        for (int p = 0; p < numPlayers; p++) {
            probabilities[p] = (double) wins[p] / numSimulations;
        }

        return probabilities;
    }

    /**
     * 分析每个格子的"危险程度"：到达该格子后期望增加的步数
     */
    public double[] analyzeCellDanger() {
        if (!expectedComputed) computeExpectedSteps();

        double[] danger = new double[boardSize + 1];
        for (int i = 0; i < boardSize; i++) {
            // 计算从i出发的平均期望
            double avgNextExpected = 0;
            int validMoves = 0;

            for (int k = 1; k <= diceFaces; k++) {
                int nextPos = getActualPosition(i + k);
                if (nextPos <= boardSize) {
                    avgNextExpected += expectedSteps[nextPos];
                    validMoves++;
                }
            }

            if (validMoves > 0) {
                avgNextExpected /= validMoves;
                // 危险度 = 从该格子出发的平均后续期望 - 当前期望 + 1
                danger[i] = avgNextExpected - expectedSteps[i] + 1;
            }
        }

        return danger;
    }

    /**
     * 打印完整的概率分析报告
     */
    public void printAnalysisReport() {
        System.out.println("=== 飞行棋概率分析报告 ===\n");

        // 期望步数
        double[] exp = computeExpectedSteps();
        System.out.println("从起点到达终点的期望步数: " + String.format("%.2f", exp[0]));
        System.out.println("\n前10个格子的期望剩余步数:");
        for (int i = 0; i < Math.min(10, boardSize); i++) {
            System.out.printf("  格子 %d: %.4f%n", i, exp[i]);
        }

        // 特定步数到达终点的概率
        System.out.println("\n到达终点的概率分布（前20步）:");
        double[][] dist = computeProbabilityDistribution(20);
        for (int step = 1; step <= 20; step++) {
            System.out.printf("  第 %2d 步: %.6f%n", step, dist[step][boardSize]);
        }

        // 多玩家获胜概率
        System.out.println("\n2人游戏的先手获胜概率:");
        double[] winProb = simulateWinProbability(2, 100000);
        for (int p = 0; p < winProb.length; p++) {
            System.out.printf("  玩家 %d: %.4f%n", p + 1, winProb[p]);
        }

        // 危险格子分析
        System.out.println("\n最危险的5个格子（蛇头位置）:");
        double[] danger = analyzeCellDanger();
        List<int[]> dangerList = new ArrayList<>();
        for (int i = 0; i < boardSize; i++) {
            dangerList.add(new int[]{i, (int)(danger[i] * 10000)});
        }
        dangerList.sort((a, b) -> b[1] - a[1]);
        for (int i = 0; i < Math.min(5, dangerList.size()); i++) {
            int[] d = dangerList.get(i);
            System.out.printf("  格子 %d: 危险指数 %.4f%n", d[0], d[1] / 10000.0);
        }
    }

    public static void main(String[] args) {
        // 创建经典100格飞行棋，6面骰
        FlightChessAnalyzer game = new FlightChessAnalyzer(100, 6);

        // 添加经典蛇
        game.addSnake(99, 1);   game.addSnake(95, 35);
        game.addSnake(92, 48);  game.addSnake(89, 51);
        game.addSnake(74, 42);  game.addSnake(64, 22);
        game.addSnake(46, 13);  game.addSnake(33, 9);

        // 添加经典梯子
        game.addLadder(3, 22);  game.addLadder(8, 26);
        game.addLadder(20, 41); game.addLadder(28, 56);
        game.addLadder(40, 59); game.addLadder(50, 67);
        game.addLadder(63, 81); game.addLadder(71, 91);

        game.printAnalysisReport();
    }
}

算法复杂度分析

扩展思考

1. 非均匀骰子：若骰子各面概率不均，修改转移概率权重即可。
2. 策略优化：当存在多条路径选择时，可用Minimax或期望最大化进行决策。
3. 大棋盘优化：对于超大棋盘，稀疏矩阵方法可加速求解。

总结

本文将飞行棋抽象为马尔可夫链模型，使用Java实现了期望步数动态规划计算、精确概率分布推导和多玩家蒙特卡洛模拟。算法核心是基于状态转移的递推求解，是概率论与动态规划结合的经典案例。