2048AI设计与实现

发表于 2019-06-04 更新于 2023-04-08 分类于 project 阅读次数：本文字数： 1.1k 阅读时长 ≈ 4 分钟

2048

针对 2048 游戏，实现一个 AI 程序，当用户选择提示功能时，系统根据当前局势找出适当的决策帮助用户赢得游戏。系统界面实现由 Android 完成，主体 AI 使用了传统的博弈树模型中常用的算法，即 Minimax 和 Alpha-beta 剪枝，重点落在启发函数的设计上。项目的启发函数从四个方面评估当前的局势，结合迭代深搜，在限定搜索时间内做出决策，赢得游戏的概率高于 90%。

2048AI设计与实现

项目简介

2048 游戏简介

2048 是一款比较流行的数字游戏，最早于 2014 年 3 月 20 日发行。原版 2048 首先在 GitHub 上发布，原作者是 Gabriele Cirulli，后被移植到各个平台。

游戏规则：

每次可以选择上下左右其中一个方向去滑动，每滑动一次，所有的数字方块都会往滑动的方向靠拢外，系统也会在空白的地方乱数出现一个数字方块，相同数字的方块在靠拢、相撞时会相加。不断的叠加最终拼凑出 2048 这个数字就算成功。

2048 智能提示实现

系统 AI 提供提示功能，从当前格局出发，寻找所能达到搜索层次的最优的解

点击 Hint 按钮，显示滑动提示

hint-1

hint-2

建模

Since the game is a discrete state space, perfect information, turn-based game like chess and checkers, I used the same methods that have been proven to work on those games, namely minimax search with alpha-beta pruning. Since there is already a lot of info on that algorithm out there, I'll just talk about the two main heuristics that I use in the static evaluation function and which formalize many of the intuitions that other people have expressed here.

2048 本质上可以抽象成信息对称双人对弈模型（玩家向四个方向中的一个移动，然后计算机在某个空格中填入 2 或 4 ）。这里“信息对称”是指在任一时刻对弈双方对格局的信息完全一致，移动策略仅依赖对接下来格局的推理。作者使用的核心算法为对弈模型中常用的带 Alpha-beta 剪枝的 Minimax。这个算法也常被用于如国际象棋等信息对称对弈 AI 中。

算法分析

http://blog.codinglabs.org/articles/2048-ai-analysis.html

算法实现

格局评估指标

/**
 * 格局评估函数
 *
 * @return 返回当前格局的评估值，用于比较判断格局的好坏
 */
private double evaluate() {
    double smoothWeight = 0.1, //平滑性权重系数
            monoWeight = 1.3, //单调性权重系数
            emptyWeight = 2.7, //空格数权重系数
            maxWeight = 1.0; //最大数权重系数
    return grid.smoothness() * smoothWeight
            + grid.monotonicity() * monoWeight
            + Math.log(getEmptyNum(grid.getCellMatrix())) * emptyWeight
            + grid.maxValue() * maxWeight;
}

采用线性函数，并添加权重系数，前 3 项指标能衡量一个局面的好坏，而最大数该项，则让游戏 AI 多了一点积极和"冒险"。

Minimax Search 和 Alpha Beta Pruning 的实现

private SearchResult search(int depth, double alpha, double beta, int positions, int cutoffs) {
    double bestScore;
    int bestMove = -1;
    SearchResult result = new SearchResult();
    int[] directions = {0, 1, 2, 3};

    if (this.grid.playerTurn) {  // Max 层
        bestScore = alpha;
        for (int direction : directions) {  // 玩家遍历四个滑动方向，找出一个最好的
            GameState newGrid = new GameState(this.grid.getCellMatrix());
            if (newGrid.move(direction)) {
                positions++;
//                if (newGrid.isWin()) {
//                    return new SearchResult(direction, 10000, positions, cutoffs);
//                }
                AI newAI = new AI(newGrid);
                newAI.grid.playerTurn = false;

                if (depth == 0) { //如果depth=0,搜索到该层后不再向下搜索
                    result.move = direction;
                    result.score = newAI.evaluate();
                } else { //如果depth>0,则继续搜索下一层，下一层为电脑做出决策的层
                    result = newAI.search(depth - 1, bestScore, beta, positions, cutoffs);
                    if (result.score > 9900) { // 如果赢得游戏
                        result.score--; // 轻微地惩罚因为更大的搜索深度
                    }
                    positions = result.positions;
                    cutoffs = result.cutoffs;
                }

                //如果当前搜索分支的格局分数要好于之前得到的分数，则更新决策，同时更新bestScore，也即alpha的值
                if (result.score > bestScore) {
                    bestScore = result.score;
                    bestMove = direction;
                }
                //如果当前bestScore也即alpha>beta时，表明这个节点下不会再有更好解，于是剪枝
                if (bestScore > beta) {
                    cutoffs++;  //剪枝
                    return new SearchResult(bestMove, beta, positions, cutoffs);
                }
            }
        }
    } else {
        // Min 层，该层为电脑层(也即我们的对手)，这里我们假设对手(电脑)足够聪明，总是能做出使格局变到最坏的决策
        bestScore = beta;

        // 尝试给每个空闲块填入2或4，然后计算格局的评估值
        List<Candidate> candidates = new ArrayList<>();
        List<int[]> cells = this.grid.getAvailableCells();
        int[] fill = {2, 4};
        List<Double> scores_2 = new ArrayList<>();
        List<Double> scores_4 = new ArrayList<>();
        for (int value : fill) {
            for (int i = 0; i < cells.size(); i++) {
                this.grid.insertTitle(cells.get(i)[0], cells.get(i)[1], value);
                if (value == 2) scores_2.add(i, -this.grid.smoothness() + this.grid.islands());
                if (value == 4) scores_4.add(i, -this.grid.smoothness() + this.grid.islands());
                this.grid.removeTile(cells.get(i)[0], cells.get(i)[1]);
            }
        }

        // 找出使格局变得最坏的所有可能操作
        double maxScore = Math.max(Collections.max(scores_2), Collections.max(scores_4));
         for (int value : fill) {
             if (value == 2) {
                 for (Double fitness : scores_2) {
                    if (fitness == maxScore) {
                        int index = scores_2.indexOf(fitness);
                        candidates.add(new Candidate(cells.get(index)[0], cells.get(index)[1], value));
                    }
                 }
            }
            if (value == 4) {
                for (Double fitness : scores_4) {
                    if (fitness == maxScore) {
                        int index = scores_4.indexOf(fitness);
                        candidates.add(new Candidate(cells.get(index)[0], cells.get(index)[1], value));
                    }
                }
            }
        }

        // 然后遍历这些操作，基于这些操作向下搜索，找到使得格局最坏的分支
        for (int i = 0; i < candidates.size(); i++) {
            int pos_x = candidates.get(i).x;
            int pos_y = candidates.get(i).y;
            int value = candidates.get(i).value;
            GameState newGrid = new GameState(this.grid.getCellMatrix());
            // 电脑即对手做出一个可能的对于电脑来说最好的（对于玩家来说最坏的）决策
            newGrid.insertTitle(pos_x, pos_y, value);
            positions++;
            AI newAI = new AI(newGrid);
            // 向下搜索，下一层为Max层，轮到玩家进行决策
            newAI.grid.playerTurn = true;
            // 这里depth没有减1是为了保证搜索到最深的层为Max层
            result = newAI.search(depth, alpha, bestScore, positions, cutoffs);
            positions = result.positions;
            cutoffs = result.cutoffs;

            // 该层为Min层，哪个分支的局势最不好，就选哪个分支，这里的bestScore代表beta
            if (result.score < bestScore) {
                bestScore = result.score;
            }
            // 如果当前bestScore也即beta<alpha时，表明这个节点下不会再有更好解，于是剪枝
            if (bestScore < alpha) {
                cutoffs++;  //减枝
                return new SearchResult(-1, alpha, positions, cutoffs);
            }
        }
    }

    return new SearchResult(bestMove, bestScore, positions, cutoffs);
}

己方格局评价函数实现

平滑性

/**
 * 测量网格的平滑程度(这些块的值可以形象地解释为海拔)。
 * 相邻两个方块的值差异越小，格局就越平滑(在log空间中，所以它表示在合并之前需要进行的合并的数量)。
 *
 * @return
 */
public double smoothness() {
    int smoothness = 0;
    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 4; y++) {
            if (this.cellMatrix[x][y] != 0) {
                double value = Math.log(this.cellMatrix[x][y]) / Math.log(2);
                // 计算水平方向和垂直方向的平滑性评估值
                for (int direction = 1; direction <= 2; direction++) {
                    int[] vector = this.vectors[direction];
                    int cnt_x = x, cnt_y = y;
                    do {
                        cnt_x += vector[0];
                        cnt_y += vector[1];
                    } while (isInBounds(cnt_x, cnt_y) && isCellAvailable(cnt_x, cnt_y));
                    if (isInBounds(cnt_x, cnt_y)) {
                        if (cellMatrix[cnt_x][cnt_y] != 0) {
                            double targetValue = Math.log(cellMatrix[cnt_x][cnt_y]) / Math.log(2);
                            smoothness -= Math.abs(value - targetValue);
                        }
                    }
                }
            }
        }
    }
    return smoothness;
}

单调性

/**
 * 测量网格的单调性。
 * 这意味着在向左/向右和向上/向下的方向，方块的值都是严格递增或递减的。
 *
 * @return
 */
public double monotonicity() {
    // 保存四个方向格局单调性的评估值
    int[] totals = {0, 0, 0, 0};

    // 左/右 方向
    for (int x = 0; x < 4; x++) {
        int current = 0;
        int next = current + 1;
        while (next < 4) {
            while (next < 4 && this.cellMatrix[x][next] == 0) next++;
            if (next >= 4) next--;
            double currentValue = (this.cellMatrix[x][current] != 0) ? Math.log(this.cellMatrix[x][current]) / Math.log(2) : 0;
            double nextValue = (this.cellMatrix[x][next] != 0) ? Math.log(this.cellMatrix[x][next]) / Math.log(2) : 0;
            if (currentValue > nextValue) {
                totals[0] += nextValue - currentValue;
            } else if (nextValue > currentValue) {
                totals[1] += currentValue - nextValue;
            }
            current = next;
            next++;
        }
    }

    // 上/下 方向
    for (int y = 0; y < 4; y++) {
        int current = 0;
        int next = current + 1;
        while (next < 4) {
            while (next < 4 && this.cellMatrix[next][y] == 0) next++;
            if (next >= 4) next--;
            double currentValue = (this.cellMatrix[current][y] != 0) ? Math.log(this.cellMatrix[current][y]) / Math.log(2) : 0;
            double nextValue = (this.cellMatrix[next][y] != 0) ? Math.log(this.cellMatrix[next][y]) / Math.log(2) : 0;
            if (currentValue > nextValue) {
                totals[2] += nextValue - currentValue;
            } else if (nextValue > currentValue) {
                totals[3] += currentValue - nextValue;
            }
            current = next;
            next++;
        }
    }

    // 取四个方向中最大的值为当前格局单调性的评估值
    return Math.max(totals[0], totals[1]) + Math.max(totals[2], totals[3]);
}

空格数

private int getEmptyNum(int[][] matrix) {
    int sum = 0;
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0; j < matrix[0].length; j++)
            if (matrix[i][j] == 0) sum++;
    return sum;
}

最大数

/**
 * 取最大数，这里取对数是为与前面其它指标的计算保持一致，均在log空间进行
 *
 * @return
 */
public double maxValue() {
    return Math.log(ArrayUtil.getMax(cellMatrix)) / Math.log(2);
}

对方格局评价函数实现

对方对于格局的目标就是使得连通个数变多并且使得平滑性降低，表现效果就是使得格局趋于散乱，让玩家难以合并相同的数字。

/**
 * 递归调用计算当前格局的连通块个数
 *
 * @return
 */
public int islands() {
    int islands = 0;

    marked = new boolean[4][4];
    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 4; y++) {
            if (this.cellMatrix[x][y] != 0) {
                this.marked[x][y] = false;
            }
        }
    }
    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 4; y++) {
            if (this.cellMatrix[x][y] != 0 && !this.marked[x][y]) {
                islands++;
                mark(x, y, this.cellMatrix[x][y]);
            }
        }
    }

    return islands;
}

private void mark(int x, int y, int value) {
    if (x >= 0 && x <= 3 && y >= 0 && y <= 3 && (this.cellMatrix[x][y] != 0)
            && (this.cellMatrix[x][y] == value) && (!this.marked[x][y])) {
        this.marked[x][y] = true;
        for (int direction = 0; direction < 4; direction++) {
            int[] vector = this.vectors[direction];
            mark(x + vector[0], y + vector[1], value);
        }
    }
}

迭代深搜

// 执行搜索操作，返回最好的移动方向
public int getBestMove() {
    return this.iterativeDeep(100);
}

// 基于alpha-beta的Minimax搜索，进行迭代深搜，搜索时间设定为0.1秒，即决策的思考时间为0.1秒
private int iterativeDeep(long minSearchTime) {
    long start = new Date().getTime();
    int depth = 0;
    int best = -1;
    do {
        SearchResult newBest = this.search(depth, -10000, 10000, 0, 0);
        if (newBest.move == -1) break;
        else best = newBest.move;
        depth++;
    } while (new Date().getTime() - start < minSearchTime);
    return best;
}

运行效果

自动运行结果

run-case-1

run-case-2

结论

游戏 AI 的决策过程，是标准的 Minimax Search 结合 Alpha Beta Pruning 的实现。所有的方向(上下左右)都会去尝试。然而在对手做决策时，不是每个空格都去尝试填 2 或 4 。而是选择了最坏的局面，做为搜索分支的剪枝条件，选择性地丢弃了很多搜索分支。对于选择性忽略搜索节点，在某些情况下，会失去获取最优解的机会。不过砍掉了很多分支后, 其搜索深度大大加强，生存能力更强大。另外，超时判断在每个深度探索结束后进行，这未必会精确，甚至误差很大，但不管如何游戏 AI 基本达到了每 100ms 决策一步的要求。最后，根据原作者 ovolve 创造性的思维和建模，把环境拟人化的对弈模型，使得传统的博弈树模型能应用于此，这是面对反馈类场景的一种很好的评估决策思路。