每日算法 — 使用java实现2048：A*搜索与单调性启发式评估

可莉爸爸 AI算法

引言

2048是一款由Gabriele Cirulli在2014年发布的数字滑块游戏，玩家通过上下左右滑动方块，使相同数字的方块合并，最终目标是合成一个2048的方块。游戏看似简单，但状态空间极为庞大（16个格子上每个格子可以是空或2的幂次方），精确的动态规划求解在大型棋盘上不可行。本文将使用Java实现2048 AI，采用A*搜索算法在有限深度的状态空间中寻找最优移动序列，并设计单调性与平滑性启发式函数来评估棋盘状态的质量。

算法核心思想

A*搜索在2048中的应用

2048是单人完全信息游戏，适合使用搜索算法寻找最优策略。A*搜索通过评估函数 f(n) = g(n) + h(n) 来引导搜索方向：
– g(n)：从初始状态到当前状态的移动步数
– h(n)：启发式函数估计当前状态到目标状态的”距离”

由于2048的状态空间太大，实际采用限定深度的A*搜索（类似于迭代深化A*），在有限的搜索深度内评估每个可能的移动序列，选择累积评估值最高的动作。

单调性与平滑性启发式

2048的核心策略是让大数字聚集在一个角落，并保持数字沿某方向单调递减。启发式函数设计如下：

  1. 单调性（Monotonicity）：棋盘沿四个方向（上、下、左、右）的单调递减程度之和。高单调性意味着大数字集中在角落。

  2. 平滑性（Smoothness）：相邻格子数值差异的倒数和。平滑的棋盘更容易合并。

  3. 空格数（Free Tiles）：空格越多，未来操作灵活性越大。

  4. 最大值位置（Max Value Position）：最大数字是否在角落的奖励。

综合启发式：h = 单调性权重 + 平滑性权重 + 空格奖励 + 角落最大值奖励

完整Java实现

import java.util.*;

/**
 * 2048游戏AI - A*搜索与单调性启发式评估
 */
public class Game2048AStar {

    private static final int SIZE = 4;
    private static final int TARGET = 2048;
    private static final Random RAND = new Random();

    // 方向
    private static final int UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;
    private static final String[] DIR_NAMES = {"UP", "RIGHT", "DOWN", "LEFT"};

    private int[][] board;
    private int score;

    public Game2048AStar() {
        this.board = new int[SIZE][SIZE];
        this.score = 0;
    }

    /**
     * 初始化游戏，在随机空格生成两个数字（90%概率为2，10%概率为4）
     */
    public void init() {
        for (int[] row : board) Arrays.fill(row, 0);
        score = 0;
        addRandomTile();
        addRandomTile();
    }

    /**
     * 在随机空格添加一个新数字
     */
    private void addRandomTile() {
        List<int[]> empty = new ArrayList<>();
        for (int i = 0; i < SIZE; i++)
            for (int j = 0; j < SIZE; j++)
                if (board[i][j] == 0) empty.add(new int[]{i, j});

        if (empty.isEmpty()) return;
        int[] pos = empty.get(RAND.nextInt(empty.size()));
        board[pos[0]][pos[1]] = RAND.nextDouble() < 0.9 ? 2 : 4;
    }

    /**
     * 执行指定方向的移动，返回是否成功移动
     */
    public boolean move(int dir) {
        int[][] old = copyBoard();

        // 旋转棋盘使统一按"左"方向处理
        int[][] rotated = rotateToLeft(board, dir);

        // 对每一行执行左合并
        for (int i = 0; i < SIZE; i++) {
            rotated[i] = slideAndMerge(rotated[i]);
        }

        // 旋转回原始方向
        board = rotateBack(rotated, dir);

        boolean changed = !boardsEqual(old, board);
        if (changed) addRandomTile();
        return changed;
    }

    /**
     * 将棋盘旋转，使指定方向变为"左"
     */
    private int[][] rotateToLeft(int[][] b, int dir) {
        int[][] result = new int[SIZE][SIZE];
        switch (dir) {
            case LEFT:
                for (int i = 0; i < SIZE; i++)
                    result[i] = b[i].clone();
                break;
            case RIGHT:
                for (int i = 0; i < SIZE; i++)
                    for (int j = 0; j < SIZE; j++)
                        result[i][j] = b[i][SIZE - 1 - j];
                break;
            case UP:
                for (int i = 0; i < SIZE; i++)
                    for (int j = 0; j < SIZE; j++)
                        result[i][j] = b[j][SIZE - 1 - i];
                break;
            case DOWN:
                for (int i = 0; i < SIZE; i++)
                    for (int j = 0; j < SIZE; j++)
                        result[i][j] = b[SIZE - 1 - j][i];
                break;
        }
        return result;
    }

    private int[][] rotateBack(int[][] b, int dir) {
        int[][] result = new int[SIZE][SIZE];
        switch (dir) {
            case LEFT:
                for (int i = 0; i < SIZE; i++) result[i] = b[i].clone();
                break;
            case RIGHT:
                for (int i = 0; i < SIZE; i++)
                    for (int j = 0; j < SIZE; j++)
                        result[i][j] = b[i][SIZE - 1 - j];
                break;
            case UP:
                for (int i = 0; i < SIZE; i++)
                    for (int j = 0; j < SIZE; j++)
                        result[j][SIZE - 1 - i] = b[i][j];
                break;
            case DOWN:
                for (int i = 0; i < SIZE; i++)
                    for (int j = 0; j < SIZE; j++)
                        result[SIZE - 1 - j][i] = b[i][j];
                break;
        }
        return result;
    }

    /**
     * 将一行向左滑动并合并
     */
    private int[] slideAndMerge(int[] row) {
        int[] result = new int[SIZE];
        int idx = 0;

        // 移除非零数字
        for (int val : row) {
            if (val != 0) result[idx++] = val;
        }

        // 合并相邻相同数字
        for (int i = 0; i < SIZE - 1; i++) {
            if (result[i] != 0 && result[i] == result[i + 1]) {
                result[i] *= 2;
                score += result[i];
                result[i + 1] = 0;
            }
        }

        // 再次滑动
        int[] finalRow = new int[SIZE];
        idx = 0;
        for (int val : result) {
            if (val != 0) finalRow[idx++] = val;
        }
        return finalRow;
    }

    private int[][] copyBoard() {
        int[][] copy = new int[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) copy[i] = board[i].clone();
        return copy;
    }

    private boolean boardsEqual(int[][] a, int[][] b) {
        for (int i = 0; i < SIZE; i++)
            for (int j = 0; j < SIZE; j++)
                if (a[i][j] != b[i][j]) return false;
        return true;
    }

    /**
     * 启发式评估函数：综合单调性、平滑性、空格数和最大值位置
     */
    public double evaluate(int[][] b) {
        double monoScore = 0;
        double smoothScore = 0;
        int emptyCount = 0;
        int maxVal = 0;
        int maxR = 0, maxC = 0;

        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                int val = b[i][j];
                if (val == 0) {
                    emptyCount++;
                    continue;
                }
                if (val > maxVal) {
                    maxVal = val;
                    maxR = i; maxC = j;
                }

                // 单调性：鼓励数字沿左/上方向递增
                if (j < SIZE - 1 && b[i][j + 1] != 0) {
                    if (val >= b[i][j + 1]) monoScore += Math.log(val) / Math.log(2);
                    else monoScore -= Math.log(b[i][j + 1]) / Math.log(2);
                }
                if (i < SIZE - 1 && b[i + 1][j] != 0) {
                    if (val >= b[i + 1][j]) monoScore += Math.log(val) / Math.log(2);
                    else monoScore -= Math.log(b[i + 1][j]) / Math.log(2);
                }

                // 平滑性：相邻差异越小越好
                if (j < SIZE - 1) {
                    int diff = Math.abs(val - b[i][j + 1]);
                    smoothScore -= diff;
                }
                if (i < SIZE - 1) {
                    int diff = Math.abs(val - b[i + 1][j]);
                    smoothScore -= diff;
                }
            }
        }

        // 最大值在角落的奖励
        double cornerBonus = 0;
        if ((maxR == 0 || maxR == SIZE - 1) && (maxC == 0 || maxC == SIZE - 1))
            cornerBonus = Math.log(maxVal) / Math.log(2) * 10;

        return monoScore * 1.0 + smoothScore * 0.1 + emptyCount * 2.7 + cornerBonus;
    }

    /**
     * A*搜索：限定深度搜索最优移动
     * @param depth 搜索深度
     * @return 最优方向的评估值
     */
    private double aStarSearch(int[][] currentBoard, int depth) {
        if (depth == 0) return evaluate(currentBoard);

        double bestScore = Double.NEGATIVE_INFINITY;

        for (int dir = 0; dir < 4; dir++) {
            int[][] sim = simulateMove(currentBoard, dir);
            if (sim == null) continue; // 该方向不可移动

            // 2048随机性：新方块以概率分布出现
            // 为简化计算，评估期望得分（ Expectimax单层简化 ）
            double moveScore = 0;
            List<int[]> empty = new ArrayList<>();
            for (int i = 0; i < SIZE; i++)
                for (int j = 0; j < SIZE; j++)
                    if (sim[i][j] == 0) empty.add(new int[]{i, j});

            if (empty.isEmpty()) {
                moveScore = aStarSearch(sim, depth - 1);
            } else {
                // 期望评估：90%生成2，10%生成4
                double total = 0;
                for (int[] pos : empty) {
                    int[][] with2 = copyBoard(sim);
                    with2[pos[0]][pos[1]] = 2;
                    total += 0.9 * aStarSearch(with2, depth - 1) / empty.size();

                    int[][] with4 = copyBoard(sim);
                    with4[pos[0]][pos[1]] = 4;
                    total += 0.1 * aStarSearch(with4, depth - 1) / empty.size();
                }
                moveScore = total;
            }

            bestScore = Math.max(bestScore, moveScore);
        }

        return bestScore == Double.NEGATIVE_INFINITY ? evaluate(currentBoard) : bestScore;
    }

    /**
     * 模拟移动（不修改真实棋盘）
     */
    private int[][] simulateMove(int[][] b, int dir) {
        int[][] rotated = rotateToLeft(b, dir);
        boolean changed = false;

        for (int i = 0; i < SIZE; i++) {
            int[] merged = slideAndMergeNoScore(rotated[i]);
            if (!Arrays.equals(rotated[i], merged)) changed = true;
            rotated[i] = merged;
        }

        if (!changed) return null;
        return rotateBack(rotated, dir);
    }

    private int[] slideAndMergeNoScore(int[] row) {
        int[] result = new int[SIZE];
        int idx = 0;
        for (int val : row) if (val != 0) result[idx++] = val;
        for (int i = 0; i < SIZE - 1; i++) {
            if (result[i] != 0 && result[i] == result[i + 1]) {
                result[i] *= 2;
                result[i + 1] = 0;
            }
        }
        int[] finalRow = new int[SIZE];
        idx = 0;
        for (int val : result) if (val != 0) finalRow[idx++] = val;
        return finalRow;
    }

    /**
     * AI选择最佳移动
     */
    public int aiMove() {
        double bestScore = Double.NEGATIVE_INFINITY;
        int bestDir = -1;

        for (int dir = 0; dir < 4; dir++) {
            int[][] sim = simulateMove(board, dir);
            if (sim == null) continue;

            // 使用A*搜索评估（深度3，平衡效率与效果）
            double score = aStarSearch(sim, 3);
            if (score > bestScore) {
                bestScore = score;
                bestDir = dir;
            }
        }

        if (bestDir >= 0) {
            move(bestDir);
            return bestDir;
        }
        return -1;
    }

    /**
     * 检查是否达到目标或无法移动
     */
    public boolean isGameOver() {
        for (int i = 0; i < SIZE; i++)
            for (int j = 0; j < SIZE; j++)
                if (board[i][j] == TARGET) return true;

        for (int dir = 0; dir < 4; dir++)
            if (simulateMove(board, dir) != null) return false;
        return true;
    }

    /**
     * 打印棋盘
     */
    public void printBoard() {
        System.out.println("Score: " + score);
        System.out.println("+------+------+------+------+");
        for (int i = 0; i < SIZE; i++) {
            System.out.print("|");
            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] == 0) System.out.print("      |");
                else System.out.printf(" %4d |", board[i][j]);
            }
            System.out.println();
            System.out.println("+------+------+------+------+");
        }
        System.out.println();
    }

    /**
     * 获取棋盘最大值
     */
    public int getMaxTile() {
        int max = 0;
        for (int[] row : board)
            for (int val : row)
                max = Math.max(max, val);
        return max;
    }

    /**
     * 运行AI游戏
     */
    public void runAI() {
        init();
        printBoard();
        int moves = 0;

        while (!isGameOver() && moves < 10000) {
            int dir = aiMove();
            if (dir < 0) break;
            moves++;
            if (moves % 50 == 0) {
                System.out.println("Move " + moves + ": " + DIR_NAMES[dir]);
                printBoard();
            }
        }

        System.out.println("Game Over! Moves: " + moves + ", Max Tile: " + getMaxTile() + ", Score: " + score);
        printBoard();
    }

    public static void main(String[] args) {
        Game2048AStar game = new Game2048AStar();
        game.runAI();
    }
}

关键算法解析

1. 单调性评估

单调性启发式是2048 AI的核心。代码中计算了棋盘沿水平方向和垂直方向的单调递减程度：
– 当val >= b[i][j+1]时，说明从左到右是递减的，奖励log2(val)
– 否则惩罚差异值

这种设计鼓励大数字聚集在左上角（或其他角落），形成”梯度”结构，便于后续合并。

2. A*搜索与期望评估

2048的随机性（新方块随机出现在空格中）使得传统的确定性A需要扩展为期望A**。代码中对每个空格模拟生成2（90%概率）和4（10%概率），计算期望评估值：

E[state] = Σ(P(tile) × Evaluate(state_with_tile))

这种期望计算使AI能够考虑随机因素的影响，做出更鲁棒的决策。

3. 搜索深度控制

2048的状态空间随空格数指数增长。代码中使用深度为3的限定搜索，在评估效果和计算效率之间取得平衡。深度过浅会导致短视，深度过深则无法在合理时间内完成评估。

复杂度分析

指标 复杂度 说明
分支因子 O(4) 每步4个方向
搜索树节点 O(4^d × E) d为深度，E为平均空格数
启发式计算 O(SIZE²) 遍历整个棋盘
单步决策时间 O(4^d × SIZE² × E) 完整A*搜索

在4×4棋盘上，深度为3时，单步决策通常可在几十毫秒内完成，适合实时游戏AI。

总结

本文实现了基于A*搜索的2048 AI，通过单调性、平滑性、空格数和角落最大值四个维度综合评估棋盘状态。期望评估机制有效处理了2048固有的随机性，使AI能够在复杂的动态环境中做出合理决策。读者可以进一步尝试调整启发式权重、增加搜索深度，或引入更高级的评估特征（如可合并对数、行/列隔离度等）来提升AI表现。

Tagged with: