每日算法 — 使用java实现Jenga抽积木：物理稳定性检测与贪心最优抽取策略

引言

Jenga（层层叠/抽积木）是一款考验耐心与物理直觉的经典桌游。玩家轮流从由54块木块堆叠而成的塔中抽取一块，并将其放置到塔顶，直到塔倒塌为止。看似简单的规则背后，隐藏着丰富的物理学与算法设计问题：如何判断抽取某块积木后塔是否仍然稳定？在多个可抽取的积木中，哪一块是最优选择？本文将用Java实现一个带物理稳定性检测的Jenga游戏，并讲解贪心策略如何帮助AI做出最优抽取决策。

一、游戏规则与物理模型

1.1 基本规则

标准Jenga塔由16层组成，每层3块木块，相邻层木块方向垂直交替。每层木块之间会有一定的间隙，使得某些木块更容易被抽出。

1.2 物理稳定性模型

塔的稳定性取决于重心是否始终落在支撑面内。每抽取一块积木后，我们需要重新计算整个塔的重心位置。

设第 $i$ 层有 $n_i$ 块木块（通常为2或3块），每块木块的质量为 $m$，重心位于其几何中心。整个塔的重心 $(\bar{x}, \bar{y})$ 可通过加权平均计算：

$$
\bar{x} = \frac{\sum_{i} m_i x_i}{\sum_{i} m_i}, \quad \bar{y} = \frac{\sum_{i} m_i y_i}{\sum_{i} m_i}
$$

如果重心投影落在最底层支撑面的边界内，则塔是稳定的；否则塔会倒塌。

1.3 力矩平衡分析

除了整体重心，还需要考虑层间力矩。当某层缺少一块或多块木块时，上层对下层的压力分布会发生变化。若压力中心偏离该层剩余木块的支撑范围，该层就会发生局部倾覆。

二、核心算法设计

2.1 数据结构

我们用三维数组表示塔的状态，同时用物理对象记录每块木块的位置和质量分布。

2.2 重心计算算法

计算塔重心需要遍历所有剩余木块，累加质量矩后除以总质量。

2.3 贪心最优抽取策略

AI的决策流程如下：

1. 枚举候选积木：找出所有可以从侧面抽出且不会立即导致塔倒塌的积木。
2. 评估稳定性损失：对每块候选积木，模拟抽取后的塔状态，计算新的重心偏移量和最小稳定裕度。
3. 选择最优积木：选择使抽取后塔稳定性最高（重心偏移最小、稳定裕度最大）的积木。
4. 放置策略：将抽出的积木放置到塔顶时，选择使整体重心最居中的位置。

三、Java完整实现

import java.util.*;

/**
 * Jenga游戏物理稳定性检测与贪心AI决策
 * 
 * 核心设计：
 * 1. 用三维数组表示塔的状态
 * 2. 物理引擎计算重心与力矩平衡
 * 3. 贪心策略选择最优抽取积木
 */
public class JengaGame {

    // 塔的配置参数
    private static final int LAYERS = 16;           // 总层数
    private static final int BLOCKS_PER_LAYER = 3;  // 每层木块数
    private static final double BLOCK_WIDTH = 7.5;  // 单块宽度(cm)
    private static final double BLOCK_HEIGHT = 2.5; // 单块高度(cm)
    private static final double BLOCK_DEPTH = 15.0; // 单块深度(cm)
    private static final double GAP = 0.2;          // 木块间隙(cm)

    // 塔的当前状态：tower[layer][position] = true表示该位置有木块
    private boolean[][] tower;
    private int currentTopLayer; // 当前最高有木块的层

    public JengaGame() {
        this.tower = new boolean[LAYERS * 2][BLOCKS_PER_LAYER]; // 预留扩展空间
        initializeTower();
    }

    /**
     * 初始化标准Jenga塔：16层，每层3块，交替方向
     */
    private void initializeTower() {
        for (int layer = 0; layer < LAYERS; layer++) {
            for (int pos = 0; pos < BLOCKS_PER_LAYER; pos++) {
                tower[layer][pos] = true;
            }
        }
        currentTopLayer = LAYERS - 1;
    }

    /**
     * 表示一块木块的物理信息
     */
    static class Block {
        int layer, position;
        double centerX, centerY, centerZ;
        double mass;

        Block(int layer, int position, double cx, double cy, double cz, double mass) {
            this.layer = layer;
            this.position = position;
            this.centerX = cx;
            this.centerY = cy;
            this.centerZ = cz;
            this.mass = mass;
        }
    }

    /**
     * 表示塔的重心分析结果
     */
    static class StabilityResult {
        double centerX, centerZ;     // 重心投影坐标
        double stabilityMargin;      // 稳定裕度（重心到支撑边界的最近距离）
        boolean isStable;            // 是否稳定
        double maxTiltAngle;         // 最大倾斜角（度）

        StabilityResult(double cx, double cz, double margin, boolean stable, double tilt) {
            this.centerX = cx;
            this.centerZ = cz;
            this.stabilityMargin = margin;
            this.isStable = stable;
            this.maxTiltAngle = tilt;
        }
    }

    /**
     * 获取当前塔中所有存在的木块列表
     */
    public List<Block> getAllBlocks() {
        List<Block> blocks = new ArrayList<>();
        double layerHeight = BLOCK_HEIGHT;

        for (int layer = 0; layer <= currentTopLayer; layer++) {
            // 偶数层：木块沿X轴排列；奇数层：木块沿Z轴排列
            boolean isXDirection = (layer % 2 == 0);
            double y = layer * layerHeight + layerHeight / 2.0;

            for (int pos = 0; pos < BLOCKS_PER_LAYER; pos++) {
                if (tower[layer][pos]) {
                    double x, z;
                    if (isXDirection) {
                        // 沿X轴排列
                        x = (pos - 1) * (BLOCK_WIDTH + GAP);
                        z = 0;
                    } else {
                        // 沿Z轴排列
                        x = 0;
                        z = (pos - 1) * (BLOCK_WIDTH + GAP);
                    }
                    blocks.add(new Block(layer, pos, x, y, z, 1.0));
                }
            }
        }
        return blocks;
    }

    /**
     * 计算塔的重心与稳定性
     * 
     * 算法步骤：
     * 1. 遍历所有木块，累加质量矩
     * 2. 计算加权平均重心
     * 3. 计算重心到支撑边界的距离（稳定裕度）
     * 4. 计算最大倾斜角
     */
    public StabilityResult calculateStability() {
        List<Block> blocks = getAllBlocks();
        if (blocks.isEmpty()) {
            return new StabilityResult(0, 0, 0, false, 0);
        }

        double totalMass = 0;
        double momentX = 0, momentZ = 0;

        for (Block b : blocks) {
            totalMass += b.mass;
            momentX += b.mass * b.centerX;
            momentZ += b.mass * b.centerZ;
        }

        double centerX = momentX / totalMass;
        double centerZ = momentZ / totalMass;

        // 计算支撑面边界（最底层的范围）
        double supportHalfWidth = (BLOCKS_PER_LAYER * BLOCK_WIDTH + (BLOCKS_PER_LAYER - 1) * GAP) / 2.0;
        double supportHalfDepth = BLOCK_DEPTH / 2.0;

        // 稳定裕度：重心到支撑边界的最小距离
        double marginX = supportHalfWidth - Math.abs(centerX);
        double marginZ = supportHalfDepth - Math.abs(centerZ);
        double stabilityMargin = Math.min(marginX, marginZ);

        // 计算最大倾斜角（简化模型）
        double towerHeight = (currentTopLayer + 1) * BLOCK_HEIGHT;
        double maxTiltX = Math.toDegrees(Math.atan2(Math.abs(centerX), towerHeight));
        double maxTiltZ = Math.toDegrees(Math.atan2(Math.abs(centerZ), towerHeight));
        double maxTilt = Math.max(maxTiltX, maxTiltZ);

        boolean isStable = stabilityMargin > 0.1; // 保留0.1cm安全裕度

        return new StabilityResult(centerX, centerZ, stabilityMargin, isStable, maxTilt);
    }

    /**
     * 判断某块木块是否可以被抽取
     * 
     * 条件：该木块所在层不是最顶层，且该层至少还有另一块木块支撑
     */
    public boolean canRemove(int layer, int position) {
        if (layer > currentTopLayer - 1) return false; // 不能抽最顶层
        if (!tower[layer][position]) return false;      // 该位置没有木块

        // 统计该层剩余木块数
        int remaining = 0;
        for (int p = 0; p < BLOCKS_PER_LAYER; p++) {
            if (tower[layer][p]) remaining++;
        }

        return remaining >= 2; // 至少留一块支撑上层
    }

    /**
     * 模拟抽取某块木块后的稳定性
     */
    public StabilityResult simulateRemove(int layer, int position) {
        // 临时移除
        boolean original = tower[layer][position];
        tower[layer][position] = false;

        StabilityResult result = calculateStability();

        // 恢复
        tower[layer][position] = original;
        return result;
    }

    /**
     * 贪心策略：选择最优抽取积木
     * 
     * 评估函数综合考虑：
     * 1. 抽取后的稳定裕度（越大越好）
     * 2. 重心偏移量（越小越好）
     * 3. 所在层的高度（越低越好，因为低层移除对整体影响较小）
     */
    public int[] chooseBestBlockToRemove() {
        List<int[]> candidates = new ArrayList<>();

        // 枚举所有可抽取的积木
        for (int layer = 0; layer <= currentTopLayer - 1; layer++) {
            for (int pos = 0; pos < BLOCKS_PER_LAYER; pos++) {
                if (canRemove(layer, pos)) {
                    candidates.add(new int[]{layer, pos});
                }
            }
        }

        if (candidates.isEmpty()) {
            return null; // 无积木可抽，游戏结束
        }

        int[] best = null;
        double bestScore = Double.NEGATIVE_INFINITY;

        for (int[] cand : candidates) {
            StabilityResult sim = simulateRemove(cand[0], cand[1]);
            if (!sim.isStable) continue; // 会导致倒塌的跳过

            // 综合评分：稳定裕度权重最高，其次是重心偏移小，最后是层数低
            double score = sim.stabilityMargin * 10.0 
                         - Math.abs(sim.centerX) - Math.abs(sim.centerZ) 
                         - cand[0] * 0.05;

            if (score > bestScore) {
                bestScore = score;
                best = cand;
            }
        }

        return best;
    }

    /**
     * 执行抽取操作
     */
    public boolean removeBlock(int layer, int position) {
        if (!canRemove(layer, position)) return false;

        tower[layer][position] = false;

        // 检查移除后的稳定性
        StabilityResult stability = calculateStability();
        if (!stability.isStable) {
            // 塔倒塌，恢复并返回失败
            tower[layer][position] = true;
            return false;
        }

        return true;
    }

    /**
     * 将木块放置到塔顶
     * 
     * 贪心放置策略：选择使塔整体重心最居中的位置
     */
    public boolean placeOnTop(int sourceLayer, int sourcePos) {
        int newLayer = currentTopLayer + 1;
        if (newLayer >= tower.length) {
            // 扩展数组
            tower = Arrays.copyOf(tower, tower.length * 2);
            for (int i = tower.length / 2; i < tower.length; i++) {
                tower[i] = new boolean[BLOCKS_PER_LAYER];
            }
        }

        // 贪心选择放置位置：使放置后重心最接近中心
        int bestPos = 0;
        double bestCenterDist = Double.MAX_VALUE;

        for (int pos = 0; pos < BLOCKS_PER_LAYER; pos++) {
            if (tower[newLayer][pos]) continue; // 位置已被占用

            tower[newLayer][pos] = true;
            StabilityResult stab = calculateStability();
            tower[newLayer][pos] = false;

            double dist = Math.abs(stab.centerX) + Math.abs(stab.centerZ);
            if (dist < bestCenterDist) {
                bestCenterDist = dist;
                bestPos = pos;
            }
        }

        tower[newLayer][bestPos] = true;
        currentTopLayer = newLayer;
        return true;
    }

    /**
     * AI完整回合：选择最优积木抽取并放置到塔顶
     */
    public boolean aiTurn() {
        int[] best = chooseBestBlockToRemove();
        if (best == null) {
            System.out.println("AI无安全积木可抽，游戏结束！");
            return false;
        }

        int layer = best[0], pos = best[1];
        System.out.printf("AI选择抽取第%d层第%d块积木...%n", layer + 1, pos + 1);

        if (!removeBlock(layer, pos)) {
            System.out.println("抽取后塔倒塌！AI失败！");
            return false;
        }

        placeOnTop(layer, pos);
        System.out.println("AI成功将积木放置到塔顶。");

        StabilityResult stab = calculateStability();
        System.out.printf("当前塔稳定性：裕度=%.3fcm, 重心偏移=(%.3f, %.3f), 倾斜角=%.2f°%n",
            stab.stabilityMargin, stab.centerX, stab.centerZ, stab.maxTiltAngle);

        return true;
    }

    /**
     * 打印塔的侧视图（简化）
     */
    public void printTower() {
        System.out.println("\n=== 当前塔状态 ===");
        for (int layer = currentTopLayer; layer >= 0; layer--) {
            System.out.printf("层%2d: ", layer + 1);
            for (int pos = 0; pos < BLOCKS_PER_LAYER; pos++) {
                System.out.print(tower[layer][pos] ? "[■]" : "[ ]");
            }
            System.out.println();
        }
        StabilityResult stab = calculateStability();
        System.out.printf("稳定性: %s | 裕度: %.2fcm | 倾斜: %.2f°%n",
            stab.isStable ? "稳定" : "不稳定", stab.stabilityMargin, stab.maxTiltAngle);
    }

    public static void main(String[] args) {
        JengaGame game = new JengaGame();
        game.printTower();

        int turn = 1;
        while (true) {
            System.out.println("\n--- 第 " + turn + " 回合 ---");
            boolean success = game.aiTurn();
            game.printTower();

            if (!success) {
                System.out.println("\n游戏在第 " + turn + " 回合结束！");
                break;
            }

            // 模拟延迟
            try { Thread.sleep(500); } catch (InterruptedException e) { }

            turn++;
            if (turn > 50) {
                System.out.println("\n达到最大回合数，游戏结束！");
                break;
            }
        }
    }
}

四、算法复杂度分析

在实际游戏中，$L \approx 16$，$B = 3$，因此单次AI决策的计算量非常小，可在毫秒级完成。

五、贪心策略的局限与改进

5.1 局限

当前贪心策略只考虑当前回合的稳定性最优，没有考虑未来回合的连锁影响。例如，抽取某块积木可能使下一回合的选择空间急剧缩小。

5.2 改进方向

1. Minimax搜索：将对手（或未来的自己）的回合也纳入搜索树，使用两玩家博弈框架。
2. 蒙特卡洛模拟：对每种抽取方案进行多次随机后续推演，选择长期期望最优的方案。
3. 机器学习评估：训练神经网络评估任意塔状态的”危险性”，替代手工设计的评估函数。

六、总结

本文实现了一个完整的Jenga物理模拟与AI决策系统。核心亮点包括：

• 物理模型：基于重心投影与稳定裕度的简化物理引擎
• 贪心策略：综合稳定裕度、重心偏移和层数高度的多因子评估函数
• 模块化设计：分离物理计算、状态模拟与策略决策，便于扩展

读者可以在此基础上添加图形界面（JavaFX/Swing）、多人对战模式或更复杂的物理引擎（如Box2D），将这个算法原型扩展为完整的游戏项目。