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

前言

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

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

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

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

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

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

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

这就是本文的重点了，请看后文！

实现过程

抽象

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

落子位置实体类，这里我们定义棋子类型字段：type，1表示黑子，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，还有对手上一步的落子位置 point，started 参数表示是否是刚开局，后续可能对刚开局情况做单独的处理。

实现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 最有利。

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

评估模型的抽象

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

    @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 SCORE = new LinkedHashMap<>();

static {
// 初始化棋型分数表
for (ChessModel chessScore : ChessModel.values()) {
for (String value : chessScore.values) {

                SCORE.put(value, chessScore.score);

            }

        }

    }
,>

判断落子点位的棋型

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

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

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

横：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();

    }

/**

     * 拼接各个方向的棋子

     * 


* 由于现有评估模型是对黑棋进行评估
* 所以，为了方便对局势进行评估，如果当前是白棋方，需要将扫描到的白棋转换为黑棋，黑棋转换为白棋
* 如：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 只知道进攻，不知道防守，所以我们需要对 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 只能算是一个刚入门五子棋的新手。

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

• 
  
• 活三又活二：总分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 （gobang.light7.cn/#/）, 我用我写的 AI 去和大佬的 AI 下棋，我的 AI 执黑，只能打败大佬的萌新级别执白的 AI。

AI 执黑的情况，赢

AI 执白的情况，输

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