人工智能课程设计

1、人工智能技术报告简介本课程设计是基于alpha-beta剪枝算法的五子棋的博弈游戏，具有悔棋，可选择禁手，支持人机对战，人人对战等功能。整个设计基于Java语言开发，界面美观大方。alpha-beta剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：（1）对于一个与节点MIN,若能估计出其倒推值的上确界卩，并且这个卩值不大于MIN的父节点（一定是或节点）的估计倒推值的下确界a，即ap，则就不必再扩展该MIN节点的其余子节点

2、了（因为这些节点的估值对MIN父节点的倒推值已无任何影响了）。这一过程称为a剪枝。（2）对于一个或节点MAX,若能估计出其倒推值的下确界a,并且这个a值不小于MAX的父节点（一定是与节点）的估计倒推值的上确界卩，即aP，则就不必再扩展该MAX节点的其余子节点了（因为这些节点的估值对MAX父节点的倒推值已无任何影响了）。这一过程称为卩剪枝。1、数据结构定义本文定义15*15的五子棋棋盘，实现算法，在算法中采用的数据结构包括：intisChessOn描述当前棋盘，0表示黑子，1表示白字，2表示无子；intpre记录棋点的x，y坐标。由于本课程设计是基于Java语言开发的，在Java中只能用类表示并

3、实现所定义的数据结构。所以下面将用类来描述相应的数据结构及算法：/棋盘背景位图/黑子位图/白子位图/棋局/是否已经分出胜负/胜利棋色/搜索的深度以及广度/和棋步数/总落子数目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;/当前应该下的棋色0：黑色（默认），1：白色protectedintx_max=15,x_min=0;/边界值,用于速度优化protectedinty_max=15,y_min=0;/边界值,用于速度优化protectedbooleanable_flag=true;/是否选择禁手标志0:无禁手1:有禁手（默认privateinth;/棋子长privateintw;priv

5、ateintinsx;privateintinsy;privatePointmousePoint;privateintwiner;privatebooleanhumanhuman=false;privateintplast=0;publicintBLACK_ONE;publicintWHITE_ONE;publicintNONE_ONE;publicintN;/搜索当前搜索状态极大值-/棋子宽/插入棋子的位置/鼠标当前位置/获胜方/是否是人人对弈/走了几步了，/0表黑子/1表白子/2表无子/棋盘边长/alpha祖先节点得到的当前最小最大值，用于alpha剪枝/beta祖先节点得到的当前最大最小

6、值，用于beta剪枝。/step还要搜索的步数/return当前搜索子树极大值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;/搜索当前搜索状态极小值/alpha祖先节点得到的当前最小最大值，用于alpha剪枝/beta祖先节点得到的当前最大最小值，用于beta剪枝/step还要搜索的步数/return当前搜索

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);/预存当前边界值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;/还原预设边界值x_min=temp1;x_max=temp2;y_min=temp3;y_max=temp4;if(tmin)min=t;/alpha剪枝if(min=alpha)returnmin;returnmin;/选取局部最优的几个落子点作为下一次扩展的节点/bwf棋色0：黑棋1：白棋/return选出来的节点坐标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、程序执行结果初始界面圄五子棋=莢开始设贵W人机博弈人人博弈圄五子棋帮助禁手选择團五子損D回|S开始设羞帮助4、个人总结、看法本程序是使用Alpha-Beta搜索的算法完成的一个简单的五子棋博弈游戏。虽然Alpha-Beta已经尽力做到细