likes
comments
collection
share

教你写一个入门级别的五子棋AI

作者站长头像
站长
· 阅读数 25

我报名参加金石计划1期挑战——瓜分10万奖池,这是我的第5篇文章,点击查看活动详情

本文首发于我的个人博客:xeblog.cn/articles/74

前言

本文只是介绍五子棋AI的实现,最终的成品只是一个 AI 接口,并不包括 GUI,且不依赖 GUI

五子棋 AI 的实现并不难,只需要解决一个问题就行:

怎么确定AI的最佳落子位置?

教你写一个入门级别的五子棋AI

一般情况下,五子棋棋盘是由15条横线和15条纵线组合而成的,15x15 的棋盘共有 225 个交叉点,也就是说共有 225 个落子点。

假如说,AI 是黑棋,先行落子,所以 AI 总共有 225 个落子点可以选择,我们可以对每个落子点进行评估打分,哪个分高下哪里,这样我们就能确定最佳落子点了。

但这样又引出了一个新的问题:

怎么对落子点进行评估打分呢?

这就是本文的重点了,请看后文!

教你写一个入门级别的五子棋AI

实现过程

抽象

注:部分基础代码依赖于 lombok,请自行引入,或手写基础代码。

落子位置实体类,这里我们定义棋子类型字段:type1表示黑子,2表示白子。

/**
 * 棋子点位
 *
 * @author anlingyi
 * @date 2021/11/10
 */
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class Point {
    /**
     * 横坐标
     */
    int x;
    /**
     * 纵坐标
     */
    int y;
    /**
     * 棋子类型 1.黑 2.白
     */
    int type;
}

AI 对外提供的接口,不会依赖任何 GUI 代码,方便其他程序调用。

/**
 * 五子棋AI接口
 *
 * @author anlingyi
 * @date 2021/11/10
 */
public interface AIService {

    /**
     * 获取AI棋位
     *
     * @param chessData 已下棋子数据
     * @param point     对手棋位
     * @param started   是否刚开局
     * @return
     */
    Point getPoint(int[][] chessData, Point point, boolean started);

}

这个接口需要知道我们现在的棋盘落子数据 chessData,还有对手上一步的落子位置 pointstarted 参数表示是否是刚开局,后续可能对刚开局情况做单独的处理。

实现AI接口

我们创建一个类 ZhiZhangAIService,这个类实现 AIService 接口,来写我们的实现逻辑。

/**
 *
 * 五子棋AI实现
 *
 * @author anlingyi
 * @date 2021/11/10
 */
public class ZhiZhangAIService implements AIService {

    /**
     * 已下棋子数据
     */
    private int[][] chessData;
    /**
     * 棋盘行数
     */
    private int rows;
    /**
     * 棋盘列数
     */
    private int cols;
    /**
     * AI棋子类型
     */
    private int ai;

    /**
     * 声明一个最大值
     */
    private static final int INFINITY = 999999999;

    @Override
    public Point getPoint(int[][] chessData, Point point, boolean started) {
    	// 初始化棋盘数据
    	initChessData(chessData);
    	// 计算AI的棋子类型
        this.ai = 3 - point.type;

        if (started) {
            // AI先下,首子天元
            int centerX = this.cols / 2;
            int centerY = this.rows / 2;
            return new Point(centerX, centerY, this.ai);
        }

        // 获取最佳下棋点位
        return getBestPoint();
    }

    /**
     * 初始化棋盘数据
     * 
     * @param chessData 当前棋盘数据
     */
    private void initChessData(int[][] chessData) {
    	// 获取棋盘行数
        this.rows = chessData.length;
        // 获取棋盘列数
        this.cols = chessData[0].length;
        // 初始化棋盘数据
        this.chessData = new int[this.cols][this.rows];
        // 深拷贝
        for (int i = 0; i < cols; i++) {
            for (int j = 0; j < rows; j++) {
                this.chessData[i][j] = chessData[i][j];
            }
        }
    }

    /**
     * 获取最佳下棋点位
     *
     * @return
     */
    private Point getBestPoint() {
	Point best = null;
        // 初始分值为最小
        int score = -INFINITY;

        /* 遍历所有能下棋的点位,评估各个点位的分值,选择分值最大的点位 */
        for (int i = 0; i < this.cols; i++) {
            for (int j = 0; j < this.rows; j++) {
                if (this.chessData[i][j] != 0) {
                    // 该点已有棋子,跳过
                    continue;
                }

                Point p = new Point(i, j, this.ai);
                // 评估该点AI得分
                int val = evaluate(p);
                // 选择得分最高的点位
                if (val > score) {
                    // 最高分被刷新
                    score = val;
                    // 更新最佳点位
                    best = p;
                }
            }
        }

        return best;
    }

    /**
     * 对当前棋位进行评估
     *
     * @param point 当前棋位
     * @return
     */
    private int evaluate(Point point) {
    	// 核心
    }

}

首先看 getPoint 方法,这个是 AI 的出入口方法,我们要对传入的棋盘数据做一个初始化,调用 initChessData 方法,计算出当前游戏的棋盘行数、列数,并且拷贝了一份棋子数据到本地(深拷贝还是浅拷贝视情况而定)。

this.ai = 3 - point.type;

这行代码可以计算出AI是执黑子还是执白子,应该很好理解。

if (started) {
    // AI先下,首子天元
    int centerX = this.cols / 2;
    int centerY = this.rows / 2;
    return new Point(centerX, centerY, this.ai);
}

这段代码是处理刚开局时 AI 先行落子的情况,我们这边是简单的将落子点确定为棋盘中心位置(天元)。开局情况的落子我们可以自己定义,并不是固定的,只是说天元的位置比较好而已。

    private Point getBestPoint() {
	Point best = null;
        // 初始分值为最小
        int score = -INFINITY;

        /* 遍历所有能下棋的点位,评估各个点位的分值,选择分值最大的点位 */
        for (int i = 0; i < this.cols; i++) {
            for (int j = 0; j < this.rows; j++) {
                if (this.chessData[i][j] != 0) {
                    // 该点已有棋子,跳过
                    continue;
                }

                Point p = new Point(i, j, this.ai);
                // 评估该点AI得分
                int val = evaluate(p);
                // 选择得分最高的点位
                if (val > score) {
                    // 最高分被刷新
                    score = val;
                    // 更新最佳点位
                    best = p;
                }
            }
        }

        return best;
    }

然后就到了我们最主要的方法了 getBestPoint,这个方法用于选择出 AI 的最佳落子位置。这个方法的思路就是遍历棋盘上所有能下棋的点,然后对这个点进行评分,如果这个点的评分比之前点的评分高,就更新当前最佳落子点位,并更新最高分,所有的落子点都评估完成之后,我们就能确定最好的点位在哪了。

   /**
     * 对当前棋位进行评估
     *
     * @param point 当前棋位
     * @return
     */
    private int evaluate(Point point) {
    	// 核心
    }

最后就是评估函数的实现了。

评估函数

在写评估函数之前,我们要先了解一下五子棋的几种棋型。(还不熟的朋友,五子棋入门了解一下:和那威学五子棋)

在这里,我把五子棋棋型大致分为:连五活四冲四活三眠三活二眠二眠一 等共8种棋型。

0:空位 1:黑子 2:白子

连五:11111
活四:011110
冲四:21111
活三:001110
眠三:211100
活二:001100
眠二:001120
眠一:001200

冲四活三 如果形成,赢的可能性很大,活四 如果形成,棋局胜负基本确定,连五 形成就已经赢了。所以说,如果 AI 落的点能够形成这几种胜率很高的棋型的话,我们要给这个点评一个高分,这样对 AI 最有利。

我这边定义好了各个棋型的分数情况

棋型分数
连五10000000
活四1000000
活三10000
冲四8000
眠三1000
活二800
眠二50
眠一10

评估模型的抽象

我们创建一个枚举内部类,然后定义这几种棋型和它的分数。

    @AllArgsConstructor
    private enum ChessModel {
        /**
         * 连五
         */
        LIANWU(10000000, new String[]{"11111"}),
        /**
         * 活四
         */
        HUOSI(1000000, new String[]{"011110"}),
        /**
         * 活三
         */
        HUOSAN(10000, new String[]{"001110", "011100", "010110", "011010"}),
        /**
         * 冲四
         */
        CHONGSI(8000, new String[]{"11110", "01111", "10111", "11011", "11101"}),
        /**
         * 眠三
         */
        MIANSAN(1000, new String[]{"001112", "010112", "011012", "211100", "211010"}),
        /**
         * 活二
         */
        HUOER(800, new String[]{"001100", "011000", "000110"}),
        /**
         * 眠二
         */
        MIANER(50, new String[]{"011200", "001120", "002110", "021100", "001010", "010100"}),
        /**
         * 眠一
         */
        MIANYI(10, new String[]{"001200", "002100", "020100", "000210", "000120"});

        /**
         * 分数
         */
        int score;
        /**
         * 局势数组
         */
        String[] values;
    }

为了评估方便,我们可以把所有定义好的棋型以及棋型对应的分数存入 Hash 表。

创建一个 LinkedHashMap 类型的类变量 SCORE,然后在静态代码块内进行初始化。

    /**
     * 棋型分数表
     */
    private static final Map<String, Integer> SCORE = new LinkedHashMap<>();

    static {
        // 初始化棋型分数表
        for (ChessModel chessScore : ChessModel.values()) {
            for (String value : chessScore.values) {
                SCORE.put(value, chessScore.score);
            }
        }
    }

判断落子点位的棋型

棋型和分数都定义好了,现在我们要知道一个点位它的棋型的情况,这样才能评估这个点位的分数。

我们以落子点位为中心,分横、纵、左斜、右斜等4个大方向,分别取出各方向的9个点位的棋子,每个方向的9个棋子都组合成一个字符串,然后匹配现有的棋型数据,累积分值,这样就计算出了这个点位的分数了。

教你写一个入门级别的五子棋AI

以上图为例,对横、纵、左斜、右斜做如上操作,可以得出:

横:000111000 -> 活三 +10000
纵:000210000 -> 眠一 +10
左斜:000210000 -> 眠一 +10
右斜:000010000 -> 未匹配到棋型 +0

所以这个点位总得分为:

10000 + 10 + 10 + 0 = 10020

代码实现:

    /**
     * 获取局势分数
     *
     * @param situation 局势
     * @return
     */
    private int getScore(String situation) {
        for (String key : SCORE.keySet()) {
            if (situation.contains(key)) {
                return SCORE.get(key);
            }
        }
        return 0;
    }

    /**
     * 获取棋位局势
     *
     * @param point     当前棋位
     * @param direction 大方向 1.横 2.纵 3.左斜 4.右斜
     * @return
     */
    private String getSituation(Point point, int direction) {
        // 下面用到了relativePoint函数,根据传入的四个大方向做转换
        direction = direction * 2 - 1;
        // 以下是将各个方向的棋子拼接成字符串返回
        StringBuilder sb = new StringBuilder();
        appendChess(sb, point, direction, 4);
        appendChess(sb, point, direction, 3);
        appendChess(sb, point, direction, 2);
        appendChess(sb, point, direction, 1);
        sb.append(1); // 当前棋子统一标记为1(黑)
        appendChess(sb, point, direction + 1, 1);
        appendChess(sb, point, direction + 1, 2);
        appendChess(sb, point, direction + 1, 3);
        appendChess(sb, point, direction + 1, 4);
        return sb.toString();
    }

    /**
     * 拼接各个方向的棋子
     * <p>
     * 由于现有评估模型是对黑棋进行评估
     * 所以,为了方便对局势进行评估,如果当前是白棋方,需要将扫描到的白棋转换为黑棋,黑棋转换为白棋
     * 如:point(x=0,y=0,type=2) 即当前为白棋方
     * 扫描到的某个方向局势为:20212 -> 转换后 -> 10121
     *
     * @param sb        字符串容器
     * @param point     当前棋子
     * @param direction 方向 1.左横 2.右横 3.上纵 4.下纵  5.左斜上 6.左斜下 7.右斜上 8.右斜下
     * @param offset    偏移量
     */
    private void appendChess(StringBuilder sb, Point point, int direction, int offset) {
        int chess = relativePoint(point, direction, offset);
        if (chess > -1) {
            if (point.type == 2) {
                // 对白棋进行转换
                if (chess > 0) {
                    // 对棋子颜色进行转换,2->1,1->2
                    chess = 3 - chess;
                }
            }
            sb.append(chess);
        }
    }

    /**
     * 获取相对点位棋子
     *
     * @param point     当前棋位
     * @param direction 方向 1.左横 2.右横 3.上纵 4.下纵  5.左斜上 6.左斜下 7.右斜上 8.右斜下
     * @param offset    偏移量
     * @return -1:越界 0:空位 1:黑棋 2:白棋
     */
    private int relativePoint(Point point, int direction, int offset) {
        int x = point.x, y = point.y;
        switch (direction) {
            case 1:
                x -= offset;
                break;
            case 2:
                x += offset;
                break;
            case 3:
                y -= offset;
                break;
            case 4:
                y += offset;
                break;
            case 5:
                x += offset;
                y -= offset;
                break;
            case 6:
                x -= offset;
                y += offset;
                break;
            case 7:
                x -= offset;
                y -= offset;
                break;
            case 8:
                x += offset;
                y += offset;
                break;
        }

        if (x < 0 || y < 0 || x >= this.cols || y >= this.rows) {
            // 越界
            return -1;
        }

        // 返回该位置的棋子
        return this.chessData[x][y];
    }

评估函数的实现

到这一步,我们已经能知道某个落子点位的各个方向的局势,又能通过局势获取到对应的分值,这样一来,评估函数就很好写了,评估函数要做的就是累积4个方向的分值,然后返回就行。

    /**
     * 对当前棋位进行评估
     *
     * @param point 当前棋位
     * @return
     */
    private int evaluate(Point point) {
        // 分值
        int score = 0;

        for (int i = 1; i < 5; i++) {
            // 获取该方向的局势
            String situation = getSituation(point, i);
            // 下此步的得分
            score += getScore(situation);
        }

        return score;
    }

现在,已经可以将我们写的 AI 接入GUI 程序做测试了。如果还没有 GUI,也可以自己写个测试方法,只要按照方法的入参信息传入就行,方法输出的就是 AI 下一步的落子位置。

    /**
     * 获取AI棋位
     *
     * @param chessData 已下棋子数据
     * @param point     对手棋位
     * @param started   是否刚开局
     * @return
     */
    Point getPoint(int[][] chessData, Point point, boolean started);

教你写一个入门级别的五子棋AI

测试了一下,现在的 AI 只知道进攻,不知道防守,所以我们需要对 getBestPoint 方法进行优化。之前只对 AI 落子进行了评估,现在我们也要对敌方落子进行评估,然后累积分值,这样可以提高 AI 的防守力度。

    private Point getBestPoint() {
	Point best = null;
        // 初始分值为最小
        int score = -INFINITY;

        /* 遍历所有能下棋的点位,评估各个点位的分值,选择分值最大的点位 */
        for (int i = 0; i < this.cols; i++) {
            for (int j = 0; j < this.rows; j++) {
                if (this.chessData[i][j] != 0) {
                    // 该点已有棋子,跳过
                    continue;
                }

                Point p = new Point(i, j, this.ai);
                // 该点得分 = AI落子得分 + 对手落子得分
                int val = evaluate(p) + evaluate(new Point(i, j, 3 - this.ai));
                // 选择得分最高的点位
                if (val > score) {
                    // 最高分被刷新
                    score = val;
                    // 更新最佳点位
                    best = p;
                }
            }
        }

        return best;
    }

只有这行代码进行了改动,现在加上了对手落子到该点的得分。

// 该点得分 = AI落子得分 + 对手落子得分
int val = evaluate(p) + evaluate(new Point(i, j, 3 - this.ai));

再次测试,现在 AI 棋力还是太一般,防守能力是提高了,但还是输给了我这个“臭棋篓子”。

教你写一个入门级别的五子棋AI

有一些局势的评分需要提高,例如:

  • 活三又活二
  • 冲四又活二
  • 两个或两个以上的活三
  • 冲四又活三

上面这些情况都得加一些分数,如果分数太普通,AI 棋力就会很普通甚至更弱,可以说目前的 AI 只能算是一个刚入门五子棋的新手。

我这边对这些情况的处理是这样的:

  • 活三又活二:总分x2
  • 冲四又活二:总分x4
  • 两个或两个以上的活三:总分x6
  • 冲四又活三:总分x8

新增一个方法,用于判断当前局势是属于什么棋型

    /**
     * 检查当前局势是否处于某个局势
     *
     * @param situation  当前局势
     * @param chessModel 检查的局势
     * @return
     */
    private boolean checkSituation(String situation, ChessModel chessModel) {
        for (String value : chessModel.values) {
            if (situation.contains(value)) {
                return true;
            }
        }
        return false;
    }

修改评估方法 evaluate,对各种棋型做一个统计,最后按照我上面给出的处理规则进行加分处理。

    /**
     * 对当前棋位进行评估
     *
     * @param point 当前棋位
     * @return
     */
    private int evaluate(Point point) {
        // 分值
        int score = 0;
        // 活三数
        int huosanTotal = 0;
        // 冲四数
        int chongsiTotal = 0;
        // 活二数
        int huoerTotal = 0;

        for (int i = 1; i < 5; i++) {
            String situation = getSituation(point, i);
            if (checkSituation(situation, ChessModel.HUOSAN)) {
                // 活三+1
                huosanTotal++;
            } else if (checkSituation(situation, ChessModel.CHONGSI)) {
                // 冲四+1
                chongsiTotal++;
            } else if (checkSituation(situation, ChessModel.HUOER)) {
                // 活二+1
                huoerTotal++;
            }

            // 下此步的得分
            score += getScore(situation);
        }

        if (huosanTotal > 0 && huoerTotal > 0) {
            // 活三又活二
            score *= 2;
        }
        if (chongsiTotal > 0 && huoerTotal > 0) {
            // 冲四又活二
            score *= 4;
        }
        if (huosanTotal > 1) {
            // 活三数大于1
            score *= 6;
        }
        if (chongsiTotal > 0 && huosanTotal > 0) {
            // 冲四又活三
            score *= 8;
        }

        return score;
    }

再次进行测试,AI 棋力已经可以打败我这个菜鸡了,但由于我棋艺不精,打败我不具代表性。

教你写一个入门级别的五子棋AI

在网上找了一个大佬写的五子棋 AIgobang.light7.cn/#/), 我用我写的 AI 去和大佬的 AI 下棋,我的 AI 执黑,只能打败大佬的萌新级别执白的 AI

AI 执黑的情况,赢

教你写一个入门级别的五子棋AI

AI 执白的情况,输

教你写一个入门级别的五子棋AI

由于目前的 AI 只能思考一步棋,所以棋力不强,对方稍微套路一下可能就输了,后续还有很大的优化空间。

源码:github.com/anlingyi/xe…

转载自:https://juejin.cn/post/7143227745164591118
评论
请登录