人工智能課程設(shè)計

1、人工智能技術(shù)報告簡介本課程設(shè)計是基于alpha-beta剪枝算法的五子棋的博弈游戲，具有悔棋，可選擇禁手，支持人機對戰(zhàn)，人人對戰(zhàn)等功能。整個設(shè)計基于Java語言開發(fā)，界面美觀大方。alpha-beta剪枝技術(shù)的基本思想或算法是，邊生成博弈樹邊計算評估各節(jié)點的倒推值，并且根據(jù)評估出的倒推值范圍，及時停止擴展那些已無必要再擴展的子節(jié)點，即相當(dāng)于剪去了博弈樹上的一些分枝，從而節(jié)約了機器開銷，提高了搜索效率。具體的剪枝方法如下：（1）對于一個與節(jié)點MIN,若能估計出其倒推值的上確界卩，并且這個卩值不大于MIN的父節(jié)點（一定是或節(jié)點）的估計倒推值的下確界a，即ap，則就不必再擴展該MIN節(jié)點的其余子節(jié)點

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

3、實現(xiàn)所定義的數(shù)據(jù)結(jié)構(gòu)。所以下面將用類來描述相應(yīng)的數(shù)據(jù)結(jié)構(gòu)及算法：/棋盤背景位圖/黑子位圖/白子位圖/棋局/是否已經(jīng)分出勝負/勝利棋色/搜索的深度以及廣度/和棋步數(shù)/總落子數(shù)目publicclassChessPanelprivateImageIconmap;privateImageIconblackchess;privateImageIconwhitechess;publicintisChessOn;protectedbooleanwin=false;protectedintwin_bw;protectedintdeep=3,weight=7;publicintdrawn_num=110;int

4、chess_num=0;publicintpre=newintdrawn_num+12;/記錄下棋點的x,y坐標最多（drawn_num+1）個publicintsbw=0;/玩家棋色黑色0，白色1publicintbw=0;/當(dāng)前應(yīng)該下的棋色0：黑色（默認），1：白色protectedintx_max=15,x_min=0;/邊界值,用于速度優(yōu)化protectedinty_max=15,y_min=0;/邊界值,用于速度優(yōu)化protectedbooleanable_flag=true;/是否選擇禁手標志0:無禁手1:有禁手（默認privateinth;/棋子長privateintw;priv

5、ateintinsx;privateintinsy;privatePointmousePoint;privateintwiner;privatebooleanhumanhuman=false;privateintplast=0;publicintBLACK_ONE;publicintWHITE_ONE;publicintNONE_ONE;publicintN;/搜索當(dāng)前搜索狀態(tài)極大值-/棋子寬/插入棋子的位置/鼠標當(dāng)前位置/獲勝方/是否是人人對弈/走了幾步了，/0表黑子/1表白子/2表無子/棋盤邊長/alpha祖先節(jié)點得到的當(dāng)前最小最大值，用于alpha剪枝/beta祖先節(jié)點得到的當(dāng)前最大最小

6、值，用于beta剪枝。/step還要搜索的步數(shù)/return當(dāng)前搜索子樹極大值protectedintfindMax(intalpha,intbeta,intstep)intmax=alpha;if(step=0)returnevaluate();intrt=getBests(1-sbw);for(inti=0;imax)max=t;/beta剪枝if(max=beta)returnmax;returnmax;/搜索當(dāng)前搜索狀態(tài)極小值/alpha祖先節(jié)點得到的當(dāng)前最小最大值，用于alpha剪枝/beta祖先節(jié)點得到的當(dāng)前最大最小值，用于beta剪枝/step還要搜索的步數(shù)/return當(dāng)前搜索

7、子樹極小值。protectedintfindMin(intalpha,intbeta,intstep)intmin=beta;if(step=0)returnevaluate();intrt=getBests(sbw);for(inti=0;irt.length;i+)intx=rti0;inty=rti1;inttype=getType(x,y,sbw);if(type=1)/玩家成5return-100*(getMark(1)+step*1000);/預(yù)存當(dāng)前邊界值inttemp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max;isChessOnxy=

8、sbw;resetMaxMin(x,y);intt=findMax(alpha,min,step-1);isChessOnxy=2;/還原預(yù)設(shè)邊界值x_min=temp1;x_max=temp2;y_min=temp3;y_max=temp4;if(tmin)min=t;/alpha剪枝if(min=alpha)returnmin;returnmin;/選取局部最優(yōu)的幾個落子點作為下一次擴展的節(jié)點/bwf棋色0：黑棋1：白棋/return選出來的節(jié)點坐標privateintgetBests(intbwf)inti_min=(x_min=0?x_min:x_min-1);intj_min=(y_

9、min=0?y_min:y_min-1);inti_max=(x_max=15?x_max:x_max+1);intj_max=(y_max=15?y_max:y_max+1);intn=0;inttype_1,type_2;intrt=newint(i_max-i_min)*(j_max-j_min)3;for(inti=i_min;ii_max;i+)for(intj=j_min;jn?n:weight;intbests=newintsize3;System.arraycopy(rt,0,bests,0,size);returnbests;3、程序執(zhí)行結(jié)果初始界面圄五子棋=莢開始設(shè)貴W人機博弈人人博弈圄五子棋幫助禁手選擇團五子損D回|S開始設(shè)羞幫助4、個人總結(jié)、看法本程序是使用Alpha-Beta搜索的算法完成的一個簡單的五子棋博弈游戲。雖然Alpha-Beta已經(jīng)盡力做到細