1、精選優(yōu)質(zhì)文檔-傾情為你奉上人工智能<五子棋> 技術(shù)報(bào)告簡(jiǎn)介本課程設(shè)計(jì)是基于alpha-beta剪枝算法的五子棋的博弈游戲，具有悔棋，可選擇禁手，支持人機(jī)對(duì)戰(zhàn)，人人對(duì)戰(zhàn)等功能。整個(gè)設(shè)計(jì)基于Java語(yǔ)言開發(fā)，界面美觀大方。 alpha-beta剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計(jì)算評(píng)估各節(jié)點(diǎn)的倒推值，并且根據(jù)評(píng)估出的倒推值范圍，及時(shí)停止擴(kuò)展那些已無必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機(jī)器開銷，提高了搜索效率。具體的剪枝方法如下：(1) 對(duì)于一個(gè)與節(jié)點(diǎn)MIN，若能估計(jì)出其倒推值的上確界，并且這個(gè)值不大于 MIN的父節(jié)點(diǎn)(一定是或節(jié)點(diǎn))的估計(jì)倒推值的下確

2、界，即，則就不必再擴(kuò)展該 MIN節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MIN父節(jié)點(diǎn)的倒推值已無任何影響 了)。這一過程稱為剪枝。(2) 對(duì)于一個(gè)或節(jié)點(diǎn)MAX，若能估計(jì)出其倒推值的下確界，并且這個(gè)值不小于 MAX的父節(jié)點(diǎn)(一定是與節(jié)點(diǎn))的估計(jì)倒推值的上確界，即，則就不必再擴(kuò)展該MAX節(jié)點(diǎn)的其余子節(jié)點(diǎn)了(因?yàn)檫@些節(jié)點(diǎn)的估值對(duì)MAX父節(jié)點(diǎn)的倒推值已無任何影響 了)。這一過程稱為剪枝。1、 數(shù)據(jù)結(jié)構(gòu)定義本文定義15*15的五子棋棋盤，實(shí)現(xiàn)算法，在算法中采用的數(shù)據(jù)結(jié)構(gòu)包括：int isChessOn描述當(dāng)前棋盤，0表示黑子，1表示白字，2表示無子；int pre記錄棋點(diǎn)的x，y坐標(biāo)。由于本課程設(shè)計(jì)是基

3、于Java語(yǔ)言開發(fā)的，在Java中只能用類表示并實(shí)現(xiàn)所定義的數(shù)據(jù)結(jié)構(gòu)。所以下面將用類來描述相應(yīng)的數(shù)據(jù)結(jié)構(gòu)及算法：public class ChessPanelprivate ImageIcon map; /棋盤背景位圖 private ImageIcon blackchess;/黑子位圖 private ImageIcon whitechess;/白子位圖 public int isChessOn ;/棋局 protected boolean win = false; / 是否已經(jīng)分出勝負(fù) protected int win_bw; / 勝利棋色 protected int deep = 3,

4、 weight = 7; / 搜索的深度以及廣度 public int drawn_num = 110; / 和棋步數(shù) int chess_num = 0; / 總落子數(shù)目 public int pre = new intdrawn_num + 12; / 記錄下棋點(diǎn)的x,y坐標(biāo) 最多 (drawn_num + 1) 個(gè) public int sbw = 0; /玩家棋色黑色0，白色1 public int bw = 0; / 當(dāng)前應(yīng)該下的棋色 0：黑色(默認(rèn))， 1：白色 protected int x_max = 15, x_min = 0; / 邊界值,用于速度優(yōu)化 protected

5、int y_max = 15, y_min = 0; / 邊界值,用于速度優(yōu)化 protected boolean able_flag = true; / 是否選擇禁手標(biāo)志 0:無禁手 1:有禁手(默認(rèn) private int h;/棋子長(zhǎng) private int w;/棋子寬 private int insx;/插入棋子的位置 private int insy; private Point mousePoint;/鼠標(biāo)當(dāng)前位置 private int winer;/獲勝方 private boolean humanhuman=false; /是否是人人對(duì)弈 private int plast

6、=0;/走了幾步了， public int BLACK_ONE;/0表黑子 public int WHITE_ONE;/1表白子 public int NONE_ONE;/2表無子public int N;/棋盤邊長(zhǎng)/-搜索當(dāng)前搜索狀態(tài)極大值-/ /alpha 祖先節(jié)點(diǎn)得到的當(dāng)前最小最大值，用于alpha 剪枝 /beta 祖先節(jié)點(diǎn)得到的當(dāng)前最大最小值，用于beta 剪枝。 /step 還要搜索的步數(shù) /return 當(dāng)前搜索子樹極大值 protected int findMax(int alpha, int beta, int step) int max = alpha; if (step

7、= 0) return evaluate(); int rt = getBests(1 - sbw); for (int i = 0; i < rt.length; i+) int x = rti0; int y = rti1; if (getType(x, y, 1 - sbw) = 1) /電腦可取勝 return 100 * ( getMark(1) + step*1000 ); isChessOnxy = 1 - sbw; / 預(yù)存當(dāng)前邊界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; resetMaxMin(x,y)

8、; int t = findMin(max, beta, step - 1); isChessOnxy = 2; / 還原預(yù)設(shè)邊界值 x_min=temp1; x_max=temp2; y_min=temp3; y_max=temp4; if (t > max) max = t; /beta 剪枝 if (max >= beta) return max; return max; /-搜索當(dāng)前搜索狀態(tài)極小值-/ /alpha 祖先節(jié)點(diǎn)得到的當(dāng)前最小最大值，用于alpha 剪枝 /beta 祖先節(jié)點(diǎn)得到的當(dāng)前最大最小值，用于beta 剪枝 /step 還要搜索的步數(shù) /return 當(dāng)

9、前搜索子樹極小值。 protected int findMin(int alpha, int beta, int step) int min = beta; if (step = 0) return evaluate(); int rt = getBests(sbw); for (int i = 0; i < rt.length; i+) int x = rti0; int y = rti1; int type = getType(x, y, sbw); if (type = 1) /玩家成5 return -100 * ( getMark(1) + step*1000 ); / 預(yù)存當(dāng)

10、前邊界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; isChessOnxy = sbw; resetMaxMin(x,y); int t = findMax( alpha, min, step - 1 ); isChessOnxy = 2; / 還原預(yù)設(shè)邊界值 x_min=temp1; x_max=temp2; y_min=temp3; y_max=temp4; if (t < min) min = t; /alpha 剪枝 if (min <= alpha) return min; return min; /-選取局

11、部最優(yōu)的幾個(gè)落子點(diǎn)作為下一次擴(kuò)展的節(jié)點(diǎn)-/ /bwf 棋色 0：黑棋 1：白棋 /return 選出來的節(jié)點(diǎn)坐標(biāo) private int getBests(int bwf) int i_min=(x_min=0 ? x_min:x_min-1); int j_min=(y_min=0 ? y_min:y_min-1); int i_max=(x_max=15 ? x_max:x_max+1); int j_max=(y_max=15 ? y_max:y_max+1); int n = 0; int type_1,type_2; int rt = new int(i_max-i_min) * (

12、j_max-j_min)3; for ( int i = i_min; i < i_max; i+) for (int j = j_min; j < j_max; j+) if (isChessOnij = 2) type_1 = getType(i, j, bwf); type_2 = getType(i, j, 1 - bwf); if(able_flag && bwf=0 && (type_1 = 20 | type_1 = 21 | type_1 = 22) / 禁手棋位置,不記錄 continue; rtn0 = i; rtn1 = j;

13、rtn2 = getMark(type_1) + getMark(type_2); n+; / 對(duì)二維數(shù)組排序 Arrays.sort(rt, new ArrComparator(); int size = weight > n? n:weight; int bests = new intsize3; System.arraycopy(rt, 0, bests, 0, size); return bests; 程序開始2、 程序流程圖顯示界面,繪制棋盤Haveai=true?Y N 與電腦博弈與人博弈 玩家下子（黑）玩家下子音樂控制悔棋重新開始音樂控制悔棋重新開始判斷勝負(fù)，是否禁手玩家下子（白）電腦下棋游戲結(jié)束3、 程序執(zhí)行結(jié)果初始界面人機(jī)博弈人人博弈禁手選擇4、 個(gè)人總結(jié)、看法本程序是