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

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

五子棋AI进阶:极大极小值搜索_第1张图片

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

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

极大极小值搜索算法
算法实现原理
对于五子棋游戏来说,如果 AI 执黑子先下,那么第一步 AI 共有 225 种落子方式,AI 落子到一个点后,表示 AI 回合结束,换到对手(白子)落子,这时对手共有 224 种落子方式。我们可以将 AI 和对手交替落子形成的所有情况穷举出来,这样就形成了一棵树,叫做 博弈树。
但是,穷举出所有情况太不现实了,这颗 博弈树 最后一层节点数就有 225! ,这个数字是特别庞大的,数字10后边要加432个0!!!这程序运行起来,电脑还要不要了?

五子棋AI进阶:极大极小值搜索_第2张图片

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

五子棋AI进阶:极大极小值搜索_第3张图片

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

五子棋AI进阶:极大极小值搜索_第4张图片

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

五子棋AI进阶:极大极小值搜索_第5张图片

AI 落子完后,就轮到对方落子了。在 A1 分支中,对方有 B1 和 B2 两种落子情况(实际有224种)
B1 情况如图所示

五子棋AI进阶:极大极小值搜索_第6张图片

B2 情况如图所示

五子棋AI进阶:极大极小值搜索_第7张图片

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

五子棋AI进阶:极大极小值搜索_第8张图片

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

五子棋AI进阶:极大极小值搜索_第9张图片

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

五子棋AI进阶:极大极小值搜索_第10张图片

则 A3 节点得分为 0,A4 节点得分为 1,A5 节点得分为 3,A6 节点得分为 2。这就很奇怪了,不是说让选得分最大的吗?这怎么都选的最小的得分???
这其实还是要从评估函数说起,因为我们现在的评估函数都是从 AI 角度出发的,评估的得分越高,只会对 AI 有利,对对方来说是不利的。所以,当是对方的分支的时候,我们要选得分最低的节点,因为 AI 要站在对方的角度去做选择,换位思考。这里如果还是没有搞懂的话,我们可以这么理解:

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

五子棋AI进阶:极大极小值搜索_第11张图片

这就是思考角度的问题,对方如果很聪明,那他肯定是选择让 AI 利益最低的一个节点,现在我们就认为对方是一个绝顶聪明的人,所以在对方选择的分支里都选择了分值最低的,好让 AI 的利益受损。
再接下去就是 AI 选择分支了,不用说,AI 肯定选分高的。AI 要从对方给的那些低分分支里选择分最高的,也就是差的里面选好的。所以 B1 得分为 1,B2 得分为 3。

五子棋AI进阶:极大极小值搜索_第12张图片

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

五子棋AI进阶:极大极小值搜索_第13张图片

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

五子棋AI进阶:极大极小值搜索_第14张图片

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

五子棋AI进阶:极大极小值搜索_第15张图片

五子棋AI进阶:极大极小值搜索_第16张图片

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

五子棋AI进阶:极大极小值搜索_第17张图片

代码实现
我们接着上次的代码来,在 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 可以思考两步棋了,所以比之前厉害了许多。

五子棋AI进阶:极大极小值搜索_第18张图片

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

五子棋AI进阶:极大极小值搜索_第19张图片

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

五子棋AI进阶:极大极小值搜索_第20张图片

AI 执白后下的话,连萌新级别的都打不赢,这个应该是评估模型的问题,后续需要对评估模型做进一步的优化。
现在写的搜索算法,如果要让 AI 思考4步棋的话,我这普通电脑还是吃不消的,后续对搜索算法还有更多的优化空间。
源码:github.com/anlingyi/xe…

你可能感兴趣的