搜索
人工智能五子棋技术报告简介本课程设计是基于alpha-beta剪枝算法的五子棋的博弈游戏，具有悔棋，可选择禁手，支持人机对战，人人对战等功能。整个设计基于Java语言开发，界面美观大方。alpha-beta剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1)对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为α剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为β剪枝。1、数据结构定义本文定义15*15的五子棋棋盘，实现算法，在算法中采用的数据结构包括：intisChessOn[][]描述当前棋盘，0表示黑子，1表示白字，2表示无子；intpre[][]记录棋点的x，y坐标。由于本课程设计是基于Java语言开发的，在Java中只能用类表示并实现所定义的数据结构。所以下面将用类来描述相应的数据结构及算法：publicclassChessPanel{privateImageIconmap;//棋盘背景位图privateImageIconblackchess;//黑子位图privateImageIconwhitechess;//白子位图publicintisChessOn[][];//棋局protectedbooleanwin=false;//是否已经分出胜负protectedintwin_bw;//胜利棋色protectedintdeep=3,weight=7;//搜索的深度以及广度publicintdrawn_num=110;//和棋步数intchess_num=0;//总落子数目publicint[][]pre=newint[drawn_num+1][2];//记录下棋点的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;//棋子宽privateintinsx;//插入棋子的位置privateintinsy;privatePointmousePoint;//鼠标当前位置privateintwiner;//获胜方privatebooleanhumanhuman=false;//是否是人人对弈privateintplast=0;//走了几步了，publicintBLACK_ONE;//0表黑子publicintWHITE_ONE;//1表白子publicintNONE_ONE;//2表无子publicintN;//棋盘边长//---------搜索当前搜索状态极大值--------------------------------////alpha祖先节点得到的当前最小最大值，用于alpha剪枝//beta祖先节点得到的当前最大最小值，用于beta剪枝。//step还要搜索的步数//return当前搜索子树极大值protectedintfindMax(intalpha,intbeta,intstep){intmax=alpha;if(step==0){returnevaluate();}int[][]rt=getBests(1-sbw);for(inti=0;irt.length;i++){intx=rt[i][0];inty=rt[i][1];if(getType(x,y,1-sbw)==1)//电脑可取胜return100*(getMark(1)+step*1000);isChessOn[x][y]=1-sbw;//预存当前边界值inttemp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max;resetMaxMin(x,y);intt=findMin(max,beta,step-1);isChessOn[x][y]=2;//还原预设边界值x_min=temp1;x_max=temp2;y_min=temp3;y_max=temp4;if(tmax)max=t;//beta剪枝if(max=beta)returnmax;}returnmax;}//-----------搜索当前搜索状态极小值--------------////alpha祖先节点得到的当前最小最大值，用于alpha剪枝//beta祖先节点得到的当前最大最小值，用于beta剪枝//step还要搜索的步数//return当前搜索子树极小值。protectedintfindMin(intalpha,intbeta,intstep){intmin=beta;if(step==0){returnevaluate();}int[][]rt=getBests(sbw);for(inti=0;irt.length;i++){intx=rt[i][0];inty=rt[i][1];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;isChessOn[x][y]=sbw;resetMaxMin(x,y);intt=findMax(alpha,min,step-1);isChessOn[x][y]=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选出来的节点坐标privateint[][]getBests(intbwf){inti_min=(x_min==0?x_min:x_min-1);intj_min=(y_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;int[][]rt=newint[(i_max-i_min)*(j_max-j_min)][3];for(inti=i_min;ii_max;i++)for(intj=j_min;jj_max;j++)if(isChessOn[i][j]==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;rt[n][0]=i;rt[n][1]=j;rt[n][2]=getMark(type_1)+getMark(type_2);n++;}//对二维数组排序Arrays.sort(rt,newArrComparator());intsize=weightn?n:weight;int[][]bests=newint[size][3];System.arraycopy(rt,0,bests,0,size);returnbests;}}2、程序流程图YN3、程序执行结果初始界面程序开始显示界面,绘制棋盘Haveai=true?与电脑博弈与人博弈玩家下子电脑下棋判断胜负，是否禁手玩家下子（黑）玩家下子（白）游戏结束音乐控制悔棋重新开始音乐控制悔棋重新开始人机博弈人人博弈禁手选择4、个人总结、看法本程序是使用Alpha-Beta搜索的算法完成的一个简单的五子棋博弈游戏。虽然Alpha-Beta已经尽力做到细致、全面，但由于Alpha-Beta搜索存在博弈树算法中普遍存在的一个缺点一随着搜索层数的增加，算法的效率大大下降。所以该搜索的效率还是不怎么理想，五子棋程序的“智力”也不高。因此可以在上述程序的基础上，针对五子棋本身的特点和规律对Alpha-Beta搜索算法进行优化与修正，比如用启发式搜索。