每日算法 — 使用java实现地产大亨：概率期望与马尔可夫链模拟

引言

地产大亨（Monopoly）是全球最经典的桌游之一，玩家在棋盘上掷骰子移动、购买地产、收取租金。本文用Java实现地产大亨的核心概率引擎，重点讲解两个算法：一是基于马尔可夫链（Markov Chain）计算玩家落在每个格子的稳态概率，二是利用蒙特卡洛模拟（Monte Carlo Simulation）评估不同投资策略的期望收益。

核心算法设计

1. 马尔可夫链稳态概率

Monopoly棋盘有40个格子，玩家每次掷两个六面骰子前进2-12格。由于骰子结果服从离散概率分布，每次移动构成一个马尔可夫过程。设转移矩阵P，其中 P[i][j] 表示从格子i一步到达格子j的概率。稳态概率向量π满足 π = πP，可通过幂迭代法求解。

2. 蒙特卡洛模拟

对于复杂的游戏规则（如机会卡、入狱、三连 doubles 等），解析求解困难。蒙特卡洛通过大量随机对局采样，统计各格子被访问频率及不同策略的胜率。

完整Java实现

import java.util.*;

/**
 * 地产大亨概率引擎：马尔可夫链 + 蒙特卡洛模拟
 */
public class MonopolySimulator {
    static final int BOARD_SIZE = 40; // 标准Monopoly有40格
    static final int JAIL = 10;
    static final int GO_TO_JAIL = 30;

    // 骰子概率分布（两个六面骰）
    double[] diceProb = new double[13]; // 索引2-12有效

    public MonopolySimulator() {
        initDiceProb();
    }

    void initDiceProb() {
        // 两个骰子之和的概率
        for (int d1 = 1; d1 <= 6; d1++) {
            for (int d2 = 1; d2 <= 6; d2++) {
                diceProb[d1 + d2] += 1.0 / 36.0;
            }
        }
    }

    /**
     * 构建基础转移矩阵（仅考虑骰子移动，不含特殊规则）
     */
    double[][] buildTransitionMatrix() {
        double[][] P = new double[BOARD_SIZE][BOARD_SIZE];
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int roll = 2; roll <= 12; roll++) {
                int next = (i + roll) % BOARD_SIZE;
                P[i][next] += diceProb[roll];
            }
        }
        return P;
    }

    /**
     * 构建含规则的增强转移矩阵
     * 包含：入狱、机会卡跳转、三连double入狱
     */
    double[][] buildEnhancedTransitionMatrix() {
        double[][] P = new double[BOARD_SIZE][BOARD_SIZE];
        Random rand = new Random(42); // 固定种子便于复现

        // 机会卡目标（简化版）
        int[] chanceCards = {0, 24, 11, -1, -1, -1, -1, -1, 5, 39, -1, -1, -1, -1, -1, -1};
        // 社区宝箱目标（简化版）
        int[] chestCards = {0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1};

        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int roll = 2; roll <= 12; roll++) {
                int next = (i + roll) % BOARD_SIZE;
                double prob = diceProb[roll];

                // 经过Go_to_Jail直接入狱
                if (next == GO_TO_JAIL) {
                    P[i][JAIL] += prob;
                    continue;
                }

                // 机会卡格子（7, 22, 36）
                if (next == 7 || next == 22 || next == 36) {
                    int card = chanceCards[rand.nextInt(chanceCards.length)];
                    if (card >= 0) {
                        P[i][card] += prob * 0.5; // 约一半机会卡会跳转
                        P[i][next] += prob * 0.5;
                    } else {
                        P[i][next] += prob;
                    }
                    continue;
                }

                // 社区宝箱格子（2, 17, 33）
                if (next == 2 || next == 17 || next == 33) {
                    int card = chestCards[rand.nextInt(chestCards.length)];
                    if (card >= 0) {
                        P[i][card] += prob * 0.0625; // 1/16概率去Go
                        P[i][next] += prob * 0.9375;
                    } else {
                        P[i][next] += prob;
                    }
                    continue;
                }

                P[i][next] += prob;
            }
        }
        return P;
    }

    /**
     * 幂迭代法求稳态概率
     */
    double[] computeSteadyState(double[][] P, int iterations) {
        double[] pi = new double[BOARD_SIZE];
        Arrays.fill(pi, 1.0 / BOARD_SIZE); // 均匀初始化

        for (int iter = 0; iter < iterations; iter++) {
            double[] next = new double[BOARD_SIZE];
            for (int j = 0; j < BOARD_SIZE; j++) {
                for (int i = 0; i < BOARD_SIZE; i++) {
                    next[j] += pi[i] * P[i][j];
                }
            }
            pi = next;
        }
        return pi;
    }

    /**
     * 蒙特卡洛模拟：模拟大量对局，统计格子访问频率
     */
    double[] monteCarloSimulation(int rounds, int stepsPerRound) {
        double[] visitCount = new double[BOARD_SIZE];
        Random rand = new Random(42);

        for (int r = 0; r < rounds; r++) {
            int pos = 0; // 从Go出发
            int consecutiveDoubles = 0;

            for (int s = 0; s < stepsPerRound; s++) {
                int d1 = rand.nextInt(6) + 1;
                int d2 = rand.nextInt(6) + 1;

                if (d1 == d2) {
                    consecutiveDoubles++;
                    if (consecutiveDoubles == 3) {
                        pos = JAIL;
                        consecutiveDoubles = 0;
                        visitCount[pos]++;
                        continue;
                    }
                } else {
                    consecutiveDoubles = 0;
                }

                pos = (pos + d1 + d2) % BOARD_SIZE;

                // 特殊格子处理
                if (pos == GO_TO_JAIL) {
                    pos = JAIL;
                } else if (pos == 7 || pos == 22 || pos == 36) {
                    // 机会卡简化处理
                    if (rand.nextDouble() < 0.5) {
                        int[] destinations = {0, 24, 11, 5, 39};
                        pos = destinations[rand.nextInt(destinations.length)];
                    }
                }

                visitCount[pos]++;
            }
        }

        // 归一化为概率
        double total = Arrays.stream(visitCount).sum();
        for (int i = 0; i < BOARD_SIZE; i++) visitCount[i] /= total;
        return visitCount;
    }

    /**
     * 投资策略评估：计算购买某地产的期望收益率
     */
    double evaluateProperty(int propertyPos, double[] steadyProb, 
                            int price, int[] rents, int houseCost) {
        double baseIncome = steadyProb[propertyPos] * rents[0] * 100; // 假设每轮对手付租期望
        double roi = baseIncome / price;

        System.out.printf("地产位置: %d, 购买价: %d, 基础租金: %d%n", 
                          propertyPos, price, rents[0]);
        System.out.printf("被访问概率: %.4f, 期望每轮收益: %.2f, ROI: %.4f%n",
                          steadyProb[propertyPos], baseIncome, roi);
        return roi;
    }

    void runAnalysis() {
        System.out.println("=== 地产大亨概率分析 ===\n");

        // 1. 基础马尔可夫链
        double[][] baseP = buildTransitionMatrix();
        double[] baseSteady = computeSteadyState(baseP, 1000);
        System.out.println("基础马尔可夫链稳态概率（仅骰子）：");
        printTopPositions(baseSteady, 10);

        // 2. 增强马尔可夫链
        double[][] enhancedP = buildEnhancedTransitionMatrix();
        double[] enhancedSteady = computeSteadyState(enhancedP, 1000);
        System.out.println("\n增强马尔可夫链稳态概率（含入狱/机会卡）：");
        printTopPositions(enhancedSteady, 10);

        // 3. 蒙特卡洛验证
        double[] mcResult = monteCarloSimulation(10000, 100);
        System.out.println("\n蒙特卡洛模拟结果（10000局×100步）：");
        printTopPositions(mcResult, 10);

        // 4. 策略评估：评估 Illinois Avenue (位置24)
        System.out.println("\n=== 投资策略评估 ===");
        evaluateProperty(24, mcResult, 240, new int[]{20, 100, 300, 750, 925, 1100}, 150);
        evaluateProperty(39, mcResult, 400, new int[]{50, 200, 600, 1400, 1700, 2000}, 200);
    }

    void printTopPositions(double[] probs, int n) {
        Integer[] indices = new Integer[BOARD_SIZE];
        for (int i = 0; i < BOARD_SIZE; i++) indices[i] = i;
        Arrays.sort(indices, (a, b) -> Double.compare(probs[b], probs[a]));

        String[] names = {
            "Go", "Mediterranean", "Community Chest", "Baltic", "Income Tax",
            "Reading Railroad", "Oriental", "Chance", "Vermont", "Connecticut",
            "Jail", "St.Charles", "Electric", "States", "Virginia",
            "Pennsylvania RR", "St.James", "Community Chest", "Tennessee", "New York",
            "Free Parking", "Kentucky", "Chance", "Indiana", "Illinois",
            "B&O Railroad", "Atlantic", "Ventnor", "Water Works", "Marvin Gardens",
            "Go To Jail", "Pacific", "North Carolina", "Community Chest", "Pennsylvania",
            "Short Line", "Chance", "Park Place", "Luxury Tax", "Boardwalk"
        };

        for (int i = 0; i < n; i++) {
            int idx = indices[i];
            System.out.printf("  %2d. %-20s 概率: %.4f%n", i+1, names[idx], probs[idx]);
        }
    }

    public static void main(String[] args) {
        new MonopolySimulator().runAnalysis();
    }
}

复杂度分析

• 马尔可夫链稳态计算：转移矩阵为 40×40，幂迭代每次矩阵向量乘法 O(40²) = O(1600)，迭代1000次总时间 O(1.6×10⁶)，空间 O(40²)。
• 蒙特卡洛模拟：时间复杂度 O(对局数 × 每局步数)，空间 O(棋盘大小)。10000局×100步可在毫秒级完成。
• 策略评估：基于稳态概率的线性计算，O(1)。

总结

本文实现了地产大亨的概率分析引擎：马尔可夫链揭示棋盘各格子的理论访问概率，蒙特卡洛模拟验证并纳入复杂规则。分析结果表明，由于入狱机制和机会卡，Jail（第10格）及相邻格子的访问概率显著高于均匀分布。读者可在此基础上扩展完整游戏规则、多玩家博弈策略、拍卖机制等，构建更完整的AI对手。