2048是一款经典的数字益智游戏，玩家通过上下左右滑动方块，使相同数字碰撞合并，最终目标是合成2048甚至更高的数字。由于每次移动后新方块会在随机空位生成2或4，游戏中存在”玩家决策”与”随机生成”两种交替进行的节点，这为算法设计带来了独特的挑战。本文将用Java实现一个带AI的2048游戏，核心采用Expectimax博弈树搜索处理随机性，配合多维度启发式评估函数进行状态评分，包含完整的游戏引擎与AI决策模块。
一、Expectimax算法原理
Expectimax是Minimax算法的扩展，专门适用于存在随机因素的对弈或决策场景。在2048中，游戏树包含两类节点：
- Max节点（玩家回合）：玩家选择上下左右四个方向中评分最高的动作，取子节点评估值的最大值。
- Chance节点（随机回合）：系统在随机空位生成2（概率90%）或4（概率10%），对所有可能的结果取期望值。
搜索深度通常受限于计算资源，实际应用中可通过迭代加深或设置时间上限来控制。Expectimax的递归公式如下：
$$
V(s) = \begin{cases}
\text{evaluate}(s) & \text{if } \text{depth} = 0 \text{ or terminal} \
\max_{a \in \text{actions}} V(s_a) & \text{if Max node} \
\sum_{r \in \text{random outcomes}} P(r) \cdot V(s_r) & \text{if Chance node}
\
\end{cases}
$$
二、多维度启发式评估函数
由于2048的搜索空间巨大，搜索深度受限时评估函数的质量直接决定AI水平。我们设计一个融合多个维度的线性加权评估函数：
| 评估维度 | 说明 | 权重方向 |
|---|---|---|
| 单调性（Monotonicity） | 鼓励行列呈单调递增或递减趋势，便于高数值聚集 | 正向 |
| 平滑性（Smoothness） | 相邻格子差值越小越好，减少”孤岛” | 正向 |
| 空格数（Empty Tiles） | 保留更多操作空间，避免死局 | 正向 |
| 最大值位置（Max Tile Position） | 将最大数字固定在角落，利于后续合并 | 正向 |
| 合并潜力（Merge Potential） | 统计相邻相等数字对，评估近期合并机会 | 正向 |
各维度加权求和后得到状态评分，引导AI向”角落聚集、平滑过渡、保留空格”的理想格局发展。
三、核心数据结构
游戏板使用4×4的二维整数数组表示，0代表空格。状态类封装棋盘与当前得分：
public class Board {
public static final int SIZE = 4;
private int[][] grid;
private int score;
public Board() {
grid = new int[SIZE][SIZE];
score = 0;
}
public Board(int[][] grid, int score) {
this.grid = new int[SIZE][SIZE];
for (int i = 0; i < SIZE; i++) {
System.arraycopy(grid[i], 0, this.grid[i], 0, SIZE);
}
this.score = score;
}
public int[][] getGrid() { return grid; }
public int getScore() { return score; }
public void setScore(int score) { this.score = score; }
/** 获取所有空格坐标 */
public List<int[]> getEmptyCells() {
List<int[]> cells = new ArrayList<>();
for (int r = 0; r < SIZE; r++) {
for (int c = 0; c < SIZE; c++) {
if (grid[r][c] == 0) cells.add(new int[]{r, c});
}
}
return cells;
}
/** 在指定位置插入数字 */
public void insertTile(int row, int col, int value) {
grid[row][col] = value;
}
/** 获取最大值 */
public int getMaxTile() {
int max = 0;
for (int[] row : grid) {
for (int v : row) max = Math.max(max, v);
}
return max;
}
/** 深拷贝 */
public Board copy() {
return new Board(grid, score);
}
}
四、游戏引擎：移动与合并逻辑
移动操作需要处理滑动、合并和计分。以向左移动为例，对每一行执行”压缩-合并-压缩”三步：
public class GameEngine {
public static final int UP = 0, DOWN = 1, LEFT = 2, RIGHT = 3;
/** 执行指定方向的移动，返回是否发生变化 */
public static boolean move(Board board, int direction) {
int[][] g = board.getGrid();
boolean moved = false;
int newScore = board.getScore();
// 统一通过旋转矩阵简化四个方向的处理
int rotations = direction == UP ? 3 : direction == DOWN ? 1 : direction == RIGHT ? 2 : 0;
int[][] working = rotate(g, rotations);
for (int r = 0; r < Board.SIZE; r++) {
int[] result = processLine(working[r]);
if (!Arrays.equals(working[r], result)) moved = true;
working[r] = result;
// 累加合并得分
for (int i = 0; i < Board.SIZE - 1; i++) {
if (result[i] != 0 && result[i] == result[i + 1]) {
newScore += result[i] * 2;
}
}
}
int[][] restored = rotate(working, (4 - rotations) % 4);
for (int i = 0; i < Board.SIZE; i++) {
System.arraycopy(restored[i], 0, g[i], 0, Board.SIZE);
}
board.setScore(newScore);
return moved;
}
/** 处理单行：压缩零值、合并相邻相等元素、再次压缩 */
private static int[] processLine(int[] line) {
int[] temp = new int[Board.SIZE];
int idx = 0;
for (int v : line) {
if (v != 0) temp[idx++] = v;
}
int[] result = new int[Board.SIZE];
idx = 0;
for (int i = 0; i < Board.SIZE; i++) {
if (temp[i] == 0) break;
if (i + 1 < Board.SIZE && temp[i] == temp[i + 1]) {
result[idx++] = temp[i] * 2;
i++; // 跳过已被合并的元素
} else {
result[idx++] = temp[i];
}
}
return result;
}
/** 矩阵顺时针旋转n次 */
private static int[][] rotate(int[][] matrix, int times) {
int[][] result = new int[Board.SIZE][Board.SIZE];
for (int i = 0; i < Board.SIZE; i++) {
System.arraycopy(matrix[i], 0, result[i], 0, Board.SIZE);
}
for (int t = 0; t < times; t++) {
int[][] next = new int[Board.SIZE][Board.SIZE];
for (int r = 0; r < Board.SIZE; r++) {
for (int c = 0; c < Board.SIZE; c++) {
next[c][Board.SIZE - 1 - r] = result[r][c];
}
}
result = next;
}
return result;
}
/** 随机在空格生成新方块（90%概率为2，10%为4） */
public static void spawnTile(Board board) {
List<int[]> empty = board.getEmptyCells();
if (empty.isEmpty()) return;
int[] cell = empty.get((int)(Math.random() * empty.size()));
int value = Math.random() < 0.9 ? 2 : 4;
board.insertTile(cell[0], cell[1], value);
}
/** 检查是否还能移动 */
public static boolean canMove(Board board) {
int[][] g = board.getGrid();
for (int r = 0; r < Board.SIZE; r++) {
for (int c = 0; c < Board.SIZE; c++) {
if (g[r][c] == 0) return true;
if (c + 1 < Board.SIZE && g[r][c] == g[r][c + 1]) return true;
if (r + 1 < Board.SIZE && g[r][c] == g[r + 1][c]) return true;
}
}
return false;
}
}
五、Expectimax AI决策引擎
AI引擎的核心是递归搜索与状态评估。由于Chance节点的分支因子等于空格数（最多16个），直接搜索深度有限。我们采用”一次生成一个随机方块”的简化模型（每次Chance节点只考虑在一个随机位置生成2或4），将分支控制在合理范围：
public class ExpectimaxAI {
// 各评估维度权重，通过大量对局调优
private static final double WEIGHT_MONOTONICITY = 47.0;
private static final double WEIGHT_SMOOTHNESS = 11.0;
private static final double WEIGHT_EMPTY = 270.0;
private static final double WEIGHT_MAX_CORNER = 100.0;
private static final double WEIGHT_MERGE = 70.0;
private int maxDepth;
public ExpectimaxAI(int maxDepth) {
this.maxDepth = maxDepth;
}
/** 为当前局面选择最优动作 */
public int findBestMove(Board board) {
int bestMove = -1;
double bestValue = Double.NEGATIVE_INFINITY;
for (int dir = 0; dir < 4; dir++) {
Board next = board.copy();
if (!GameEngine.move(next, dir)) continue; // 非法移动
double value = expectimax(next, maxDepth - 1, false);
if (value > bestValue) {
bestValue = value;
bestMove = dir;
}
}
return bestMove;
}
/** Expectimax递归搜索
* @param board 当前棋盘
* @param depth 剩余深度
* @param isMax true表示玩家回合(Max节点)，false表示随机回合(Chance节点)
*/
private double expectimax(Board board, int depth, boolean isMax) {
if (depth == 0 || !GameEngine.canMove(board)) {
return evaluate(board);
}
if (isMax) {
// Max节点：玩家选择最佳动作
double maxValue = Double.NEGATIVE_INFINITY;
for (int dir = 0; dir < 4; dir++) {
Board next = board.copy();
if (!GameEngine.move(next, dir)) continue;
double value = expectimax(next, depth - 1, false);
maxValue = Math.max(maxValue, value);
}
return maxValue == Double.NEGATIVE_INFINITY ? evaluate(board) : maxValue;
} else {
// Chance节点：随机生成方块，取期望值
List<int[]> empty = board.getEmptyCells();
if (empty.isEmpty()) return evaluate(board);
double totalValue = 0.0;
int count = 0;
// 为提高效率，只采样部分空格（如全部采样会导致分支爆炸）
int sampleSize = Math.min(empty.size(), 8);
for (int i = 0; i < sampleSize; i++) {
int[] cell = empty.get(i);
// 90%概率生成2
Board with2 = board.copy();
with2.insertTile(cell[0], cell[1], 2);
totalValue += 0.9 * expectimax(with2, depth - 1, true);
// 10%概率生成4
Board with4 = board.copy();
with4.insertTile(cell[0], cell[1], 4);
totalValue += 0.1 * expectimax(with4, depth - 1, true);
count++;
}
return totalValue / count;
}
}
/** 多维度启发式评估函数 */
public static double evaluate(Board board) {
int[][] g = board.getGrid();
double score = 0.0;
// 1. 空格数评估
int emptyCount = board.getEmptyCells().size();
score += WEIGHT_EMPTY * emptyCount;
// 2. 单调性评估（四个方向的单调性取最大值）
double[] monoScores = new double[4];
// 从左到右、从右到左
for (int r = 0; r < Board.SIZE; r++) {
for (int c = 0; c < Board.SIZE - 1; c++) {
if (g[r][c] > g[r][c + 1]) monoScores[0] += g[r][c] - g[r][c + 1];
else monoScores[1] += g[r][c + 1] - g[r][c];
}
}
// 从上到下、从下到上
for (int c = 0; c < Board.SIZE; c++) {
for (int r = 0; r < Board.SIZE - 1; r++) {
if (g[r][c] > g[r + 1][c]) monoScores[2] += g[r][c] - g[r + 1][c];
else monoScores[3] += g[r + 1][c] - g[r][c];
}
}
double mono = Math.max(
Math.max(monoScores[0], monoScores[1]),
Math.max(monoScores[2], monoScores[3])
);
score -= WEIGHT_MONOTONICITY * mono;
// 3. 平滑性评估
double smooth = 0.0;
for (int r = 0; r < Board.SIZE; r++) {
for (int c = 0; c < Board.SIZE; c++) {
if (r + 1 < Board.SIZE) {
smooth -= Math.abs(g[r][c] - g[r + 1][c]);
}
if (c + 1 < Board.SIZE) {
smooth -= Math.abs(g[r][c] - g[r][c + 1]);
}
}
}
score += WEIGHT_SMOOTHNESS * smooth;
// 4. 最大值位于角落的奖励
int maxTile = board.getMaxTile();
boolean inCorner = (g[0][0] == maxTile || g[0][Board.SIZE - 1] == maxTile
|| g[Board.SIZE - 1][0] == maxTile || g[Board.SIZE - 1][Board.SIZE - 1] == maxTile);
if (inCorner) score += WEIGHT_MAX_CORNER * maxTile;
// 5. 合并潜力评估
int mergePotential = 0;
for (int r = 0; r < Board.SIZE; r++) {
for (int c = 0; c < Board.SIZE; c++) {
if (g[r][c] == 0) continue;
if (c + 1 < Board.SIZE && g[r][c] == g[r][c + 1]) mergePotential += g[r][c];
if (r + 1 < Board.SIZE && g[r][c] == g[r + 1][c]) mergePotential += g[r][c];
}
}
score += WEIGHT_MERGE * mergePotential;
return score;
}
}
六、主程序与自动对局
以下主程序启动一个AI自动运行的2048游戏，每步通过Expectimax搜索决策，控制台输出棋盘变化：
public class Game2048 {
public static void main(String[] args) {
Board board = new Board();
GameEngine.spawnTile(board);
GameEngine.spawnTile(board);
ExpectimaxAI ai = new ExpectimaxAI(4); // 搜索深度4，平衡性能与效果
System.out.println("=== 2048 AI 自动对局 ===");
printBoard(board);
int moves = 0;
while (GameEngine.canMove(board)) {
int move = ai.findBestMove(board);
if (move == -1) break; // 无合法移动
GameEngine.move(board, move);
GameEngine.spawnTile(board);
moves++;
String[] dirNames = {"上", "下", "左", "右"};
System.out.println("\n第" + moves + "步: " + dirNames[move] + " (得分: " + board.getScore() + ")");
printBoard(board);
}
System.out.println("\n=== 游戏结束 ===");
System.out.println("总步数: " + moves);
System.out.println("最终得分: " + board.getScore());
System.out.println("最大方块: " + board.getMaxTile());
}
private static void printBoard(Board board) {
int[][] g = board.getGrid();
for (int[] row : g) {
for (int v : row) {
System.out.printf("%6d", v);
}
System.out.println();
}
}
}
七、复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | $O(b^m \cdot c)$ | $b$为玩家分支因子(≤4)，$m$为搜索深度，$c$为Chance节点采样数 |
| 空间复杂度 | $O(m)$ | 递归栈深度等于搜索深度 |
| 评估函数 | $O(1)$ | 棋盘固定为4×4，评估为常数时间 |
实际运行中，深度4的Expectimax配合8个空格采样，每次决策约需评估数万个节点，在现代CPU上可在100ms内完成。如需提升性能，可采用迭代加深配合置换表（Transposition Table）缓存已评估状态，或引入多线程并行扩展Chance节点。
八、总结
本文用Java完整实现了2048游戏的AI决策系统，核心亮点包括：
- Expectimax搜索：精准建模2048中”玩家决策-随机生成”的交替过程，通过Max节点取最优、Chance节点取期望的方式推导理论最优策略。
- 多维度启发式评估：融合单调性、平滑性、空格数、角落最大化和合并潜力五个维度，引导AI形成”角落聚集、平滑过渡”的高分布局。
- 可扩展架构：Board、GameEngine、ExpectimaxAI三层分离，便于后续引入置换表、迭代加深、神经网络评估等进阶优化。
Expectimax作为处理随机决策问题的经典算法，不仅适用于2048，也可推广到麻将、扑克等含隐藏信息与随机性的博弈场景。读者可尝试调整评估权重、增加搜索深度或引入蒙特卡洛采样，进一步挖掘AI的得分上限。
