噗哟噗哟（Puyo Puyo）是由日本 Compile 公司开发的经典下落式消除游戏，两个（或更多）同颜色的噗哟相连达到 4 个及以上即可消除，消除后上方的噗哟下落可能引发连锁反应（Chain），连锁次数越多得分越高。与同类消除游戏相比，噗哟噗哟的核心策略在于主动构建连锁结构而非被动消除，这要求 AI 具备前瞻性的布局评估能力。本文将用 Java 实现噗哟噗哟的核心算法，重点讲解连通块检测、连锁模拟以及基于贪心启发式的最优落子策略。
一、游戏规则与数据表示
1.1 棋盘与噗哟
标准噗哟噗哟棋盘为 6 列 × 12 行的网格（实际显示 6×13，最上方一行用于生成新噗哟）。每回合从顶部落下一对噗哟（称为 Tsu），玩家可以水平移动和旋转，决定落点。
1.2 消除规则
- 同色噗哟在上下左右四个方向相连（4-连通），数量 ≥ 4 时消除
- 消除后上方噗哟下落填补空缺
- 下落后的噗哟若再次形成 ≥4 的连通块，则引发连锁
- 连锁次数越多，单次消除得分越高（指数增长）
1.3 状态表示
// 棋盘：0=空, 1=红, 2=绿, 3=蓝, 4=黄, 5=紫
int[][] board = new int[ROWS][COLS];
// 当前下落的噗哟对：{颜色A, 颜色B, 列位置, 旋转状态}
二、核心算法
2.1 连通块检测（Flood Fill）
使用 BFS/DFS 找出同色连通的区域，统计每个连通块的大小。这是消除判定的基础。
2.2 连锁模拟（Cascade Simulation）
落子后需要模拟完整的消除-下落-再消除过程，直到棋盘稳定。算法流程：
1. 扫描所有连通块，标记大小 ≥4 的块
2. 消除标记的噗哟，计算得分
3. 每列上方的噗哟下落填补空缺
4. 重复步骤 1-3，连锁次数 +1
5. 直到没有可消除的连通块
2.3 布局评估函数
评估函数是 AI 决策的核心，综合考虑以下因素：
– 连锁潜力：预测最多能触发几层连锁
– 颜色分离度：同色噗哟聚集在一起有利于形成大连通块
– 高度均衡：各列高度应尽量均匀，避免”高塔”
– 危险列：高度接近顶部的列需要优先消除
– 连接数：同色相邻的噗哟对数
综合评分公式：
score = chainPower * 1000 + colorClusters * 50 - heightVariance * 30
- maxHeight * 20 + connections * 10
2.4 贪心最优落子搜索
对于当前下落的噗哟对，枚举所有合法落点（约 22 种：6 列 × 4 种旋转 – 边界非法情况），对每种落子后的棋盘状态进行连锁模拟和评估，选择得分最高的落点。
三、Java 实现
import java.util.*;
/**
* 噗哟噗哟（Puyo Puyo）AI 实现
* 核心算法：Flood Fill连通检测、连锁模拟、贪心启发式评估
*/
public class PuyoPuyoAI {
private static final int ROWS = 12;
private static final int COLS = 6;
private static final int EMPTY = 0;
private static final int MIN_CHAIN = 4; // 消除阈值
private static final int[] COLORS = {1, 2, 3, 4}; // 红绿蓝黄
private int[][] board;
private Random random;
public PuyoPuyoAI() {
this.board = new int[ROWS][COLS];
this.random = new Random();
}
/**
* 获取指定列的当前高度（从底部数）
*/
public int getColumnHeight(int col) {
for (int row = 0; row < ROWS; row++) {
if (board[row][col] != EMPTY) {
return ROWS - row;
}
}
return 0;
}
/**
* 在指定列的顶部放置一个噗哟
*/
public boolean placePuyo(int col, int color) {
if (col < 0 || col >= COLS || color == EMPTY) return false;
if (getColumnHeight(col) >= ROWS) return false;
int row = ROWS - 1 - getColumnHeight(col);
board[row][col] = color;
return true;
}
/**
* 使用Flood Fill找出所有连通块
* @return 每个连通块的{颜色, 位置列表}列表
*/
public List<List<int[]>> findConnectedGroups() {
boolean[][] visited = new boolean[ROWS][COLS];
List<List<int[]>> groups = new ArrayList<>();
int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == EMPTY || visited[r][c]) continue;
int color = board[r][c];
List<int[]> group = new ArrayList<>();
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{r, c});
visited[r][c] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
group.add(cur);
for (int[] d : dirs) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS
&& !visited[nr][nc] && board[nr][nc] == color) {
visited[nr][nc] = true;
queue.add(new int[]{nr, nc});
}
}
}
groups.add(group);
}
}
return groups;
}
/**
* 执行一步消除-下落操作
* @return 消除的噗哟数量，0表示无消除
*/
public int stepEliminate() {
List<List<int[]>> groups = findConnectedGroups();
boolean[][] toRemove = new boolean[ROWS][COLS];
int eliminated = 0;
for (List<int[]> group : groups) {
if (group.size() >= MIN_CHAIN) {
for (int[] pos : group) {
toRemove[pos[0]][pos[1]] = true;
eliminated++;
}
}
}
if (eliminated == 0) return 0;
// 消除标记的噗哟
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (toRemove[r][c]) {
board[r][c] = EMPTY;
}
}
}
// 下落填补
applyGravity();
return eliminated;
}
/**
* 应用重力：每列上方的噗哟下落
*/
public void applyGravity() {
for (int c = 0; c < COLS; c++) {
int writeRow = ROWS - 1;
for (int r = ROWS - 1; r >= 0; r--) {
if (board[r][c] != EMPTY) {
board[writeRow][c] = board[r][c];
if (writeRow != r) {
board[r][c] = EMPTY;
}
writeRow--;
}
}
// 清空剩余位置
for (int r = writeRow; r >= 0; r--) {
board[r][c] = EMPTY;
}
}
}
/**
* 模拟完整的连锁消除过程
* @return {总消除数, 连锁次数}
*/
public int[] simulateChain() {
int totalEliminated = 0;
int chainCount = 0;
while (true) {
int eliminated = stepEliminate();
if (eliminated == 0) break;
totalEliminated += eliminated;
chainCount++;
}
return new int[]{totalEliminated, chainCount};
}
/**
* 局面评估函数
*/
public int evaluateBoard() {
int score = 0;
// 1. 最大高度惩罚（越高越危险）
int maxHeight = 0;
int[] heights = new int[COLS];
for (int c = 0; c < COLS; c++) {
heights[c] = getColumnHeight(c);
maxHeight = Math.max(maxHeight, heights[c]);
}
score -= maxHeight * 50;
// 2. 高度方差惩罚（不均衡不利）
double avgHeight = Arrays.stream(heights).average().orElse(0);
double variance = 0;
for (int h : heights) variance += (h - avgHeight) * (h - avgHeight);
score -= (int)(variance * 5);
// 3. 同色连接奖励（相邻同色越多越容易消除）
int connections = 0;
int[][] dirs = {{0,1}, {1,0}}; // 右、下（避免重复计数）
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == EMPTY) continue;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < ROWS && nc < COLS && board[nr][nc] == board[r][c]) {
connections++;
}
}
}
}
score += connections * 30;
// 4. 连通块大小奖励（接近4的连通块最有价值）
List<List<int[]>> groups = findConnectedGroups();
for (List<int[]> group : groups) {
int size = group.size();
if (size == 3) score += 80; // 差一点消除
else if (size == 2) score += 20; // 有潜力
else if (size >= 4) score += 200; // 已可消除
}
// 5. 底部填充奖励（底部有更多棋子更稳定）
int bottomFill = 0;
for (int c = 0; c < COLS; c++) {
for (int r = ROWS - 1; r >= ROWS - 3 && r >= 0; r--) {
if (board[r][c] != EMPTY) bottomFill++;
}
}
score += bottomFill * 10;
return score;
}
/**
* 获取噗哟对的所有合法落点
* @param color1 主噗哟颜色
* @param color2 副噗哟颜色
* @return 所有可能的落子后棋盘状态及落子信息
*/
public List<MoveResult> getLegalMoves(int color1, int color2) {
List<MoveResult> results = new ArrayList<>();
// 旋转状态：0=竖直(上), 1=水平(右), 2=竖直(下), 3=水平(左)
int[][] offsets = {{-1,0}, {0,1}, {1,0}, {0,-1}};
for (int col = 0; col < COLS; col++) {
for (int rot = 0; rot < 4; rot++) {
int r1 = ROWS - 1 - getColumnHeight(col);
int c1 = col;
int r2 = r1 + offsets[rot][0];
int c2 = c1 + offsets[rot][1];
// 边界检查
if (c2 < 0 || c2 >= COLS || r2 < 0 || r2 >= ROWS) continue;
if (getColumnHeight(c2) >= ROWS - (r2 < r1 ? 1 : 0)) continue;
// 保存当前状态
int[][] saved = deepCopy(board);
// 执行落子（副噗哟先放还是主噗哟先放取决于旋转方向）
if (offsets[rot][0] > 0 || offsets[rot][1] != 0) {
// 副噗哟在主噗哟下方/右方，先放副噗哟
if (r2 > r1 || (r2 == r1 && c2 > c1)) {
placePuyo(c2, color2);
placePuyo(c1, color1);
} else {
placePuyo(c1, color1);
placePuyo(c2, color2);
}
} else {
placePuyo(c1, color1);
placePuyo(c2, color2);
}
// 模拟连锁
int[] chainResult = simulateChain();
int eval = evaluateBoard();
// 连锁有额外奖励
eval += chainResult[1] * 1000 + chainResult[0] * 50;
results.add(new MoveResult(col, rot, eval, chainResult[1],
deepCopy(board)));
// 恢复状态
board = saved;
}
}
return results;
}
/**
* AI 寻找最佳落子
*/
public MoveResult findBestMove(int color1, int color2) {
List<MoveResult> moves = getLegalMoves(color1, color2);
if (moves.isEmpty()) return null;
MoveResult best = moves.get(0);
for (MoveResult move : moves) {
if (move.evaluation > best.evaluation) {
best = move;
}
}
return best;
}
private int[][] deepCopy(int[][] src) {
int[][] dst = new int[src.length][];
for (int i = 0; i < src.length; i++) {
dst[i] = src[i].clone();
}
return dst;
}
/**
* 打印棋盘（旋转90度显示，底部在下方）
*/
public void printBoard() {
String[] colorChars = {".", "R", "G", "B", "Y", "P"};
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
System.out.print(colorChars[board[r][c]] + " ");
}
System.out.println();
}
System.out.println("-------------");
}
/**
* 落子结果类
*/
static class MoveResult {
int column, rotation, evaluation, chainCount;
int[][] resultingBoard;
MoveResult(int col, int rot, int eval, int chain, int[][] board) {
this.column = col;
this.rotation = rot;
this.evaluation = eval;
this.chainCount = chain;
this.resultingBoard = board;
}
@Override
public String toString() {
return String.format("Col=%d, Rot=%d, Eval=%d, Chain=%d",
column, rotation, evaluation, chainCount);
}
}
public static void main(String[] args) {
PuyoPuyoAI game = new PuyoPuyoAI();
// 预设一些棋子用于测试
game.placePuyo(0, 1);
game.placePuyo(0, 1);
game.placePuyo(0, 1);
game.placePuyo(1, 1);
game.placePuyo(1, 2);
game.placePuyo(1, 2);
game.placePuyo(1, 2);
game.placePuyo(2, 3);
game.placePuyo(2, 3);
game.placePuyo(2, 3);
System.out.println("Initial board:");
game.printBoard();
// AI 决策：当前下落噗哟对为 {红, 绿}
MoveResult best = game.findBestMove(1, 2);
if (best != null) {
System.out.println("Best move: " + best);
game.board = best.resultingBoard;
System.out.println("After move:");
game.printBoard();
}
}
}
四、算法复杂度分析
| 模块 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 连通块检测 | O(ROWS×COLS) | O(ROWS×COLS) | BFS遍历整个棋盘 |
| 单次消除 | O(ROWS×COLS) | O(ROWS×COLS) | 含下落操作 |
| 连锁模拟 | O(k×ROWS×COLS) | O(ROWS×COLS) | k 为连锁层数，通常 k ≤ 10 |
| 局面评估 | O(ROWS×COLS) | O(1) | 多轮线性扫描 |
| 合法落子枚举 | O(m×k×ROWS×COLS) | O(m×ROWS×COLS) | m 为合法落子数（约 20） |
在 6×12 的棋盘上，单次 AI 决策的总计算量约为 20 × 10 × 72 = 14400 次操作，现代 CPU 可在微秒级完成。
五、总结
噗哟噗哟的 AI 设计核心在于连锁预判与布局结构评估。不同于简单的”消除越多越好”，高质量的 AI 会主动构建”阶梯状”或”交叉状”的结构，使得一次消除能够引发多层连锁。本文实现的贪心启发式评估综合考虑了高度控制、颜色聚集和连通潜力，能够在实际对局中做出具有战略眼光的决策。读者可以进一步探索蒙特卡洛树搜索（MCTS）或多步前瞻（Lookahead）来提升 AI 的连锁构建能力。
