人工智能α-β剪枝实现的一字棋实验报告及人工智能大作业报告

人工智能课程项目报告PAGE12实验5：-剪枝实现一字棋一、实验目的学习极大极小搜索及-剪枝算法实现一字棋。二、实验原理1.游戏规则"一字棋"游戏（又叫"三子棋"或"井字棋"），是一款十分经典的益智小游戏。"井字棋"的棋盘很简单，是一个3×3的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先三子连成一线就胜利。2.极小极大分析法设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。○╳用圆圈表示MAX，用叉号代表MIN○○○比如左图中就是MAX取胜的棋局。╳╳估价函数定义如下设棋局为P，估价函数为e(P)。(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)(2)若P是MAX必胜的棋局，则e(P)＝+（实际上赋了60）。(3)若P是B必胜的棋局，则e(P)＝-（实际上赋了-20）。比如P如下图示,则e(P)=5-4=1○╳需要说明的是，+赋60，-赋-20的原因是机器若赢了，则不论玩家下一步是否会赢，都会走这步必赢棋。3.-剪枝算法上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了-剪枝技术。-剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1)对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响了)。这一过程称为剪枝。(2)对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响了)。这一过程称为剪枝。从算法中看到：(1)MAX节点(包括起始节点)的值永不减少；(2)MIN节点(包括起始节点)的值永不增加。在搜索期间，和值的计算如下：(1)一个MAX节点的值等于其后继节点当前最大的最终倒推值。(2)一个MIN节点的值等于其后继节点当前最小的最终倒推值。4．输赢判断算法设计因为每次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。三、实验代码#include<iostream>usingnamespacestd;intnum=0;//记录棋盘上棋子的个数intp,q;//判断是否平局inttmpQP[3][3];//表示棋盘数据的临时数组，其中的元素0表示该格为空，intnow[3][3];//存储当前棋盘的状态constintdepth=3;//搜索树的最大深度voidInit(){//初始化棋盘状态for(inti=0;i<3;i++) for(intj=0;j<3;j++) now[i][j]=0;//将初值均置为0}voidPrintQP(){//打印棋盘当前状态for(inti=0;i<3;i++){for(intj=0;j<3;j++) cout<<now[i][j]<<'\t';cout<<endl;}}voidplayerinput(){//用户通过此函数来输入落子的位置，比如：用户输入31，则表示用户在第3行第1列落子。intx,y;L1:cout<<"请输入您的棋子位置(xy):"<<endl;cin>>x>>y;if(x>0&&x<4&&y>0&&y<4&&now[x-1][y-1]==0)now[x-1][y-1]=-1;//站在电脑一方，玩家落子置为-1else{cout<<"非法输入!"<<endl;//提醒输入错误gotoL1;}}intCheckwin()//检查是否有一方赢棋（返回0：没有任何一方赢；1：计算机赢；-1：人赢）{//该方法没有判断平局for(inti=0;i<3;i++){if((now[i][0]==1&&now[i][1]==1&&now[i][2]==1)||(now[0][i]==1&&now[1][i]==1&&now[2][i]==1)||(now[0][0]==1&&now[1][1]==1&&now[2][2]==1)||(now[2][0]==1&&now[1][1]==1&&now[0][2]==1))//正方行连成线return1;if((now[i][0]==-1&&now[i][1]==-1&&now[i][2]==-1)||(now[0][i]==-1&&now[1][i]==-1&&now[2][i]==-1)||(now[0][0]==-1&&now[1][1]==-1&&now[2][2]==-1)||(now[2][0]==-1&&now[1][1]==-1&&now[0][2]==-1))//反方行连成线return-1;}return0;}intvalue(){//评估当前棋盘状态的值（同时可以用p或q判断是否平局）p=0;q=0;for(inti=0;i<3;i++){//计算机一方将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1for(intj=0;j<3;j++){if(now[i][j]==0)tmpQP[i][j]=1;elsetmpQP[i][j]=now[i][j];}}for(inti=0;i<3;i++)//计算共有多少连成3个1的行p+=(tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2])/3;for(inti=0;i<3;i++)//计算共有多少连成3个1的列p+=(tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i])/3;p+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2])/3;//计算共有多少连成3个1的对角线p+=(tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2])/3;for(inti=0;i<3;i++){//人一方//将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为-1for(intj=0;j<3;j++){if(now[i][j]==0)tmpQP[i][j]=-1;elsetmpQP[i][j]=now[i][j];}}for(inti=0;i<3;i++)//计算共有多少连成3个-1的行q+=(tmpQP[i][0]+tmpQP[i][1]+tmpQP[i][2])/3;for(inti=0;i<3;i++)//计算共有多少连成3个1的列q+=(tmpQP[0][i]+tmpQP[1][i]+tmpQP[2][i])/3;q+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP[2][2])/3;//计算共有多少连成3个1的对角线q+=(tmpQP[2][0]+tmpQP[1][1]+tmpQP[0][2])/3;returnp+q;//返回评估出的棋盘状态的值}intcut(int&val,intdep,boolmax){//主算法部分，实现a-B剪枝的算法，val为上一个结点的估计值，dep为搜索深度，max记录上一个结点是否为上确界if(dep==depth||dep+num==9)//如果搜索深度达到最大深度，或者深度加上当前棋子数已经达到9，就直接调用估计函数returnvalue();inti,j,flag,temp;//flag记录本层的极值，temp记录下层求得的估计值boolout=false;//out记录是否剪枝，初始为falseif(max)//如果上一个结点是上确界，本层则需要是下确界，记录flag为无穷大；反之，则为记录为负无穷大flag=10000;//flag记录本层节点的极值elseflag=-10000;for(i=0;i<3&&!out;i++){//双重循环，遍历棋盘所有位置for(j=0;j<3&&!out;j++){if(now[i][j]==0){//如果该位置上没有棋子if(max){//并且上一个结点为上确界，即本层为下确界,轮到用户玩家走了。now[i][j]=-1;//该位置填上用户玩家棋子if(Checkwin()==-1)//如果用户玩家赢了temp=-10000;//置棋盘估计值为负无穷elsetemp=cut(flag,dep+1,!max);//否则继续调用a-B剪枝函数if(temp<flag)//如果下一步棋盘的估计值小于本层节点的极值，则置本层极值为更小者flag=temp;if(flag<=val)//如果本层的极值已经小于上一个结点的估计值，则不需要搜索下去，剪枝out=true;}else{//如果上一个结点为下确界，即本层为上确界,轮到计算机走了。now[i][j]=1;//该位置填上计算机棋子if(Checkwin()==1)//如果计算机赢了temp=10000;//置棋盘估计值为无穷elsetemp=cut(flag,dep+1,!max);//否则继续调用a-B剪枝函数if(temp>flag)flag=temp;if(flag>=val)out=true;}now[i][j]=0;//把模拟下的一步棋还原，回溯}}}if(max){//根据上一个结点是否为上确界，用本层的极值修改上一个结点的估计值if(flag>val)val=flag;}else{if(flag<val)val=flag;}returnflag;//函数返回的是本层的极值}intcomputer(){intm=-10000,val=-10000,dep=1;//m用来存放最大的valintx_pos,y_pos;//记录最佳走步的坐标charch;cout<<"您希望先走吗?(y/n)";cin>>ch;while(ch!='y'&&ch!='n'){cout<<"非法输入!"<<"您希望先走吗(y/n)"<<endl;cin>>ch;}system("cls");Init();cout<<"棋盘如下:"<<endl;PrintQP();if(ch=='n'){//计算机先走L5:for(intx=0;x<3;x++){for(inty=0;y<3;y++){if(now[x][y]==0){now[x][y]=1;cut(val,dep,1);//计算机试探的走一步棋，棋盘状态改变了，在该状态下计算出深度为dep-1的棋盘状态估计值valif(Checkwin()==1){cout<<"电脑将棋子放在:"<<x+1<<y+1<<endl;PrintQP();cout<<"电脑获胜!游戏结束."<<endl;return0;}if(val>m){//m要记录通过试探求得的棋盘状态的最大估计值m=val;x_pos=x;y_pos=y;}val=-10000;now[x][y]=0;}}}now[x_pos][y_pos]=1;val=-10000;m=-10000;dep=1;cout<<"电脑将棋子放在:"<<x_pos+1<<y_pos+1<<endl;PrintQP();cout<<endl;num++;value();if(p==0){cout<<"平局!"<<endl;return0;}playerinput();//玩家走一步棋PrintQP();cout<<endl;num++;value();if(p==0){cout<<"平局!"<<endl;return0;}if(Checkwin()==-1){cout<<"您获胜!游戏结束."<<endl;return0;}gotoL5;}else{//人先走L4:playerinput();PrintQP();cout<<endl;num++;value();if(q==0){cout<<"平局!"<<endl;return0;}if(Checkwin()==-1){cout<<"您获胜!游戏结束."<<endl;return0;}for(intx=0;x<3;x++){for(inty=0;y<3;y++){if(now[x][y]==0){now[x][y]=1;cut(val,dep,1);if(Checkwin()==1){cout<<"电脑将棋子放在:"<<x+1<<y+1<<endl;PrintQP();cout<<"电脑获胜!游戏结束."<<endl;return0;}if(val>m){m=val;x_pos=x;y_pos=y;}val=-10000;now[x][y]=0;}}}now[x_pos][y_pos]=1;val=-10000;m=-10000;dep=1;cout<<"电脑将棋子放在:"<<x_pos+1<<y_pos+1<<endl;PrintQP();cout<<endl;num++;value();if(q==0){cout<<"平局!"<<endl;return0;}gotoL4;}return0;}intmain(){computer(); system("pause");return0;}4.主要函数1估值函数估价函数：intCTic_MFCDlg::evaluate(intboard[])完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是MAX的必胜局，则e=+INFINITY，这里为+60若是MIN的必胜局，则e=-INFINITY，这里为-20，这样赋值的原因是机器若赢了，则不考虑其它因素。其它情况，棋盘上能使CUMPUTER成三子一线的数目为e1棋盘上能使PLAYER成三子一线的数目为e2，e1-e2作为最终权值参数：board:待评估棋盘返回：评估结果2.Alpha-Beta剪枝算法AlphaBeta剪枝主函数：intCTic_MFCDlg::AlphaBeta(intBoard[],intDepth,intturn,intAlpha,intBeta,int*result)完成功能：根据输入棋盘，搜索深度，及其他参数，给出一个相应的最优解，存入result中。参数： board:待评估棋盘 Depth:搜索深度 turn:当前是机器走(MAX结点)还是玩家走(MIN结点) Alpha:alpha值，第一次调用默认-100 Beta:beta值，第一次调用默认+100 result:输出结果返回： 若当前点为MAX节点，则返回alpha值；若当前点为MIN节点，则返回beta值３.判断胜负intCTic_MFCDlg::isWin(intcurPos)完成功能：根据输入棋盘，判断当前棋盘的结果，COMPUTER胜？PLAYER胜？平局？参数： board:待评估棋盘返回： -1表示：尚未结束0表示：平局1表示：PLAYER胜2表示：COMPUTER胜五、实验截图六、实验总结通过本次实验进一步对老师课堂上所讲的-剪枝有了更加深刻的了解，对它的一般实现有了初步的认识。搜索深度并非越深越好，局限于估值函数是根据能够成三子一线的数目决定的，所以搜索到最后一层，如果有人胜，则出现，如果没人胜，则三子一线数目为0，所以毫无意义。。这也是为什么大多数情况下都是平局的原因。人工智能课程大作业——基于回溯搜索的地图着色班级：20110616学号：2011061624姓名：曾江东2014年11月26号摘要：人工智能是20世纪50年代中期兴起的一门边缘学科。人工智能领域中，地图着色问题是一典型的优化的问题。由它引发的“四色猜想”是全世界的难题，直到1975年由三台超高速电子计算机，经过1200小时的计算才终于正明了“四色定理”。这是世界上最长的证明。本文并不是想证明，而只是想基于回溯法来给地图着色，求出最少用色。本文着重介绍利用MFC设计界面来对中国省级地图着色进行演示。计算机视觉是研究为完成在复杂的环境中运动和在复杂的场景中识别物体所需要哪些视觉信息，以及如何从图像中获取这些信息的科学领域。关键词：地图着色；回溯搜索；MFC本组成员：曾江东，杨星，俞洋本人分工：本人主要基于回溯搜索算法的代码的编写。1引言人，现在社会的发展中心都离不开这个人字，人是发展的本体，人类的自然智能伴随到处都是，本次实验研究什么是人工智能，人工智能又能如何的运用在生活和学习中。

人工智能(Artificial

Intelligence)

，英文缩写为AI。它是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。

人工智能（Artificial

Intelligence，AI）是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。人工智能从诞生以来，理论和技术日益成熟，应用领域也不断扩大，但没有一个统一的定义。人工智能是计算机科学的一个分支，它企图了解智能的实质，并生产出一种新的能以人类智能相似的方式做出反应的智能机器，该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。

本次实验研究的是关于人工智能中搜索的功能，实现用回溯法对地图不同地区的着色问题，地图上有不同国家（不同区域），每个国家都与其他一些国家邻接。现要求对地图着色，使所有的国家与它的邻接的国家有不同的颜色。通常由四种颜色就已足够。地图着色的算法比较多，但是切实可行的算法很少，回溯法在地图区域较大，邻接关系复杂的情况下，回溯次数将会大大增多，严重影响了程序执行效率。不过本次作业则是采用修改后的回溯法，在一定的条件下，执行效率还是很高。

本次实验是要对中国地图中的省级行政区最多使用四种颜色来进行着色，编程实现回溯算法用于地图自动着色。我负责得是改进的回溯算法的代码的编写。2算法原理与系统设计2.1

回溯算法原理要解决地图着色的问题，本文采用的是回溯法。回溯法是一种系统地搜索问题解的搜索算法。回溯法递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

其基本步骤：1.定义一个解空间，它包含问题的解。

2.利用适于\o"搜索"搜索的方法组织解空间。3.利用\o"深度优先法"深度优先法搜索解空间。4.利用\o"限界函数"限界函数避免移动到不可能产生解的子空间。而地图着色的问题可以处理为：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。则着色问题变成了对解问题的最优搜索算法的实现。我利用分枝定界法对候选解进行系统检查，能以较高效率的找到最优解。2.2

详细设计地图着色功能流程图如图2-1所示：图2-1地图颜色确定流程图在窗口上着色时，用到的是广度算法的思想，搜索遍历一个省区域内的所有像素点。着色是各省渐变着色，感观上能看见是从省中间向边缘扩散。在对一个省进行着色时，用深度优先的算法实现，共用4种颜色，分别是红，绿，蓝，黄。每次给当前省份4种颜色中的一种，然后判断是否合理，如不合理则换另一种颜色值，根据图的4色定理一定能从4种颜色中找到一个合适的颜色，直到当前省份找到合适颜色后，进行下个省份的判断。在着色时，以这个省份的中心点为基准，由环形向外进行着色，采用深度优先搜索算法，并根据标记的二维数组来进行边界检测，以保证着色的准确性。在本次设计中，用到了关于地图信息的两个文件，一个是地图标记点文档，如图2-2所示。它里边存储的是地图的每个省份的中间点的像素坐标，如“新疆

125

123”，代表的是新疆在地图中的坐标位置，一共32个省。另一个是相邻之间的关系的文档，如图2-3所示。它里边存储的是省与省之间的相邻接关系，比如“13”，代表省1，省3相邻。这里的0和1是根据node表中的顺序得来的，0代表新疆，1代表西藏。当两个省相临时，他们不能着相同的颜色。程序不要求用户输入，运行程序后自动从文件中读取地图信息，并加载原始地图，出现可操作的可视化界面。图2-2地图标记点文件图2-3相邻之间的关系文件3系统实现3-1回溯算法我采用的是深度优先搜索算法，它就是把最近刚产生的结点优先扩展，直到达到一定的深度限制。若未找到目标或无法再扩展时，再回溯到另一个结点继续扩展。它类似于树的先根搜索，是树的先根搜索的推广。3-2代码实现地图涂色用到深度优先搜索算法voidCMyDlg::On_Color(){ //TODO:Addyourcontrolnotificationhandlercodehere ALgraphG; inti,s,d;listnode*p,*q; ifstreamifile("C:\\地图(邻接表)\\text2.txt",ios::in); G.vexnum=32; G.arcnum=68; for(i=1;i<=32;i++) { G.vexs[i].first=NULL; } for(i=1;i<=68;i++){ ifile>>s>>d; p=newlistnode; p->adjvex=d; p->next=G.vexs[s].first; G.vexs[s].fi