Java實(shí)現(xiàn)AI五子棋游戲的示例代碼
前言
本文只是介紹五子棋AI的實(shí)現(xiàn),最終的成品只是一個(gè) AI 接口,并不包括 GUI,且不依賴 GUI。
五子棋 AI 的實(shí)現(xiàn)并不難,只需要解決一個(gè)問(wèn)題就行:
怎么確定AI的最佳落子位置?
一般情況下,五子棋棋盤是由15條橫線和15條縱線組合而成的,15x15
的棋盤共有 225
個(gè)交叉點(diǎn),也就是說(shuō)共有 225
個(gè)落子點(diǎn)。
假如說(shuō),AI 是黑棋,先行落子,所以 AI 總共有 225
個(gè)落子點(diǎn)可以選擇,我們可以對(duì)每個(gè)落子點(diǎn)進(jìn)行評(píng)估打分,哪個(gè)分高下哪里,這樣我們就能確定最佳落子點(diǎn)了。
但這樣又引出了一個(gè)新的問(wèn)題:
怎么對(duì)落子點(diǎn)進(jìn)行評(píng)估打分呢?
這就是本文的重點(diǎn)了,請(qǐng)看后文!
實(shí)現(xiàn)過(guò)程
抽象
注:部分基礎(chǔ)代碼依賴于 lombok
,請(qǐng)自行引入,或手寫(xiě)基礎(chǔ)代碼。
落子位置實(shí)體類,這里我們定義棋子類型字段: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
對(duì)外提供的接口,不會(huì)依賴任何 GUI
代碼,方便其他程序調(diào)用。
/** * 五子棋AI接口 * * @author anlingyi * @date 2021/11/10 */ public interface AIService { /** * 獲取AI棋位 * * @param chessData 已下棋子數(shù)據(jù) * @param point 對(duì)手棋位 * @param started 是否剛開(kāi)局 * @return */ Point getPoint(int[][] chessData, Point point, boolean started); }
這個(gè)接口需要知道我們現(xiàn)在的棋盤落子數(shù)據(jù) chessData
,還有對(duì)手上一步的落子位置 point
,started
參數(shù)表示是否是剛開(kāi)局,后續(xù)可能對(duì)剛開(kāi)局情況做單獨(dú)的處理。
實(shí)現(xiàn)AI接口
我們創(chuàng)建一個(gè)類 ZhiZhangAIService
,這個(gè)類實(shí)現(xiàn) AIService
接口,來(lái)寫(xiě)我們的實(shí)現(xiàn)邏輯。
/** * * 五子棋AI實(shí)現(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; /** * 聲明一個(gè)最大值 */ private static final int INFINITY = 999999999; @Override public Point getPoint(int[][] chessData, Point point, boolean started) { // 初始化棋盤數(shù)據(jù) initChessData(chessData); // 計(jì)算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)位,評(píng)估各個(gè)點(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)已有棋子,跳過(guò) continue; } Point p = new Point(i, j, this.ai); // 評(píng)估該點(diǎn)AI得分 int val = evaluate(p); // 選擇得分最高的點(diǎn)位 if (val > score) { // 最高分被刷新 score = val; // 更新最佳點(diǎn)位 best = p; } } } return best; } /** * 對(duì)當(dāng)前棋位進(jìn)行評(píng)估 * * @param point 當(dāng)前棋位 * @return */ private int evaluate(Point point) { // 核心 } }
首先看 getPoint
方法,這個(gè)是 AI
的出入口方法,我們要對(duì)傳入的棋盤數(shù)據(jù)做一個(gè)初始化,調(diào)用 initChessData
方法,計(jì)算出當(dāng)前游戲的棋盤行數(shù)、列數(shù),并且拷貝了一份棋子數(shù)據(jù)到本地(深拷貝還是淺拷貝視情況而定)。
this.ai = 3 - point.type;
這行代碼可以計(jì)算出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); }
這段代碼是處理剛開(kāi)局時(shí) AI
先行落子的情況,我們這邊是簡(jiǎn)單的將落子點(diǎn)確定為棋盤中心位置(天元)。開(kāi)局情況的落子我們可以自己定義,并不是固定的,只是說(shuō)天元的位置比較好而已。
private Point getBestPoint() { Point best = null; // 初始分值為最小 int score = -INFINITY; /* 遍歷所有能下棋的點(diǎn)位,評(píng)估各個(gè)點(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)已有棋子,跳過(guò) continue; } Point p = new Point(i, j, this.ai); // 評(píng)估該點(diǎn)AI得分 int val = evaluate(p); // 選擇得分最高的點(diǎn)位 if (val > score) { // 最高分被刷新 score = val; // 更新最佳點(diǎn)位 best = p; } } } return best; }
然后就到了我們最主要的方法了 getBestPoint
,這個(gè)方法用于選擇出 AI
的最佳落子位置。這個(gè)方法的思路就是遍歷棋盤上所有能下棋的點(diǎn),然后對(duì)這個(gè)點(diǎn)進(jìn)行評(píng)分,如果這個(gè)點(diǎn)的評(píng)分比之前點(diǎn)的評(píng)分高,就更新當(dāng)前最佳落子點(diǎn)位,并更新最高分,所有的落子點(diǎn)都評(píng)估完成之后,我們就能確定最好的點(diǎn)位在哪了。
/** * 對(duì)當(dāng)前棋位進(jìn)行評(píng)估 * * @param point 當(dāng)前棋位 * @return */ private int evaluate(Point point) { // 核心 }
最后就是評(píng)估函數(shù)的實(shí)現(xiàn)了。
評(píng)估函數(shù)
在寫(xiě)評(píng)估函數(shù)之前,我們要先了解一下五子棋的幾種棋型。(還不熟的朋友,五子棋入門了解一下:和那威學(xué)五子棋)
在這里,我把五子棋棋型大致分為:連五、活四、沖四、活三、眠三、活二、眠二、眠一 等共8種棋型。
0:空位 1:黑子 2:白子
連五:11111
活四:011110
沖四:21111
活三:001110
眠三:211100
活二:001100
眠二:001120
眠一:001200
沖四、活三 如果形成,贏的可能性很大,活四 如果形成,棋局勝負(fù)基本確定,連五 形成就已經(jīng)贏了。所以說(shuō),如果 AI
落的點(diǎn)能夠形成這幾種勝率很高的棋型的話,我們要給這個(gè)點(diǎn)評(píng)一個(gè)高分,這樣對(duì) AI
最有利。
我這邊定義好了各個(gè)棋型的分?jǐn)?shù)情況
棋型 | 分?jǐn)?shù) |
---|---|
連五 | 10000000 |
活四 | 1000000 |
活三 | 10000 |
沖四 | 8000 |
眠三 | 1000 |
活二 | 800 |
眠二 | 50 |
眠一 | 10 |
評(píng)估模型的抽象
我們創(chuàng)建一個(gè)枚舉內(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ì)數(shù)組 */ String[] values; }
為了評(píng)估方便,我們可以把所有定義好的棋型以及棋型對(duì)應(yīng)的分?jǐn)?shù)存入 Hash
表。
創(chuàng)建一個(gè) 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)在我們要知道一個(gè)點(diǎn)位它的棋型的情況,這樣才能評(píng)估這個(gè)點(diǎn)位的分?jǐn)?shù)。
我們以落子點(diǎn)位為中心,分橫、縱、左斜、右斜等4個(gè)大方向,分別取出各方向的9個(gè)點(diǎn)位的棋子,每個(gè)方向的9個(gè)棋子都組合成一個(gè)字符串,然后匹配現(xiàn)有的棋型數(shù)據(jù),累積分值,這樣就計(jì)算出了這個(gè)點(diǎn)位的分?jǐn)?shù)了。
以上圖為例,對(duì)橫、縱、左斜、右斜做如上操作,可以得出:
橫:000111000 -> 活三 +10000
縱:000210000 -> 眠一 +10
左斜:000210000 -> 眠一 +10
右斜:000010000 -> 未匹配到棋型 +0
所以這個(gè)點(diǎn)位總得分為:
10000 + 10 + 10 + 0 = 10020
代碼實(shí)現(xiàn):
/** * 獲取局勢(shì)分?jǐn)?shù) * * @param situation 局勢(shì) * @return */ private int getScore(String situation) { for (String key : SCORE.keySet()) { if (situation.contains(key)) { return SCORE.get(key); } } return 0; } /** * 獲取棋位局勢(shì) * * @param point 當(dāng)前棋位 * @param direction 大方向 1.橫 2.縱 3.左斜 4.右斜 * @return */ private String getSituation(Point point, int direction) { // 下面用到了relativePoint函數(shù),根據(jù)傳入的四個(gè)大方向做轉(zhuǎn)換 direction = direction * 2 - 1; // 以下是將各個(gè)方向的棋子拼接成字符串返回 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(); } /** * 拼接各個(gè)方向的棋子 * <p> * 由于現(xiàn)有評(píng)估模型是對(duì)黑棋進(jìn)行評(píng)估 * 所以,為了方便對(duì)局勢(shì)進(jìn)行評(píng)估,如果當(dāng)前是白棋方,需要將掃描到的白棋轉(zhuǎn)換為黑棋,黑棋轉(zhuǎn)換為白棋 * 如:point(x=0,y=0,type=2) 即當(dāng)前為白棋方 * 掃描到的某個(gè)方向局勢(shì)為: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) { // 對(duì)白棋進(jìn)行轉(zhuǎn)換 if (chess > 0) { // 對(duì)棋子顏色進(jìn)行轉(zhuǎn)換,2->1,1->2 chess = 3 - chess; } } sb.append(chess); } } /** * 獲取相對(duì)點(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]; }
評(píng)估函數(shù)的實(shí)現(xiàn)
到這一步,我們已經(jīng)能知道某個(gè)落子點(diǎn)位的各個(gè)方向的局勢(shì),又能通過(guò)局勢(shì)獲取到對(duì)應(yīng)的分值,這樣一來(lái),評(píng)估函數(shù)就很好寫(xiě)了,評(píng)估函數(shù)要做的就是累積4個(gè)方向的分值,然后返回就行。
/** * 對(duì)當(dāng)前棋位進(jìn)行評(píng)估 * * @param point 當(dāng)前棋位 * @return */ private int evaluate(Point point) { // 分值 int score = 0; for (int i = 1; i < 5; i++) { // 獲取該方向的局勢(shì) String situation = getSituation(point, i); // 下此步的得分 score += getScore(situation); } return score; }
現(xiàn)在,已經(jīng)可以將我們寫(xiě)的 AI
接入GUI
程序做測(cè)試了。如果還沒(méi)有 GUI
,也可以自己寫(xiě)個(gè)測(cè)試方法,只要按照方法的入?yún)⑿畔魅刖托?,方法輸出的就?AI
下一步的落子位置。
/** * 獲取AI棋位 * * @param chessData 已下棋子數(shù)據(jù) * @param point 對(duì)手棋位 * @param started 是否剛開(kāi)局 * @return */ Point getPoint(int[][] chessData, Point point, boolean started);
測(cè)試了一下,現(xiàn)在的 AI
只知道進(jìn)攻,不知道防守,所以我們需要對(duì) getBestPoint
方法進(jìn)行優(yōu)化。之前只對(duì) AI
落子進(jìn)行了評(píng)估,現(xiàn)在我們也要對(duì)敵方落子進(jìn)行評(píng)估,然后累積分值,這樣可以提高 AI
的防守力度。
private Point getBestPoint() { Point best = null; // 初始分值為最小 int score = -INFINITY; /* 遍歷所有能下棋的點(diǎn)位,評(píng)估各個(gè)點(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)已有棋子,跳過(guò) continue; } Point p = new Point(i, j, this.ai); // 該點(diǎn)得分 = AI落子得分 + 對(duì)手落子得分 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)行了改動(dòng),現(xiàn)在加上了對(duì)手落子到該點(diǎn)的得分。
// 該點(diǎn)得分 = AI落子得分 + 對(duì)手落子得分 int val = evaluate(p) + evaluate(new Point(i, j, 3 - this.ai));
再次測(cè)試,現(xiàn)在 AI
棋力還是太一般,防守能力是提高了,但還是輸給了我這個(gè)“臭棋簍子”。
有一些局勢(shì)的評(píng)分需要提高,例如:
- 活三又活二
- 沖四又活二
- 兩個(gè)或兩個(gè)以上的活三
- 沖四又活三
上面這些情況都得加一些分?jǐn)?shù),如果分?jǐn)?shù)太普通,AI
棋力就會(huì)很普通甚至更弱,可以說(shuō)目前的 AI
只能算是一個(gè)剛?cè)腴T五子棋的新手。
我這邊對(duì)這些情況的處理是這樣的:
- 活三又活二:總分x2
- 沖四又活二:總分x4
- 兩個(gè)或兩個(gè)以上的活三:總分x6
- 沖四又活三:總分x8
新增一個(gè)方法,用于判斷當(dāng)前局勢(shì)是屬于什么棋型
/** * 檢查當(dāng)前局勢(shì)是否處于某個(gè)局勢(shì) * * @param situation 當(dāng)前局勢(shì) * @param chessModel 檢查的局勢(shì) * @return */ private boolean checkSituation(String situation, ChessModel chessModel) { for (String value : chessModel.values) { if (situation.contains(value)) { return true; } } return false; }
修改評(píng)估方法 evaluate
,對(duì)各種棋型做一個(gè)統(tǒng)計(jì),最后按照我上面給出的處理規(guī)則進(jìn)行加分處理。
/** * 對(duì)當(dāng)前棋位進(jìn)行評(píng)估 * * @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)行測(cè)試,AI
棋力已經(jīng)可以打敗我這個(gè)菜雞了,但由于我棋藝不精,打敗我不具代表性。
在網(wǎng)上找了一個(gè)大佬寫(xiě)的五子棋 AI
(gobang.light7.cn/#/), 我用我寫(xiě)的 AI
去和大佬的 AI
下棋,我的 AI
執(zhí)黑,只能打敗大佬的萌新級(jí)別執(zhí)白的 AI
。
AI 執(zhí)黑的情況,贏
AI 執(zhí)白的情況,輸
由于目前的 AI
只能思考一步棋,所以棋力不強(qiáng),對(duì)方稍微套路一下可能就輸了,后續(xù)還有很大的優(yōu)化空間。
以上就是Java實(shí)現(xiàn)AI五子棋游戲的示例代碼的詳細(xì)內(nèi)容,更多關(guān)于Java AI五子棋的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
java實(shí)現(xiàn)excel導(dǎo)入數(shù)據(jù)的工具類
這篇文章主要介紹了java實(shí)現(xiàn)的excel導(dǎo)入數(shù)據(jù)的工具類,需要的朋友可以參考下2014-03-03springboot使用ThreadPoolTaskExecutor多線程批量插入百萬(wàn)級(jí)數(shù)據(jù)的實(shí)現(xiàn)方法
這篇文章主要介紹了springboot利用ThreadPoolTaskExecutor多線程批量插入百萬(wàn)級(jí)數(shù)據(jù),本文通過(guò)示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-02-02Java橋接模式實(shí)例詳解【簡(jiǎn)單版與升級(jí)版】
這篇文章主要介紹了Java橋接模式,結(jié)合實(shí)例形式分析了java橋接模式簡(jiǎn)單版與升級(jí)版兩種實(shí)現(xiàn)技巧,需要的朋友可以參考下2019-07-07Java 數(shù)組內(nèi)置函數(shù)toArray詳解
這篇文章主要介紹了Java 數(shù)組內(nèi)置函數(shù)toArray詳解,文本詳細(xì)的講解了toArray底層的代碼和文檔,需要的朋友可以參考下2021-06-06從底層源碼深入分析Spring的IoC容器的實(shí)現(xiàn)原理
IoC容器負(fù)責(zé)管理對(duì)象的生命周期和依賴關(guān)系,大大簡(jiǎn)化了應(yīng)用程序的開(kāi)發(fā)和維,我們這篇文章將會(huì)從底層源碼的角度深入分析Spring的IoC容器實(shí)現(xiàn),探索它的工作原理和關(guān)鍵組件,需要的朋友可以參考下2023-07-07java字符串比較獲取字符串出現(xiàn)次數(shù)的示例
java獲取一個(gè)字符串在整個(gè)字符串出現(xiàn)的次數(shù),下面寫(xiě)出我的思路和二個(gè)實(shí)現(xiàn)方法,大家參考使用吧2014-01-01