引言
数字合并是一类经典的滑动益智游戏：玩家在网格上滑动数字方块，相同数字碰撞时合并为它们的和，目标是生成尽可能大的数字或填满特定目标值。本文用Java实现一个通用的数字合并引擎，重点讲解网格状态转移、滑动合并算法、空位生成策略以及基于蒙特卡洛模拟的启发式AI决策。
核心机制
游戏在 N × N 网格上进行，每次滑动（上/下/左/右）使所有方块向该方向移动并合并：
1. 移动：非零方块向滑动方向靠拢，中间不留空位。
2. 合并：相邻且值相同的方块碰撞时合并，得分增加合并后的值。每步中每个方块仅参与一次合并。
3. 生成：每次有效滑动后，在随机空位以给定概率生成新方块（通常为2或4）。
滑动合并算法
以向左滑动为例，对每一行执行：
1. 压缩：将非零元素左移，去除中间空位。
2. 合并：从左到右扫描，若相邻两元素相等则合并，右置零。
3. 再压缩：将合并产生的零位移除。
// 单行向左滑动示例
int[] line = {2, 0, 2, 4};
// 压缩: [2, 2, 4, 0]
// 合并: [4, 0, 4, 0]
// 再压缩: [4, 4, 0, 0]
Java实现
import java.util.*;
/**
* 数字合并游戏引擎：滑动、合并、AI决策
*/
public class NumberMergeGame {
private int size;
private int[][] board;
private Random random;
private int score;
private boolean moved; // 标记本轮是否发生移动
public NumberMergeGame(int size) {
this.size = size;
this.board = new int[size][size];
this.random = new Random();
this.score = 0;
spawnTile();
spawnTile();
}
/**
* 执行滑动操作
* @param direction 0=左, 1=上, 2=右, 3=下
* @return 是否成功移动
*/
public boolean move(int direction) {
moved = false;
// 根据方向选择遍历策略
switch (direction) {
case 0: // 左
for (int r = 0; r < size; r++) board[r] = slideAndMerge(board[r]);
break;
case 1: // 上
for (int c = 0; c < size; c++) {
int[] col = extractColumn(c);
col = slideAndMerge(col);
setColumn(c, col);
}
break;
case 2: // 右
for (int r = 0; r < size; r++) {
int[] reversed = reverse(board[r]);
reversed = slideAndMerge(reversed);
board[r] = reverse(reversed);
}
break;
case 3: // 下
for (int c = 0; c < size; c++) {
int[] col = extractColumn(c);
col = reverse(col);
col = slideAndMerge(col);
col = reverse(col);
setColumn(c, col);
}
break;
}
if (moved) {
spawnTile();
return true;
}
return false;
}
/**
* 单行/列的滑动与合并
*/
private int[] slideAndMerge(int[] line) {
int[] filtered = Arrays.stream(line).filter(v -> v != 0).toArray();
int[] merged = new int[filtered.length];
int idx = 0;
for (int i = 0; i < filtered.length; i++) {
if (i + 1 < filtered.length && filtered[i] == filtered[i + 1]) {
merged[idx++] = filtered[i] * 2;
score += filtered[i] * 2;
i++; // 跳过下一个已合并元素
moved = true;
} else {
merged[idx++] = filtered[i];
}
}
// 检测是否发生位置变化
int[] result = new int[size];
for (int i = 0; i < idx; i++) result[i] = merged[i];
for (int i = 0; i < size; i++) {
if (result[i] != line[i]) moved = true;
}
return result;
}
private int[] extractColumn(int c) {
int[] col = new int[size];
for (int r = 0; r < size; r++) col[r] = board[r][c];
return col;
}
private void setColumn(int c, int[] col) {
for (int r = 0; r < size; r++) board[r][c] = col[r];
}
private int[] reverse(int[] arr) {
int[] rev = new int[arr.length];
for (int i = 0; i < arr.length; i++) rev[i] = arr[arr.length - 1 - i];
return rev;
}
/**
* 在随机空位生成新方块（90%概率为2，10%概率为4）
*/
private void spawnTile() {
List<int[]> empty = new ArrayList<>();
for (int r = 0; r < size; r++)
for (int c = 0; c < size; c++)
if (board[r][c] == 0) empty.add(new int[]{r, c});
if (empty.isEmpty()) return;
int[] pos = empty.get(random.nextInt(empty.size()));
board[pos[0]][pos[1]] = random.nextDouble() < 0.9 ? 2 : 4;
}
/**
* 启发式评估函数：综合空位数、单调性、平滑度、最大值位置
*/
public double evaluate() {
int empty = countEmpty();
double smoothness = calculateSmoothness();
double monotonicity = calculateMonotonicity();
double maxCorner = maxInCorner();
return empty * 100 + smoothness * 10 + monotonicity * 50 + maxCorner * 1000;
}
private int countEmpty() {
int count = 0;
for (int[] row : board)
for (int v : row)
if (v == 0) count++;
return count;
}
private double calculateSmoothness() {
double smooth = 0;
for (int r = 0; r < size; r++) {
for (int c = 0; c < size - 1; c++) {
smooth -= Math.abs(board[r][c] - board[r][c + 1]);
}
}
for (int c = 0; c < size; c++) {
for (int r = 0; r < size - 1; r++) {
smooth -= Math.abs(board[r][c] - board[r + 1][c]);
}
}
return smooth;
}
private double calculateMonotonicity() {
// 优先保持行/列单调递减（大数在一角）
double mono = 0;
for (int r = 0; r < size; r++) {
for (int c = 0; c < size - 1; c++) {
if (board[r][c] >= board[r][c + 1]) mono++;
}
}
return mono;
}
private double maxInCorner() {
int max = 0;
for (int[] row : board)
for (int v : row)
max = Math.max(max, v);
if (board[0][0] == max || board[0][size-1] == max
|| board[size-1][0] == max || board[size-1][size-1] == max)
return 1;
return 0;
}
/**
* 蒙特卡洛模拟：对每个合法移动模拟若干随机对局，选平均分最高的
*/
public int monteCarloMove(int simulations) {
double[] scores = new double[4];
for (int dir = 0; dir < 4; dir++) {
int[][] backup = copyBoard();
if (!move(dir)) {
board = backup;
scores[dir] = Double.NEGATIVE_INFINITY;
continue;
}
double total = evaluate();
for (int sim = 0; sim < simulations; sim++) {
total += randomPlayout();
board = copyBoard(); // 恢复状态
}
scores[dir] = total / (simulations + 1);
board = backup;
}
int bestDir = 0;
for (int i = 1; i < 4; i++)
if (scores[i] > scores[bestDir]) bestDir = i;
return bestDir;
}
/**
* 随机对局直到结束，返回最终得分
*/
private double randomPlayout() {
int steps = 0;
while (steps < 50) {
List<Integer> valid = new ArrayList<>();
for (int d = 0; d < 4; d++) {
int[][] backup = copyBoard();
if (move(d)) valid.add(d);
board = backup;
}
if (valid.isEmpty()) break;
move(valid.get(random.nextInt(valid.size())));
steps++;
}
return evaluate();
}
private int[][] copyBoard() {
int[][] copy = new int[size][size];
for (int r = 0; r < size; r++)
System.arraycopy(board[r], 0, copy[r], 0, size);
return copy;
}
public boolean canMove() {
for (int d = 0; d < 4; d++) {
int[][] backup = copyBoard();
boolean ok = move(d);
board = backup;
if (ok) return true;
}
return false;
}
public void printBoard() {
System.out.println("Score: " + score);
for (int[] row : board) {
for (int v : row) {
System.out.printf("%6d", v);
}
System.out.println();
}
}
public static void main(String[] args) {
NumberMergeGame game = new NumberMergeGame(4);
while (game.canMove()) {
game.printBoard();
int dir = game.monteCarloMove(20);
String[] names = {"左", "上", "右", "下"};
System.out.println("AI选择: " + names[dir]);
game.move(dir);
System.out.println();
}
game.printBoard();
System.out.println("游戏结束！");
}
}
启发式评估详解
数字合并的AI性能高度依赖评估函数。上述实现采用四因子加权：
1. 空位数：保留更多操作空间，权重最高。
2. 平滑度：相邻格子差值越小越好，利于未来合并。
3. 单调性：行/列呈单调递减，使大数向角落聚集。
4. 最大值在角落：防止大数被锁死在中部。
蒙特卡洛模拟在此基础上进行短局 rollout，对随机生成的不确定性进行统计平均，显著提升决策稳定性。
扩展方向
- ** 期望Minimax**：将随机生成建模为期望值节点，构建深度为3-4的博弈树。
- ** 神经网络评估**：用TD-Learning训练浅层网络替代手工评估函数。
- ** 变体规则**：支持三向合并、障碍格、目标值挑战等扩展模式。
