引言
马里奥医生（Dr. Mario）是任天堂于1990年推出的经典下落式消除游戏。与俄罗斯方块不同，游戏中下落的是由两种颜色胶囊组成的双格方块，玩家需要将四个及以上同色胶囊横向或纵向连成一线来消除病毒。本文用 Java 实现马里奥医生的 AI 决策系统，重点讲解贪心落点评估算法与连锁消除深度预测，让 AI 能够自主选择最优下落位置与旋转角度。
游戏规则建模
游戏场景为一个 8 行 × 16 列的垂直 bottle（药瓶）：
– 病毒（Virus）：红、黄、蓝三色，散布在药瓶底部区域
– 胶囊（Capsule）：由两个相连的半胶囊组成，有 6 种颜色组合（RR, YY, BB, RY, RB, YB）
– 消除规则：4 个及以上同色半胶囊横向或纵向连续时消除
– 连锁（Chain）：消除后上方胶囊下落，可能形成新的消除，产生连锁反应
AI 的决策空间：对于每一个下落的胶囊，选择{旋转角度} × {水平位置} × {是否加速下落}，共约 40 种可能动作。
核心算法设计
贪心落点评估
AI 需要对每一个可能的落点进行评分，选择分数最高的动作。评估函数包含多个维度：
- 消除贡献（Elimination Score）：落点直接消除的病毒数量 × 100
- 连通潜力（Connectivity Bonus）：与已有同色半胶囊相邻的数量 × 10
- 高度惩罚（Height Penalty）：落点越高（越接近瓶口）扣分越多，防止堆叠过高
- 空洞惩罚（Hole Penalty）：落点下方有空隙时扣分，避免制造难以消除的深洞
- 连锁预测（Chain Prediction）：预测消除后引发的连锁反应深度，深度越大加分越多
综合评分公式：
Score = 消除贡献 + 连通潜力 - 高度惩罚 - 空洞惩罚 + 连锁加分
连锁消除深度预测
连锁是马里奥医生高分的关键。AI 需要模拟”放置胶囊 → 检测消除 → 胶囊下落 → 再次检测”的连锁过程，计算最大连锁深度。
我们使用迭代消除模拟：
1. 在当前棋盘状态下放置胶囊
2. 执行 Flood Fill 检测所有 4 连以上的同色区域
3. 标记消除，让上方胶囊下落（重力模拟）
4. 重复步骤 2-3，直到没有新的消除产生
5. 记录连锁次数和总消除病毒数
Java 实现
import java.util.*;
/**
* 马里奥医生 AI：贪心落点评估与连锁消除预测
*/
public class DrMarioAI {
// 颜色定义
static final int EMPTY = 0;
static final int RED = 1;
static final int YELLOW = 2;
static final int BLUE = 3;
static final int HALF_RED = 4; // 胶囊的左/上半部分
static final int HALF_YELLOW = 5;
static final int HALF_BLUE = 6;
static final int VIRUS_RED = 7;
static final int VIRUS_YELLOW = 8;
static final int VIRUS_BLUE = 9;
static final int ROWS = 16;
static final int COLS = 8;
// 方向数组：上下左右
static final int[] DX = {0, 0, -1, 1};
static final int[] DY = {-1, 1, 0, 0};
int[][] board; // 游戏棋盘
public DrMarioAI() {
this.board = new int[ROWS][COLS];
}
public DrMarioAI(int[][] board) {
this.board = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
System.arraycopy(board[i], 0, this.board[i], 0, COLS);
}
}
/**
* 胶囊定义：(color1, color2)，水平或垂直放置
*/
static class Capsule {
int c1, c2; // 两个半胶囊的颜色
int x, y; // 中心位置（水平时c1在左，垂直时c1在上）
boolean horizontal; // true=水平, false=垂直
Capsule(int c1, int c2) {
this.c1 = c1; this.c2 = c2;
}
// 获取两个半胶囊的坐标
int[][] getPositions() {
if (horizontal) {
return new int[][]{{y, x}, {y, x + 1}};
} else {
return new int[][]{{y, x}, {y + 1, x}};
}
}
}
/**
* 落点动作：包含位置和旋转状态
*/
static class Action {
int x, rotation; // x为水平位置，rotation为旋转角度(0=水平,1=垂直,2=水平翻转,3=垂直翻转)
double score;
int chainDepth;
int virusesCleared;
Action(int x, int rotation) {
this.x = x; this.rotation = rotation;
}
}
/**
* AI 主决策函数：对所有可能落点进行贪心评估
*/
public Action decideBestMove(int[][] currentBoard, int c1, int c2) {
this.board = currentBoard;
List<Action> candidates = new ArrayList<>();
// 遍历所有可能的旋转和水平位置
for (int rot = 0; rot < 4; rot++) {
Capsule cap = new Capsule(c1, c2);
cap.horizontal = (rot == 0 || rot == 2);
// 根据旋转确定两个颜色位置
if (rot == 2) { int tmp = cap.c1; cap.c1 = cap.c2; cap.c2 = tmp; } // 水平翻转
if (rot == 3) { int tmp = cap.c1; cap.c1 = cap.c2; cap.c2 = tmp; } // 垂直翻转
int width = cap.horizontal ? 2 : 1;
for (int x = 0; x <= COLS - width; x++) {
cap.x = x;
cap.y = 0; // 从顶部开始下落
Action action = evaluateDrop(cap);
if (action != null) {
action.x = x;
action.rotation = rot;
candidates.add(action);
}
}
}
if (candidates.isEmpty()) return null;
// 选择评分最高的动作
candidates.sort((a, b) -> Double.compare(b.score, a.score));
return candidates.get(0);
}
/**
* 评估一个胶囊在特定位置的落点效果
*/
Action evaluateDrop(Capsule cap) {
// 模拟下落到最底部
int[][] positions = cap.getPositions();
int finalY = findDropPosition(positions[0][1], positions[0][0],
positions[1][1], positions[1][0]);
if (finalY < 0) return null; // 无法放置（游戏结束）
// 在模拟棋盘上放置胶囊
int[][] simBoard = cloneBoard();
int[][] finalPos = new int[][]{
{finalY, positions[0][1]},
{finalY + (positions[1][0] - positions[0][0]), positions[1][1]}
};
// 放置两个半胶囊
simBoard[finalPos[0][0]][finalPos[0][1]] = HALF_RED + cap.c1 - 1;
simBoard[finalPos[1][0]][finalPos[1][1]] = HALF_RED + cap.c2 - 1;
// 计算各项评分指标
Action result = new Action(cap.x, cap.horizontal ? 0 : 1);
// 1. 预测连锁消除
ChainResult chain = simulateChainElimination(simBoard);
result.chainDepth = chain.depth;
result.virusesCleared = chain.virusesCleared;
// 2. 计算综合评分
result.score = computeScore(simBoard, finalPos, chain);
return result;
}
/**
* 查找胶囊下落后的最终位置
*/
int findDropPosition(int x1, int y1, int x2, int y2) {
int dy = 0;
while (true) {
int ny1 = y1 + dy + 1;
int ny2 = y2 + dy + 1;
if (ny1 >= ROWS || ny2 >= ROWS) break;
if (board[ny1][x1] != EMPTY || board[ny2][x2] != EMPTY) break;
dy++;
}
return y1 + dy;
}
/**
* 模拟连锁消除过程
*/
ChainResult simulateChainElimination(int[][] simBoard) {
int depth = 0;
int totalViruses = 0;
boolean changed;
do {
changed = false;
boolean[][] toEliminate = new boolean[ROWS][COLS];
// 检测所有 4 连以上的同色区域
for (int y = 0; y < ROWS; y++) {
for (int x = 0; x < COLS; x++) {
if (simBoard[y][x] == EMPTY) continue;
int color = normalizeColor(simBoard[y][x]);
// 水平检测
int countH = 1;
for (int dx = 1; x + dx < COLS && normalizeColor(simBoard[y][x + dx]) == color; dx++) countH++;
for (int dx = 1; x - dx >= 0 && normalizeColor(simBoard[y][x - dx]) == color; dx++) countH++;
if (countH >= 4) {
for (int dx = 0; x + dx < COLS && normalizeColor(simBoard[y][x + dx]) == color; dx++) toEliminate[y][x + dx] = true;
for (int dx = 1; x - dx >= 0 && normalizeColor(simBoard[y][x - dx]) == color; dx++) toEliminate[y][x - dx] = true;
}
// 垂直检测
int countV = 1;
for (int dy = 1; y + dy < ROWS && normalizeColor(simBoard[y + dy][x]) == color; dy++) countV++;
for (int dy = 1; y - dy >= 0 && normalizeColor(simBoard[y - dy][x]) == color; dy++) countV++;
if (countV >= 4) {
for (int dy = 0; y + dy < ROWS && normalizeColor(simBoard[y + dy][x]) == color; dy++) toEliminate[y + dy][x] = true;
for (int dy = 1; y - dy >= 0 && normalizeColor(simBoard[y - dy][x]) == color; dy++) toEliminate[y - dy][x] = true;
}
}
}
// 统计消除的病毒数
for (int y = 0; y < ROWS; y++) {
for (int x = 0; x < COLS; x++) {
if (toEliminate[y][x]) {
if (isVirus(simBoard[y][x])) totalViruses++;
simBoard[y][x] = EMPTY;
changed = true;
}
}
}
// 重力下落：让上方胶囊落下
if (changed) {
applyGravity(simBoard);
depth++;
}
} while (changed);
return new ChainResult(depth, totalViruses);
}
/**
* 应用重力：让悬浮的胶囊下落
*/
void applyGravity(int[][] simBoard) {
for (int x = 0; x < COLS; x++) {
int writePos = ROWS - 1;
for (int y = ROWS - 1; y >= 0; y--) {
if (simBoard[y][x] != EMPTY) {
if (writePos != y) {
simBoard[writePos][x] = simBoard[y][x];
simBoard[y][x] = EMPTY;
}
writePos--;
}
}
}
}
/**
* 综合评分函数
*/
double computeScore(int[][] simBoard, int[][] placedPos, ChainResult chain) {
double score = 0;
// 1. 消除病毒得分（最重要）
score += chain.virusesCleared * 100;
// 2. 连锁深度加分
score += chain.depth * chain.depth * 50; // 连锁深度平方加分
// 3. 连通潜力：放置的胶囊与已有同色半胶囊相邻的数量
for (int[] pos : placedPos) {
int y = pos[0], x = pos[1];
int color = normalizeColor(simBoard[y][x]);
for (int d = 0; d < 4; d++) {
int nx = x + DX[d], ny = y + DY[d];
if (inBounds(ny, nx) && normalizeColor(simBoard[ny][nx]) == color) {
score += 10;
}
}
}
// 4. 高度惩罚：落点越高越危险
int maxHeight = Math.min(placedPos[0][0], placedPos[1][0]);
score -= maxHeight * 2;
// 5. 空洞惩罚：放置后下方是否有空隙
for (int[] pos : placedPos) {
int y = pos[0], x = pos[1];
for (int dy = y + 1; dy < ROWS; dy++) {
if (simBoard[dy][x] == EMPTY) {
score -= 15; // 下方有空洞，扣分
break;
}
}
}
// 6. 平整度奖励：同一行填满的格子越多越好
for (int y = 0; y < ROWS; y++) {
int filled = 0;
for (int x = 0; x < COLS; x++) {
if (simBoard[y][x] != EMPTY) filled++;
}
if (filled == COLS) score += 20; // 整行填满奖励
}
return score;
}
int normalizeColor(int cell) {
if (cell == EMPTY) return EMPTY;
if (cell == HALF_RED || cell == VIRUS_RED) return RED;
if (cell == HALF_YELLOW || cell == VIRUS_YELLOW) return YELLOW;
if (cell == HALF_BLUE || cell == VIRUS_BLUE) return BLUE;
return cell;
}
boolean isVirus(int cell) {
return cell == VIRUS_RED || cell == VIRUS_YELLOW || cell == VIRUS_BLUE;
}
boolean inBounds(int y, int x) {
return y >= 0 && y < ROWS && x >= 0 && x < COLS;
}
int[][] cloneBoard() {
int[][] clone = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
System.arraycopy(board[i], 0, clone[i], 0, COLS);
}
return clone;
}
static class ChainResult {
int depth;
int virusesCleared;
ChainResult(int d, int v) { depth = d; virusesCleared = v; }
}
// 主程序：演示 AI 决策
public static void main(String[] args) {
int[][] board = new int[ROWS][COLS];
// 初始化一些病毒
board[14][2] = VIRUS_RED;
board[14][3] = VIRUS_RED;
board[13][2] = VIRUS_YELLOW;
board[15][5] = VIRUS_BLUE;
board[14][5] = VIRUS_BLUE;
board[13][5] = VIRUS_BLUE;
// 放置一些已有胶囊
board[15][2] = HALF_RED;
board[15][3] = HALF_RED;
board[14][2] = VIRUS_RED; // 被覆盖，重新设置
board[14][3] = VIRUS_RED;
// 重新设置病毒（避免被覆盖）
board[14][2] = VIRUS_RED;
board[14][3] = VIRUS_RED;
board[13][2] = VIRUS_YELLOW;
board[15][5] = VIRUS_BLUE;
board[14][5] = VIRUS_BLUE;
board[13][5] = VIRUS_BLUE;
DrMarioAI ai = new DrMarioAI(board);
// AI 决策：当前下落的是红色-蓝色胶囊
Action best = ai.decideBestMove(board, RED, BLUE);
System.out.println("=== 马里奥医生 AI 决策结果 ===");
if (best != null) {
System.out.println("最佳动作：水平位置=" + best.x + ", 旋转=" + best.rotation);
System.out.println("预测连锁深度：" + best.chainDepth);
System.out.println("预测消除病毒数：" + best.virusesCleared);
System.out.println("综合评分：" + String.format("%.2f", best.score));
} else {
System.out.println("无可用动作，游戏结束！");
}
}
}
算法解析
贪心评估 vs 全局最优
马里奥医生的状态空间极其庞大（每步约 40 种动作，病毒分布千变万化），精确求解全局最优在计算上不可行。贪心评估策略在局部选择评分最高的落点，虽然不能保证全局最优，但在实际游戏中表现优异：
– 优先消除病毒，减少失败风险
– 追求连锁反应，获得高分
– 维持盘面平整，为后续操作留有余地
连锁预测的关键
连锁预测是 AI 的核心难点。我们的 simulateChainElimination 方法通过迭代消除+重力模拟准确预测连锁深度。关键在于：
1. 消除后要正确处理胶囊的拆分（一个胶囊的两个半部分可能分别属于不同消除组）
2. 重力下落时要保持胶囊的相对位置关系
3. 连锁评分采用平方加权（深度² × 50），鼓励 AI 追求高连锁而非浅层多次消除
评估函数的调参艺术
评估函数中各项权重的设置直接影响 AI 风格：
– 提高病毒消除权重 → AI 更保守，优先清盘
– 提高连锁深度权重 → AI 更激进，追求高分但风险更大
– 提高高度惩罚 → AI 更谨慎，避免堆叠过高
通过调整权重，可以训练出不同风格的 AI：速攻型、保守型、高分型。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 生成候选动作 | O(4 × COLS) = O(COLS) | O(COLS) |
| 单次落点模拟 | O(ROWS × COLS) | O(ROWS × COLS) |
| 连锁消除检测 | O(K × ROWS × COLS)，K 为连锁次数 | O(ROWS × COLS) |
| 完整决策 | O(COLS × K × ROWS × COLS) | O(ROWS × COLS) |
对于 16×8 的棋盘，单次决策约需评估 30-40 个落点，每个落点模拟 1-3 次连锁，总计算量在数万级别，现代 CPU 可在毫秒级完成。
扩展思路
- 蒙特卡洛树搜索（MCTS）：用 MCTS 替代贪心评估，考虑未来多步的期望收益
- 胶囊序列预测：根据已出现的胶囊序列，用马尔可夫链预测下一个胶囊颜色
- 深度学习评估：用 CNN 训练一个局面评估网络，替代手工设计的评分函数
总结
本文实现了一个完整的马里奥医生 AI，核心亮点在于：
– 多维度贪心评估：综合考虑消除、连锁、高度、空洞、平整度五个维度
– 精确连锁模拟：通过迭代消除+重力模拟准确预测连锁深度
– 物理下落模拟：正确处理胶囊重力下落和位置关系
读者可以从中学习到：贪心算法的评估函数设计、消除类游戏的连锁检测机制、以及游戏 AI 的决策框架。
