每日算法 — 使用java实现叠叠乐：蒙特卡洛树搜索与最优抽取风险评估策略

引言

叠叠乐（Jenga）是一款经典的物理益智游戏，玩家轮流从木塔中抽取积木并叠放到塔顶，使塔倒塌者判负。本文将叠叠乐中的最优抽取决策建模为不完全信息博弈问题，并使用蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS）结合风险评估函数，让AI在考虑物理稳定性、对手反应和塔结构变化的多重因素下做出最优决策。

问题建模

塔的结构表示

标准叠叠乐由54块积木组成，每层3块，共18层。相邻层之间旋转90度交错堆叠。每块积木的状态由以下属性定义：

• 位置 (layer, index)：层号（0为底层）和该层内的序号（0~2）
• 质心偏移：该块被抽出后，剩余结构的质心偏移量
• 支撑状态：该块是否为上方某层的直接支撑

博弈树模型

将叠叠乐建模为双人零和博弈：

• 状态：当前塔的三维结构（每块积木是否存在）
• 动作：选择一块合法积木抽出并放置到塔顶
• 转移：更新塔结构，检查是否倒塌
• 终止：塔倒塌时，当前行动玩家判负（得分为-1），对手得+1

由于塔的实际物理行为具有随机性（同一块积木的抽出可能导致不同倾斜），我们引入随机节点：每次抽取后，塔的倾斜角度服从以质心偏移为均值的高斯分布。

蒙特卡洛树搜索

MCTS通过四个阶段迭代构建搜索树：

1. 选择（Selection）：从根节点出发，使用UCB1公式选择子节点，直到到达未完全展开的节点
2. 扩展（Expansion）：为该节点添加一个未访问的子节点
3. 模拟（Simulation）：从新节点出发，使用默认策略（随机或启发式）快速模拟至终局
4. 回溯（Backpropagation）：将模拟结果沿路径更新所有祖先节点的统计值

UCB1公式：

$$
\text{UCB1} = \bar{X}_j + C \sqrt{\frac{2 \ln n}{n_j}}
$$

其中 $\bar{X}_j$ 为子节点平均收益，$n$ 为父节点访问次数，$n_j$ 为子节点访问次数，$C$ 为探索常数。

Java实现

核心数据结构

import java.util.*;

/**
 * 叠叠乐MCTS求解器
 * 蒙特卡洛树搜索 + 风险评估
 */
public class JengaMCTSSolver {

    static final int BLOCKS_PER_LAYER = 3;
    static final int TOTAL_LAYERS = 18;
    static final int TOTAL_BLOCKS = 54;
    static final double EXPLORATION_C = 1.414;  // UCB1探索常数 sqrt(2)
    static final int SIMULATION_DEPTH = 20;      // 最大模拟深度
    static final int MAX_ITERATIONS = 5000;      // MCTS迭代次数

    // 积木块
    static class Block {
        int layer;
        int index;  // 0~2
        boolean present;  // 是否仍在塔中
        double mass = 1.0;

        Block(int layer, int index) {
            this.layer = layer;
            this.index = index;
            this.present = true;
        }
    }

    // 塔状态
    static class TowerState {
        Block[][] layers;  // layers[layer][index]
        int currentLayerCount;  // 当前总层数
        int nextLayerOrientation;  // 0=水平, 1=垂直（交替）

        TowerState() {
            layers = new Block[TOTAL_LAYERS * 2][BLOCKS_PER_LAYER];
            currentLayerCount = TOTAL_LAYERS;
            nextLayerOrientation = 0;

            for (int l = 0; l < TOTAL_LAYERS; l++) {
                for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
                    layers[l][i] = new Block(l, i);
                }
            }
        }

        TowerState copy() {
            TowerState clone = new TowerState();
            clone.currentLayerCount = this.currentLayerCount;
            clone.nextLayerOrientation = this.nextLayerOrientation;
            for (int l = 0; l < layers.length; l++) {
                for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
                    if (this.layers[l][i] != null) {
                        Block b = new Block(l, i);
                        b.present = this.layers[l][i].present;
                        clone.layers[l][i] = b;
                    }
                }
            }
            return clone;
        }
    }

    // 动作：从某层抽取某块，放置到新层
    static class Action {
        int fromLayer;
        int fromIndex;

        Action(int layer, int index) {
            this.fromLayer = layer;
            this.fromIndex = index;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Action)) return false;
            Action other = (Action) o;
            return fromLayer == other.fromLayer && fromIndex == other.fromIndex;
        }

        @Override
        public int hashCode() {
            return fromLayer * 10 + fromIndex;
        }

        @Override
        public String toString() {
            return String.format("抽取第%d层第%d块", fromLayer, fromIndex);
        }
    }

    // MCTS节点
    static class MCTSNode {
        TowerState state;
        Action action;  // 到达此节点的动作
        MCTSNode parent;
        List<MCTSNode> children;
        int visits;
        double totalValue;
        boolean fullyExpanded;

        MCTSNode(TowerState state, Action action, MCTSNode parent) {
            this.state = state;
            this.action = action;
            this.parent = parent;
            this.children = new ArrayList<>();
            this.visits = 0;
            this.totalValue = 0;
            this.fullyExpanded = false;
        }

        double getUCB1() {
            if (visits == 0) return Double.MAX_VALUE;
            double exploitation = totalValue / visits;
            double exploration = EXPLORATION_C * Math.sqrt(2 * Math.log(parent.visits) / visits);
            return exploitation + exploration;
        }
    }

风险评估函数

    /**
     * 计算塔的风险评估分数（越高越危险）
     */
    double evaluateRisk(TowerState tower) {
        double risk = 0;

        // 1. 质心偏移风险：计算每层上方的质心是否偏离支撑基础
        for (int l = 1; l < tower.currentLayerCount; l++) {
            double[] com = computeCenterOfMass(tower, l);  // 从第l层往上的质心
            double[] supportBase = computeSupportBase(tower, l - 1);  // 第l-1层的支撑范围

            double xOffset = Math.abs(com[0] - supportBase[0]);
            double zOffset = Math.abs(com[1] - supportBase[1]);

            // 偏移量越大，风险越高，且随高度指数增长
            risk += (xOffset + zOffset) * Math.pow(1.1, l);
        }

        // 2. 支撑缺失风险：检查每层缺失的支撑块数
        for (int l = 1; l < tower.currentLayerCount; l++) {
            int missingSupport = countMissingSupport(tower, l);
            risk += missingSupport * 5.0;
        }

        // 3. 高层的脆弱性：高层积木缺失惩罚更大
        int topMissing = 0;
        for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
            if (!tower.layers[tower.currentLayerCount - 1][i].present) topMissing++;
        }
        risk += topMissing * 3.0;

        return risk;
    }

    /**
     * 计算从startLayer往上的质心坐标 (x, z)
     */
    double[] computeCenterOfMass(TowerState tower, int startLayer) {
        double totalMass = 0, sumX = 0, sumZ = 0;
        for (int l = startLayer; l < tower.currentLayerCount; l++) {
            for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
                Block b = tower.layers[l][i];
                if (b != null && b.present) {
                    double[] pos = getBlockPosition(l, i);
                    sumX += pos[0] * b.mass;
                    sumZ += pos[1] * b.mass;
                    totalMass += b.mass;
                }
            }
        }
        return new double[]{sumX / totalMass, sumZ / totalMass};
    }

    double[] getBlockPosition(int layer, int index) {
        // 简化模型：每层长3单位，每块宽1单位
        boolean isHorizontal = (layer % 2 == 0);
        if (isHorizontal) {
            return new double[]{index - 1.0, 0.0};  // x偏移，z=0
        } else {
            return new double[]{0.0, index - 1.0};  // x=0, z偏移
        }
    }

    double[] computeSupportBase(TowerState tower, int layer) {
        // 支撑基础的范围中心
        double minX = 1, maxX = -1, minZ = 1, maxZ = -1;
        for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
            Block b = tower.layers[layer][i];
            if (b != null && b.present) {
                double[] pos = getBlockPosition(layer, i);
                minX = Math.min(minX, pos[0] - 0.5);
                maxX = Math.max(maxX, pos[0] + 0.5);
                minZ = Math.min(minZ, pos[1] - 0.5);
                maxZ = Math.max(maxZ, pos[1] + 0.5);
            }
        }
        return new double[]{(minX + maxX) / 2, (minZ + maxZ) / 2};
    }

    int countMissingSupport(TowerState tower, int layer) {
        int count = 0;
        for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
            Block b = tower.layers[layer][i];
            if (b == null || !b.present) {
                // 检查上方是否有块依赖此支撑
                if (layer + 1 < tower.currentLayerCount) {
                    boolean hasDependent = false;
                    for (int j = 0; j < BLOCKS_PER_LAYER; j++) {
                        Block above = tower.layers[layer + 1][j];
                        if (above != null && above.present) {
                            hasDependent = true;
                            break;
                        }
                    }
                    if (hasDependent) count++;
                }
            }
        }
        return count;
    }

合法动作生成与状态转移

    /**
     * 获取当前状态下所有合法抽取动作
     * 规则：不能抽取顶层，不能抽取导致立即倒塌的块
     */
    List<Action> getLegalActions(TowerState tower) {
        List<Action> actions = new ArrayList<>();

        for (int l = 0; l < tower.currentLayerCount - 1; l++) {  // 不抽顶层
            for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
                Block b = tower.layers[l][i];
                if (b != null && b.present) {
                    // 检查抽出后是否导致结构不稳定（简化：允许抽取，但在模拟中评估风险）
                    actions.add(new Action(l, i));
                }
            }
        }

        return actions;
    }

    /**
     * 执行动作并返回新状态
     */
    TowerState applyAction(TowerState tower, Action action) {
        TowerState next = tower.copy();

        // 移除原位置的块
        next.layers[action.fromLayer][action.fromIndex].present = false;

        // 放置到塔顶新层
        int newLayer = next.currentLayerCount;
        // 检查新层是否已满，若满则创建下一层
        int placedCount = 0;
        for (int i = 0; i < BLOCKS_PER_LAYER; i++) {
            if (next.layers[newLayer][i] != null && next.layers[newLayer][i].present) {
                placedCount++;
            }
        }

        if (placedCount >= BLOCKS_PER_LAYER) {
            newLayer++;
            next.currentLayerCount++;
        }

        if (newLayer < next.layers.length) {
            if (next.layers[newLayer][placedCount] == null) {
                next.layers[newLayer][placedCount] = new Block(newLayer, placedCount);
            }
            next.layers[newLayer][placedCount].present = true;
        }

        return next;
    }

    /**
     * 检查塔是否倒塌
     * 简化模型：若风险评估超过阈值，则以概率判定倒塌
     */
    boolean isCollapsed(TowerState tower) {
        double risk = evaluateRisk(tower);
        double threshold = 50.0;
        if (risk > threshold) {
            double collapseProb = Math.min(0.95, (risk - threshold) / 100.0);
            return Math.random() < collapseProb;
        }
        return false;
    }

MCTS核心算法

    /**
     * MCTS主循环
     */
    Action mctsSearch(TowerState rootState) {
        MCTSNode root = new MCTSNode(rootState, null, null);

        for (int iter = 0; iter < MAX_ITERATIONS; iter++) {
            // 1. 选择
            MCTSNode node = select(root);

            // 2. 扩展
            if (!isTerminal(node.state)) {
                node = expand(node);
            }

            // 3. 模拟
            double reward = simulate(node.state);

            // 4. 回溯
            backpropagate(node, reward);
        }

        // 返回访问次数最多的动作（稳健选择）
        MCTSNode bestChild = null;
        int maxVisits = -1;
        for (MCTSNode child : root.children) {
            if (child.visits > maxVisits) {
                maxVisits = child.visits;
                bestChild = child;
            }
        }
        return bestChild != null ? bestChild.action : null;
    }

    MCTSNode select(MCTSNode node) {
        while (!node.children.isEmpty() && node.fullyExpanded) {
            node = getBestUCB1Child(node);
        }
        return node;
    }

    MCTSNode getBestUCB1Child(MCTSNode node) {
        MCTSNode best = null;
        double bestUCB = Double.NEGATIVE_INFINITY;
        for (MCTSNode child : node.children) {
            double ucb = child.getUCB1();
            if (ucb > bestUCB) {
                bestUCB = ucb;
                best = child;
            }
        }
        return best;
    }

    MCTSNode expand(MCTSNode node) {
        List<Action> legalActions = getLegalActions(node.state);

        // 找出未访问过的动作
        Set<Action> tried = new HashSet<>();
        for (MCTSNode child : node.children) {
            tried.add(child.action);
        }

        for (Action action : legalActions) {
            if (!tried.contains(action)) {
                TowerState nextState = applyAction(node.state, action);
                MCTSNode child = new MCTSNode(nextState, action, node);
                node.children.add(child);

                if (node.children.size() == legalActions.size()) {
                    node.fullyExpanded = true;
                }
                return child;
            }
        }

        node.fullyExpanded = true;
        return node;
    }

    /**
     * 默认策略模拟：随机选择动作直到终局或深度限制
     */
    double simulate(TowerState state) {
        TowerState simState = state.copy();
        int depth = 0;
        int currentPlayer = 0;  // 0或1

        while (depth < SIMULATION_DEPTH) {
            if (isCollapsed(simState)) {
                // 上一个行动的玩家导致倒塌，当前玩家获胜
                return currentPlayer == 0 ? 1.0 : -1.0;
            }

            List<Action> actions = getLegalActions(simState);
            if (actions.isEmpty()) break;

            // 启发式随机：优先选择风险较低的动作
            Action chosen = selectHeuristicAction(simState, actions);
            simState = applyAction(simState, chosen);
            currentPlayer = 1 - currentPlayer;
            depth++;
        }

        // 若未倒塌，用风险评估作为终局估值
        double risk = evaluateRisk(simState);
        return -risk / 100.0;  // 风险越低，估值越高
    }

    /**
     * 启发式动作选择：倾向于选择风险低的动作
     */
    Action selectHeuristicAction(TowerState state, List<Action> actions) {
        double[] weights = new double[actions.size()];
        double totalWeight = 0;

        for (int i = 0; i < actions.size(); i++) {
            TowerState next = applyAction(state, actions.get(i));
            double risk = evaluateRisk(next);
            // 权重与风险成反比
            weights[i] = Math.exp(-risk / 20.0);
            totalWeight += weights[i];
        }

        double r = Math.random() * totalWeight;
        double cumsum = 0;
        for (int i = 0; i < actions.size(); i++) {
            cumsum += weights[i];
            if (r <= cumsum) return actions.get(i);
        }
        return actions.get(actions.size() - 1);
    }

    void backpropagate(MCTSNode node, double reward) {
        while (node != null) {
            node.visits++;
            node.totalValue += reward;
            // 奖励取反（零和博弈）
            reward = -reward;
            node = node.parent;
        }
    }

    boolean isTerminal(TowerState state) {
        return isCollapsed(state);
    }

测试入口

    public static void main(String[] args) {
        JengaMCTSSolver solver = new JengaMCTSSolver();
        TowerState tower = new TowerState();

        System.out.println("初始风险评估: " + solver.evaluateRisk(tower));

        // 模拟对局
        for (int turn = 0; turn < 20; turn++) {
            if (solver.isCollapsed(tower)) {
                System.out.println("塔在回合 " + turn + " 倒塌！");
                break;
            }

            Action bestAction = solver.mctsSearch(tower);
            if (bestAction == null) {
                System.out.println("无合法动作，对局结束");
                break;
            }

            System.out.println("回合 " + (turn + 1) + ": " + bestAction);
            tower = solver.applyAction(tower, bestAction);
            System.out.println("  当前风险评估: " + String.format("%.2f", solver.evaluateRisk(tower)));
        }
    }
}

算法分析

MCTS在不完全信息博弈中的优势在于：无需精确的终局估值函数，通过大量随机模拟即可收敛到近似最优策略。叠叠乐的物理随机性天然适合MCTS的概率框架。

扩展方向

1. 神经网络策略网络（AlphaZero范式）：用ResNet替代随机模拟，指导MCTS的走子概率和局面估值
2. 对手建模：根据对手历史行为调整其模拟策略，实现自适应对策
3. 三维物理引擎集成：用Bullet或Box2D精确模拟积木抽出时的摩擦力、振动和倾倒过程

总结

本文将叠叠乐的抽取决策建模为双人零和博弈，设计了包含质心偏移、支撑缺失和高层脆弱性等多维度的风险评估函数，并基于蒙特卡洛树搜索在庞大的动作空间中寻找最优策略。读者可以调整MCTS的迭代次数和模拟深度来平衡决策质量与响应速度，也可以将框架迁移到其他物理博弈类游戏AI中。