Java實現(xiàn)AI五子棋游戲的示例代碼

更新時間：2022年09月15日 15:50:56 作者：AnLingYi

本文只是介紹五子棋AI的實現(xiàn)，最終的成品只是一個?AI?接口，并不包括?GUI，且不依賴?GUI，文中的示例代碼講解詳細(xì)，感興趣的可以嘗試一下

前言

本文只是介紹五子棋AI的實現(xiàn)，最終的成品只是一個 AI 接口，并不包括 GUI，且不依賴 GUI。

五子棋 AI 的實現(xiàn)并不難，只需要解決一個問題就行：

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

一般情況下，五子棋棋盤是由15條橫線和15條縱線組合而成的，15x15 的棋盤共有 225 個交叉點(diǎn)，也就是說共有 225 個落子點(diǎn)。

假如說，AI 是黑棋，先行落子，所以 AI 總共有 225 個落子點(diǎn)可以選擇，我們可以對每個落子點(diǎn)進(jìn)行評估打分，哪個分高下哪里，這樣我們就能確定最佳落子點(diǎn)了。

但這樣又引出了一個新的問題：

怎么對落子點(diǎn)進(jìn)行評估打分呢？

這就是本文的重點(diǎn)了，請看后文！

實現(xiàn)過程

抽象

注：部分基礎(chǔ)代碼依賴于 lombok，請自行引入，或手寫基礎(chǔ)代碼。

落子位置實體類，這里我們定義棋子類型字段：type，1表示黑子，2表示白子。

/**
 * 棋子點(diǎn)位
 *
 * @author anlingyi
 * @date 2021/11/10
 */
@AllArgsConstructor
@NoArgsConstructor
@ToString
public class Point {
    /**
     * 橫坐標(biāo)
     */
    int x;
    /**
     * 縱坐標(biāo)
     */
    int y;
    /**
     * 棋子類型 1.黑 2.白
     */
    int type;
}

AI 對外提供的接口，不會依賴任何 GUI 代碼，方便其他程序調(diào)用。

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

    /**
     * 獲取AI棋位
     *
     * @param chessData 已下棋子數(shù)據(jù)
     * @param point     對手棋位
     * @param started   是否剛開局
     * @return
     */
    Point getPoint(int[][] chessData, Point point, boolean started);

}

這個接口需要知道我們現(xiàn)在的棋盤落子數(shù)據(jù) chessData，還有對手上一步的落子位置 point，started 參數(shù)表示是否是剛開局，后續(xù)可能對剛開局情況做單獨(dú)的處理。

實現(xiàn)AI接口

我們創(chuàng)建一個類 ZhiZhangAIService，這個類實現(xiàn) AIService 接口，來寫我們的實現(xiàn)邏輯。

/**
 *
 * 五子棋AI實現(xiàn)
 *
 * @author anlingyi
 * @date 2021/11/10
 */
public class ZhiZhangAIService implements AIService {

    /**
     * 已下棋子數(shù)據(jù)
     */
    private int[][] chessData;
    /**
     * 棋盤行數(shù)
     */
    private int rows;
    /**
     * 棋盤列數(shù)
     */
    private int cols;
    /**
     * AI棋子類型
     */
    private int ai;

    /**
     * 聲明一個最大值
     */
    private static final int INFINITY = 999999999;

    @Override
    public Point getPoint(int[][] chessData, Point point, boolean started) {
    	// 初始化棋盤數(shù)據(jù)
    	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);
        }

        // 獲取最佳下棋點(diǎn)位
        return getBestPoint();
    }

    /**
     * 初始化棋盤數(shù)據(jù)
     * 
     * @param chessData 當(dāng)前棋盤數(shù)據(jù)
     */
    private void initChessData(int[][] chessData) {
    	// 獲取棋盤行數(shù)
        this.rows = chessData.length;
        // 獲取棋盤列數(shù)
        this.cols = chessData[0].length;
        // 初始化棋盤數(shù)據(jù)
        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];
            }
        }
    }

    /**
     * 獲取最佳下棋點(diǎn)位
     *
     * @return
     */
    private Point getBestPoint() {
	Point best = null;
        // 初始分值為最小
        int score = -INFINITY;

        /* 遍歷所有能下棋的點(diǎn)位，評估各個點(diǎn)位的分值，選擇分值最大的點(diǎn)位 */
        for (int i = 0; i < this.cols; i++) {
            for (int j = 0; j < this.rows; j++) {
                if (this.chessData[i][j] != 0) {
                    // 該點(diǎn)已有棋子，跳過
                    continue;
                }

                Point p = new Point(i, j, this.ai);
                // 評估該點(diǎn)AI得分
                int val = evaluate(p);
                // 選擇得分最高的點(diǎn)位
                if (val > score) {
                    // 最高分被刷新
                    score = val;
                    // 更新最佳點(diǎn)位
                    best = p;
                }
            }
        }

        return best;
    }

    /**
     * 對當(dāng)前棋位進(jìn)行評估
     *
     * @param point 當(dāng)前棋位
     * @return
     */
    private int evaluate(Point point) {
    	// 核心
    }

}

首先看 getPoint 方法，這個是 AI 的出入口方法，我們要對傳入的棋盤數(shù)據(jù)做一個初始化，調(diào)用 initChessData 方法，計算出當(dāng)前游戲的棋盤行數(shù)、列數(shù)，并且拷貝了一份棋子數(shù)據(jù)到本地（深拷貝還是淺拷貝視情況而定）。

this.ai = 3 - point.type;

這行代碼可以計算出AI是執(zhí)黑子還是執(zhí)白子，應(yīng)該很好理解。

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

這段代碼是處理剛開局時 AI 先行落子的情況，我們這邊是簡單的將落子點(diǎn)確定為棋盤中心位置（天元）。開局情況的落子我們可以自己定義，并不是固定的，只是說天元的位置比較好而已。

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

        /* 遍歷所有能下棋的點(diǎn)位，評估各個點(diǎn)位的分值，選擇分值最大的點(diǎn)位 */
        for (int i = 0; i < this.cols; i++) {
            for (int j = 0; j < this.rows; j++) {
                if (this.chessData[i][j] != 0) {
                    // 該點(diǎn)已有棋子，跳過
                    continue;
                }

                Point p = new Point(i, j, this.ai);
                // 評估該點(diǎn)AI得分
                int val = evaluate(p);
                // 選擇得分最高的點(diǎn)位
                if (val > score) {
                    // 最高分被刷新
                    score = val;
                    // 更新最佳點(diǎn)位
                    best = p;
                }
            }
        }

        return best;
    }

然后就到了我們最主要的方法了 getBestPoint，這個方法用于選擇出 AI 的最佳落子位置。這個方法的思路就是遍歷棋盤上所有能下棋的點(diǎn)，然后對這個點(diǎn)進(jìn)行評分，如果這個點(diǎn)的評分比之前點(diǎn)的評分高，就更新當(dāng)前最佳落子點(diǎn)位，并更新最高分，所有的落子點(diǎn)都評估完成之后，我們就能確定最好的點(diǎn)位在哪了。

   /**
     * 對當(dāng)前棋位進(jìn)行評估
     *
     * @param point 當(dāng)前棋位
     * @return
     */
    private int evaluate(Point point) {
    	// 核心
    }

最后就是評估函數(shù)的實現(xiàn)了。

評估函數(shù)

在寫評估函數(shù)之前，我們要先了解一下五子棋的幾種棋型。(還不熟的朋友，五子棋入門了解一下：和那威學(xué)五子棋)

在這里，我把五子棋棋型大致分為：連五、活四、沖四、活三、眠三、活二、眠二、眠一等共8種棋型。

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

連五：11111
活四：011110
沖四：21111
活三：001110
眠三：211100
活二：001100
眠二：001120
眠一：001200

沖四、活三如果形成，贏的可能性很大，活四如果形成，棋局勝負(fù)基本確定，連五形成就已經(jīng)贏了。所以說，如果 AI 落的點(diǎn)能夠形成這幾種勝率很高的棋型的話，我們要給這個點(diǎn)評一個高分，這樣對 AI 最有利。

我這邊定義好了各個棋型的分?jǐn)?shù)情況

棋型	分?jǐn)?shù)
連五	10000000
活四	1000000
活三	10000
沖四	8000
眠三	1000
活二	800
眠二	50
眠一	10

評估模型的抽象

我們創(chuàng)建一個枚舉內(nèi)部類，然后定義這幾種棋型和它的分?jǐn)?shù)。

    @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"});

        /**
         * 分?jǐn)?shù)
         */
        int score;
        /**
         * 局勢數(shù)組
         */
        String[] values;
    }

為了評估方便，我們可以把所有定義好的棋型以及棋型對應(yīng)的分?jǐn)?shù)存入 Hash 表。

創(chuàng)建一個 LinkedHashMap 類型的類變量 SCORE，然后在靜態(tài)代碼塊內(nèi)進(jìn)行初始化。

    /**
     * 棋型分?jǐn)?shù)表
     */
    private static final Map<String, Integer> SCORE = new LinkedHashMap<>();

    static {
        // 初始化棋型分?jǐn)?shù)表
        for (ChessModel chessScore : ChessModel.values()) {
            for (String value : chessScore.values) {
                SCORE.put(value, chessScore.score);
            }
        }
    }

判斷落子點(diǎn)位的棋型

棋型和分?jǐn)?shù)都定義好了，現(xiàn)在我們要知道一個點(diǎn)位它的棋型的情況，這樣才能評估這個點(diǎn)位的分?jǐn)?shù)。

我們以落子點(diǎn)位為中心，分橫、縱、左斜、右斜等4個大方向，分別取出各方向的9個點(diǎn)位的棋子，每個方向的9個棋子都組合成一個字符串，然后匹配現(xiàn)有的棋型數(shù)據(jù)，累積分值，這樣就計算出了這個點(diǎn)位的分?jǐn)?shù)了。

以上圖為例，對橫、縱、左斜、右斜做如上操作，可以得出：

橫：000111000 -> 活三 +10000
縱：000210000 -> 眠一 +10
左斜：000210000 -> 眠一 +10
右斜：000010000 -> 未匹配到棋型 +0

所以這個點(diǎn)位總得分為：

10000 + 10 + 10 + 0 = 10020

代碼實現(xiàn)：

    /**
     * 獲取局勢分?jǐn)?shù)
     *
     * @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     當(dāng)前棋位
     * @param direction 大方向 1.橫 2.縱 3.左斜 4.右斜
     * @return
     */
    private String getSituation(Point point, int direction) {
        // 下面用到了relativePoint函數(shù)，根據(jù)傳入的四個大方向做轉(zhuǎn)換
        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); // 當(dāng)前棋子統(tǒng)一標(biāo)記為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>
     * 由于現(xiàn)有評估模型是對黑棋進(jìn)行評估
     * 所以，為了方便對局勢進(jìn)行評估，如果當(dāng)前是白棋方，需要將掃描到的白棋轉(zhuǎn)換為黑棋，黑棋轉(zhuǎn)換為白棋
     * 如：point(x=0,y=0,type=2) 即當(dāng)前為白棋方
     * 掃描到的某個方向局勢為：20212 -> 轉(zhuǎn)換后 -> 10121
     *
     * @param sb        字符串容器
     * @param point     當(dāng)前棋子
     * @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) {
                // 對白棋進(jìn)行轉(zhuǎn)換
                if (chess > 0) {
                    // 對棋子顏色進(jìn)行轉(zhuǎn)換，2->1，1->2
                    chess = 3 - chess;
                }
            }
            sb.append(chess);
        }
    }

    /**
     * 獲取相對點(diǎn)位棋子
     *
     * @param point     當(dāng)前棋位
     * @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];
    }

評估函數(shù)的實現(xiàn)

到這一步，我們已經(jīng)能知道某個落子點(diǎn)位的各個方向的局勢，又能通過局勢獲取到對應(yīng)的分值，這樣一來，評估函數(shù)就很好寫了，評估函數(shù)要做的就是累積4個方向的分值，然后返回就行。

    /**
     * 對當(dāng)前棋位進(jìn)行評估
     *
     * @param point 當(dāng)前棋位
     * @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;
    }

現(xiàn)在，已經(jīng)可以將我們寫的 AI 接入GUI 程序做測試了。如果還沒有 GUI，也可以自己寫個測試方法，只要按照方法的入?yún)⑿畔魅刖托?，方法輸出的就?AI 下一步的落子位置。

    /**
     * 獲取AI棋位
     *
     * @param chessData 已下棋子數(shù)據(jù)
     * @param point     對手棋位
     * @param started   是否剛開局
     * @return
     */
    Point getPoint(int[][] chessData, Point point, boolean started);

測試了一下，現(xiàn)在的 AI 只知道進(jìn)攻，不知道防守，所以我們需要對 getBestPoint 方法進(jìn)行優(yōu)化。之前只對 AI 落子進(jìn)行了評估，現(xiàn)在我們也要對敵方落子進(jìn)行評估，然后累積分值，這樣可以提高 AI 的防守力度。

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

        /* 遍歷所有能下棋的點(diǎn)位，評估各個點(diǎn)位的分值，選擇分值最大的點(diǎn)位 */
        for (int i = 0; i < this.cols; i++) {
            for (int j = 0; j < this.rows; j++) {
                if (this.chessData[i][j] != 0) {
                    // 該點(diǎn)已有棋子，跳過
                    continue;
                }

                Point p = new Point(i, j, this.ai);
                // 該點(diǎn)得分 = AI落子得分 + 對手落子得分
                int val = evaluate(p) + evaluate(new Point(i, j, 3 - this.ai));
                // 選擇得分最高的點(diǎn)位
                if (val > score) {
                    // 最高分被刷新
                    score = val;
                    // 更新最佳點(diǎn)位
                    best = p;
                }
            }
        }

        return best;
    }

只有這行代碼進(jìn)行了改動，現(xiàn)在加上了對手落子到該點(diǎn)的得分。

// 該點(diǎn)得分 = AI落子得分 + 對手落子得分
int val = evaluate(p) + evaluate(new Point(i, j, 3 - this.ai));

再次測試，現(xiàn)在 AI 棋力還是太一般，防守能力是提高了，但還是輸給了我這個“臭棋簍子”。

有一些局勢的評分需要提高，例如：

活三又活二
沖四又活二
兩個或兩個以上的活三
沖四又活三

上面這些情況都得加一些分?jǐn)?shù)，如果分?jǐn)?shù)太普通，AI 棋力就會很普通甚至更弱，可以說目前的 AI 只能算是一個剛?cè)腴T五子棋的新手。

我這邊對這些情況的處理是這樣的：

活三又活二：總分x2
沖四又活二：總分x4
兩個或兩個以上的活三：總分x6
沖四又活三：總分x8

新增一個方法，用于判斷當(dāng)前局勢是屬于什么棋型

    /**
     * 檢查當(dāng)前局勢是否處于某個局勢
     *
     * @param situation  當(dāng)前局勢
     * @param chessModel 檢查的局勢
     * @return
     */
    private boolean checkSituation(String situation, ChessModel chessModel) {
        for (String value : chessModel.values) {
            if (situation.contains(value)) {
                return true;
            }
        }
        return false;
    }

修改評估方法 evaluate，對各種棋型做一個統(tǒng)計，最后按照我上面給出的處理規(guī)則進(jìn)行加分處理。

    /**
     * 對當(dāng)前棋位進(jìn)行評估
     *
     * @param point 當(dāng)前棋位
     * @return
     */
    private int evaluate(Point point) {
        // 分值
        int score = 0;
        // 活三數(shù)
        int huosanTotal = 0;
        // 沖四數(shù)
        int chongsiTotal = 0;
        // 活二數(shù)
        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) {
            // 活三數(shù)大于1
            score *= 6;
        }
        if (chongsiTotal > 0 && huosanTotal > 0) {
            // 沖四又活三
            score *= 8;
        }

        return score;
    }

再次進(jìn)行測試，AI 棋力已經(jīng)可以打敗我這個菜雞了，但由于我棋藝不精，打敗我不具代表性。