五子棋AI进阶：极大极小值搜索

前言

上篇文章，介绍了一下五子棋 AI 的入门实现，学完之后能用，就是 AI 还太年轻，只能思考一步棋。

本文将介绍一种提高 AI 思考能力的算法：极大极小值算法。

Minimax算法 又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。通常以递归形式来实现。
Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的一个，其输赢的总和为0（有点像能量守恒，就像本身两个玩家都有1点，最后输家要将他的1点给赢家，但整体上还是总共有2点）。 —— 百度百科

极大极小值搜索算法

算法实现原理

对于五子棋游戏来说，如果 AI 执黑子先下，那么第一步 AI 共有 225 种落子方式，AI 落子到一个点后，表示 AI 回合结束，换到对手（白子）落子，这时对手共有 224 种落子方式。我们可以将 AI 和对手交替落子形成的所有情况穷举出来，这样就形成了一棵树，叫做 博弈树。

但是，穷举出所有情况太不现实了，这颗 博弈树 最后一层节点数就有 225! ，这个数字是特别庞大的，数字10后边要加432个0！！！这程序运行起来，电脑还要不要了？

所以，我们只考虑2步棋或4步棋的情况。

如图所示，我只列举出了走4步棋所形成的部分情况。A0 是起点，AI 将在这个点中选择出最佳的落子点位。A0 下面有两个分支（实际有225个分支，这里放不下，就只演示2个）A1 和 A2，这两个分支表示的就是 AI 第一步落子的两种情况。

A1 如果落子到 (0,0)，则当前局面就如下图所示

A2 如果落子到 (0,1)，则当前局面就如下图所示

AI 落子完后，就轮到对方落子了。在 A1 分支中，对方有 B1 和 B2 两种落子情况（实际有224种）

B1 情况如图所示

B2 情况如图所示

一直到第4步落子完时，B5 的局面就会像下图这样

要知道，这颗 博弈树 是以 AI 的角度建立的，AI 为了赢，它需要从 A1 和 A2 分支中，选择一个对自己最有利的落子点，而 A1 和 A2 分支的好坏需要它们下面的 B1、B2 和 B3 、B4 决定，所以说，下层分支的局面会影响上层分支的选择。

要确定 A1 和 A2 分支哪个好，我们必须从这个分支的最深层看起。

B5 ~ B12 节点的局面是由对方造成的，我们就假设对方很聪明，他一定能选择一个最有利于他自己的落子点。怎么知道哪个落子点好？还是和之前一样，用评估函数评估一下，分高的就好呗，但有一点不同的是，之前评估的是一个点，现在需要评估一个局面，怎么评估本文后面会提到。

假设 B5 ~ B12 中 各个节点的得分如下图最底部所示

则 A3 节点得分为 0，A4 节点得分为 1，A5 节点得分为 3，A6 节点得分为 2。这就很奇怪了，不是说让选得分最大的吗？这怎么都选的最小的得分？？？

这其实还是要从评估函数说起，因为我们现在的评估函数都是从 AI 角度出发的，评估的得分越高，只会对 AI 有利，对对方来说是不利的。所以，当是对方的分支的时候，我们要选得分最低的节点，因为 AI 要站在对方的角度去做选择，换位思考。这里如果还是没有搞懂的话，我们可以这么理解：

假如张三遇到了抢劫犯，他认为他身上值钱的东西有：《Java从入门到入土》、1000元现金、某厂月薪3.5K包吃包住的Offer。现在抢劫犯要抢劫他身上的一样东西，如果站在张三的角度思考的话，那肯定是让抢《Java从入门到入土》这本破书了，但是站在抢劫犯的角度思考，1000元现金比什么都强！

这就是思考角度的问题，对方如果很聪明，那他肯定是选择让 AI 利益最低的一个节点，现在我们就认为对方是一个绝顶聪明的人，所以在对方选择的分支里都选择了分值最低的，好让 AI 的利益受损。

再接下去就是 AI 选择分支了，不用说，AI 肯定选分高的。AI 要从对方给的那些低分分支里选择分最高的，也就是差的里面选好的。所以 B1 得分为 1，B2 得分为 3。

后面也是一样的流程，又轮到对方选择了，对方肯定选择 B1 分支，B1 分支是得分最低的节点，所以到最后，A1 分支的最终得分为 1。

我们对 A2 分支也做如上操作：AI 选高分，对方选低分。最后可以得出如下图所示的结果

现在我们知道 A1 最终得分为 1，A2 最终得分为 2，因为 AI 会选择最大得分的分支 A2，所以最终 A0 得分为 2，也就是说，AI 下一步的最佳落子点为 (0,1)。

AI 选择的分支一定是选最高分值的叫做 Max 分支，对方选择的分支一定是选最低分值的叫做 Min 分支，然后由低到高，倒推着求出起点的得分，这就是 极大极小值搜索 的实现原理。

代码实现

我们接着上次的代码来，在 ZhiZhangAIService 类中定义一个全局变量 bestPoint 用于存放 AI 当前最佳下棋点位，再定义一个全局变量 attack 用于设置 AI 的进攻能力。

    /**

     * AI最佳下棋点位

     */

    private Point bestPoint;

    /**

     * 进攻系数

     */

    private int attack;

新增 minimax 方法，编写 极大极小值搜索 算法的实现代码。这里是使用递归的方式，深度优先遍历 博弈树，生成树和选择节点是同时进行的。type 表示当前走棋方，刚开始时，因为要从根节点开始生成树，所以要传入 0 ，并且 AI 最后选择高分节点的时候也是在根节点进行的。depth 表示搜索的深度，也就是 AI 思考的步数
，我这边传入的是 2，也就是只思考两步棋，思考4步或6步都行，只要你电脑吃得消（计算量很大的哦）。

    /**

     * 极大极小值搜索

     *

     * @param type  当前走棋方 0.根节点表示AI走棋 1.AI 2.玩家

     * @param depth 搜索深度

     * @return

     */

    private int minimax(int type, int depth) {

        // 是否是根节点

        boolean isRoot = type == 0;

        if (isRoot) {

            // 根节点是AI走棋

            type = this.ai;

        }


        // 当前是否是AI走棋

        boolean isAI = type == this.ai;

        // 当前分值，

        int score;

        if (isAI) {

            // AI因为要选择最高分，所以初始化一个难以到达的低分

            score = -INFINITY;

        } else {

            // 对手要选择最低分，所以初始化一个难以到达的高分

            score = INFINITY;

        }


        // 到达叶子结点

        if (depth == 0) {

            /**

             * 评估每棵博弈树的叶子结点的局势

             * 比如：depth=2时，表示从AI开始走两步棋之后的局势评估，AI(走第一步) -> 玩家(走第二步)，然后对局势进行评估

             * 注意：局势评估是以AI角度进行的，分值越大对AI越有利，对玩家越不利

             */

            return evaluateAll();

        }


        for (int i = 0; i < this.cols; i++) {

            for (int j = 0; j < this.rows; j++) {

                if (this.chessData[i][j] != 0) {

                    // 该处已有棋子，跳过

                    continue;

                }


                /* 模拟 AI -> 玩家 交替落子 */

                Point p = new Point(i, j, type);

                // 落子

                putChess(p);

                // 递归生成博弈树，并评估叶子结点的局势获取分值

                int curScore = minimax(3 - type, depth - 1);

                // 撤销落子

                revokeChess(p);


                if (isAI) {

                    // AI要选对自己最有利的节点（分最高的）

                    if (curScore > score) {

                        // 最高值被刷新

                        score = curScore;

                        if (isRoot) {

                            // 根节点处更新AI最好的棋位

                            this.bestPoint = p;

                        }

                    }

                } else {

                    // 对手要选对AI最不利的节点（分最低的）

                    if (curScore < score) {

                        // 最低值被刷新

                        score = curScore;

                    }

                }

            }

        }


        return score;

    }

新增模拟落子 putChess 和撤销落子 revokeChess 等方法。

    /**

     * 下棋子

     *

     * @param point 棋子

     */

    private void putChess(Point point) {

        this.chessData[point.x][point.y] = point.type;

    }


    /**

     * 撤销下的棋子

     *

     * @param point 棋子

     */

    private void revokeChess(Point point) {

        this.chessData[point.x][point.y] = 0;

    }

新增一个评估函数 evaluateAll ，用于评估一个局面。这个评估函数实现原理为：搜索棋盘上现在所有的已落子的点位，然后调用之前的评估函数 evaluate 对这个点进行评分，如果这个位置上是 AI 的棋子，则加上评估的分值，是对方的棋子就减去评估的分值。注意这里有个进攻系数 attack，这个值我现在设定的是 2，如果这个值太低或太高都会影响 AI 的判断，我这边经过测试，觉得设置为 2 会比较好点。最后就是将 AI 所有棋子的总得分乘以进攻系数，再减去对手所有棋子的总得分，作为本局面的得分。

    /**

     * 以AI角度对当前局势进行评估，分数越大对AI越有利

     *

     * @return

     */

    private int evaluateAll() {

        // AI得分

        int aiScore = 0;

        // 对手得分

        int foeScore = 0;


        for (int i = 0; i < this.cols; i++) {

            for (int j = 0; j < this.rows; j++) {

                int type = this.chessData[i][j];

                if (type == 0) {

                    // 该点没有棋子，跳过

                    continue;

                }


                // 评估该棋位分值

                int val = evaluate(new Point(i, j, type));

                if (type == this.ai) {

                    // 累积AI得分

                    aiScore += val;

                } else {

                    // 累积对手得分

                    foeScore += val;

                }

            }

        }


        // 该局AI最终得分 = AI得分 * 进攻系数 - 对手得分

        return aiScore * this.attack - foeScore;

    }

调整 AI 入口方法 getPoint，现在使用 minimax 方法获取 AI 的最佳落子点位。

    @Override

    public Point getPoint(int[][] chessData, Point point, boolean started) {

        initChessData(chessData);

        this.ai = 3 - point.type;

        this.bestPoint = null;

        this.attack = 2;


        if (started) {

            // AI先下，首子天元

            int centerX = this.cols / 2;

            int centerY = this.rows / 2;

            return new Point(centerX, centerY, this.ai);

        }


        // 基于极大极小值搜索获取最佳棋位

        minimax(0, 2);


        return this.bestPoint;

    }

测试一下，因为现在的 AI 可以思考两步棋了，所以比之前厉害了许多。

但是，又因为要搜索很多个节点，所以响应耗时也变长了很多，思考两步的情况下，平均响应时间在 3s 左右。

再去和大佬的 AI 下一把（gobang.light7.cn/#/），思考两步棋的 AI 执黑子先下，已经可以很轻松的打败大佬的普通级别的 AI 了。

AI 执白后下的话，连萌新级别的都打不赢，这个应该是评估模型的问题，后续需要对评估模型做进一步的优化。

现在写的搜索算法，如果要让 AI 思考4步棋的话，我这普通电脑还是吃不消的，后续对搜索算法还有更多的优化空间。