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

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

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

前言

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

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

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

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

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

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

怎么對落子點進行評估打分呢？

這就是本文的重點了，請看后文！

實現(xiàn)過程

抽象

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

落子位置實體類，這里我們定義棋子類型字段：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 代碼，方便其他程序調(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ù)可能對剛開局情況做單獨的處理。

實現(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);
        }

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

    /**
     * 初始化棋盤數(shù)據(jù)
     * 
     * @param chessData 當前棋盤數(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];
            }
        }
    }

    /**
     * 獲取最佳下棋點位
     *
     * @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 的出入口方法，我們要對傳入的棋盤數(shù)據(jù)做一個初始化，調(diào)用 initChessData 方法，計算出當前游戲的棋盤行數(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 先行落子的情況，我們這邊是簡單的將落子點確定為棋盤中心位置（天元）。開局情況的落子我們可以自己定義，并不是固定的，只是說天元的位置比較好而已。

    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) {
    	// 核心
    }

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

評估函數(shù)

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

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

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

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

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

我這邊定義好了各個棋型的分數(shù)情況

棋型	分數(shù)
連五	10000000
活四	1000000
活三	10000
沖四	8000
眠三	1000
活二	800
眠二	50
眠一	10

評估模型的抽象

我們創(chuàng)建一個枚舉內(nèi)部類，然后定義這幾種棋型和它的分數(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"});

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

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

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

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

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

判斷落子點位的棋型

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

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

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

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

所以這個點位總得分為：

10000 + 10 + 10 + 0 = 10020

代碼實現(xià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     當前棋位
     * @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); // 當前棋子統(tǒng)一標記為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)有評估模型是對黑棋進行評估
     * 所以，為了方便對局勢進行評估，如果當前是白棋方，需要將掃描到的白棋轉(zhuǎn)換為黑棋，黑棋轉(zhuǎn)換為白棋
     * 如：point(x=0,y=0,type=2) 即當前為白棋方
     * 掃描到的某個方向局勢為：20212 -> 轉(zhuǎn)換后 -> 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) {
                // 對白棋進行轉(zhuǎn)換
                if (chess > 0) {
                    // 對棋子顏色進行轉(zhuǎn)換，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];
    }

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

到這一步，我們已經(jīng)能知道某個落子點位的各個方向的局勢，又能通過局勢獲取到對應(yīng)的分值，這樣一來，評估函數(shù)就很好寫了，評估函數(shù)要做的就是累積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;
    }

現(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 只知道進攻，不知道防守，所以我們需要對 getBestPoint 方法進行優(yōu)化。之前只對 AI 落子進行了評估，現(xiàn)在我們也要對敵方落子進行評估，然后累積分值，這樣可以提高 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;
    }

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

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

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

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

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

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

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

活三又活二：總分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，對各種棋型做一個統(tǒng)計，最后按照我上面給出的處理規(guī)則進行加分處理。

    /**
     * 對當前棋位進行評估
     *
     * @param point 當前棋位
     * @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;
    }

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