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

1、实验5:剪枝实现一字棋、实验目的学习极大极小搜索及剪枝算法实现一字棋.二、实验原理1.游戏规那么"一字棋"游戏(又叫"三子棋"或"井字棋"),是一款十分经典的益智小游戏."井字棋的棋盘很简单,是一个3X3的格子,很像中国文字中的"井"字,所以得名"井字棋"."井字棋游戏的规那么与“五子棋"十分类似,"五子棋"的规那么是一方首先五子连成一线就胜利；“井字棋是一方首先三子连成一线就胜利.2.极小极大分析法设有九个空格,由MAX,MIN二人对弈,轮到谁

2、走棋谁就往空格上放一只自己的棋子,谁先使自己的棋子构成"三子成一线(同一行或列或对角线全是e(P)o(1)假设P对任何一方来说都不是获胜的位置,那么着的完全的行、列或对角线的总数)-e(那些仍为MIN角线的总数)e(P)=eCB些仍为MAX空空着的完全的行、列或对(2)假设P是MAX必胜的棋局,那么e(P)=+假设P是B必胜的棋局,那么e(P)=-(实际上赋了60).(实际上赋了-20).上述的极小极大分析法,实际是先生成一棵博弈树,然后再计算其倒推值,至使极小极大分析法效率较低.于是在极小极大分析法的根底上提出了-剪枝技术.-剪枝技术的根本思想或算法是,边生成博弈树边计算评估各节点

3、的倒推值,并且根据评估出的倒推值范围,及时停止扩展那些已无必要再扩展的子节点,即相当于剪去了博弈树上的一些分枝,从而节约了机器开销,提升了搜索效率.具体的剪枝方法如下:(1)对于一个与节点MIN,假设能估计出其倒推值的上确界,并且这个值不大于MIN的父节点(一定是或节点)的估计倒推值的下确界,即,那么就不必再扩展该MIN节点的其余子节点了(由于这些节点的估值对MIN父节点的倒推值已无任何影响了).这一过程称为剪枝.(2)对于一个或节点MAX,假设能估计出其倒推值的下确界,并且这个值不小于MAX的父节点(一定是与节点)的估计倒推值的上确界,即,那么就不必再扩展该MAX节点的其余子节点了(由于这些

4、节点的估值对MAX父节点的倒推值已无任何影响了).这一过程称为剪枝.从算法中看到：(1) MAX节点(包括起始节点)的值永不减少；(2) MIN节点(包括起始节点)的值永不增加.在搜索期间,和值的计算如下:(1) 一个MAX节点的值等于其后继节点当前最大的最终倒推值.(2) 一个MIN节点的值等于其后继节点当前最小的最终倒推值.4.输赢判断算法设计由于每次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断是否已经形成三子.对于这个子的八个方向判断是否已经形成三子.如果有,那么说明有一方胜利,如果没有那么继续搜索,直到有一方胜利或者搜索完整个棋盘.三、实验代码#include&l

5、t;iostream>usingnamespacestd;intnum=0;intp,q;inttmpQP33;表示该格为空,intnow33;constintdepth=3;voidInit()for(inti=0;i<3;i+)for(intj=0;j<3;j+)nowij=0;/记录棋盘上棋子的个数/判断是否平局表示棋盘数据的临时数组,其中的元素0/存储当前棋盘的状态/搜索树的最大深度/将初值均置为0/初始化棋盘状态voidPrintQP()打印棋盘当前状态for(inti=0;i<3;i+)for(intj=0；j<3；j+)cout<<now

6、ij<<'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&&nowx-1y-1=0)nowx-1y-1=-1;elsecout<<"非法输入!

7、"<<endl;gotoL1;intCheckwin()任何一方赢；1:计算机赢；-1:人赢)for(inti=0;i<3;i+)/站在电脑一方,玩家落子置为-1/提醒输入错误/检查是否有一方赢棋(返回0:没有/该方法没有判断平局if(nowi0=1&&nowi1=1&&nowi2=1)|(now0i=1&&now1i=1&&now2i=1)|(now00=1&&now11=1&&now22=1)|(now20=1&&now11=1&&no

8、w02=1)正方行连成线return1;if(nowi0=-1&&nowi1=-1&&nowi2=-1)|(now0i=-1&&now1i=-1&&now2i=-1)|(now00=-1&&now11=-1&&now22=-1)|(now20=-1&&now11=-1&&now02=-1)/反方行连成线return-1;return0;intvalue()/评估当前棋盘状态的值(同时可以用p或q判断是否平局)p=0;q=0;for(inti=0;i<3;i+)计

9、算机一方将棋盘中的空格填满自己的棋子,既将棋盘数组中的0变为1for(intj=0;j<3;j+)if(nowij=0)tmpQPij=1;elsetmpQPij=nowij;)for(inti=0;i<3;i+)p+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(inti=0;i<3;i+)p+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;p+=(tmpQP00+tmpQP11+tmpQP22)/3;线p+=(tmpQP20+tmpQP11+tmpQP02)/3;for(inti=0;i<3;i+)既将棋盘数组中的0变为-1for(int

10、j=0;j<3;j+)/计算共有多少连成3个1的行/计算共有多少连成3个1的列/计算共有多少连成3个1的对角/人一方/将棋盘中的空格填满自己的棋子,if(nowij=0)tmpQPij=-1;elsetmpQPij=nowij;)for(inti=0;i<3;i+)q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(inti=0;i<3;i+)q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;q+=(tmpQP00+tmpQP11+tmpQP22)/3;角线q+=(tmpQP20+tmpQP11+tmpQP02)/3;returnp+q;)int

11、cut(int&val,intdep,boolmax)val为上一个结点的估计值,dep为搜索深度,if(dep=depth|dep+num=9)度,或者深度加上当前棋子数已经到达returnvalue();inti,j,flag,temp;层求得的估计值boolout=false;if(max)层那么需要是下确界,记录)/计算共有多少连成3个-1的行/计算共有多少连成3个1的列/计算共有多少连成3个1的对/返回评估出的棋盘状态的值主算法局部,实现a-B剪枝的算法,max记录上一个结点是否为上确界/如果搜索深度到达最大深9,就直接调用估计函数/flag记录本层的极值,temp记录下/o

12、ut记录是否剪枝,初始为false/如果上一个结点是上确界,本flag为无穷大；反之,那么为记录为负无穷大flag=10000;/flag记录本层节点的极值elseflag=-10000;for(i=0;i<3&&!out;i+)/双重循环,遍历棋盘所有位置for(j=0;j<3&&!out;j+)if(nowij=0)if(max)轮到用户玩家走了./如果该位置上没有棋子并且上一个结点为上确界,即本层为下确界nowij=-1;if(Checkwin()=-1)temp=-10000;else/该位置填上用户玩家棋子如果用户玩家赢了/置棋盘估计值为负

13、无穷temp=cut(flag,dep+1,!max);/否那么继续调用a-B剪枝函数if(temp<flag)值,那么置本层极值为更小者flag=temp;if(flag<=val)值,那么不需要搜索下去,剪枝out=true;/如果下一步棋盘的估计值小于本层节点的极/如果本层的极值已经小于上一个结点的估计else/如果上一个结点为下确界,即本层为上确界,轮到计算机走了./该位置填上计算机棋子/如果计算机赢了/置棋盘估计值为无穷nowij=1;if(Checkwin()=1)temp=10000;elsetemp=cut(flag,dep+1,!max);/否那么继续调用a-B剪

14、枝函数if(temp>flag)flag=temp;if(flag>=val)out=true;nowij=0;把模拟下的一步棋复原,回溯根据上一个结点是否为上确界,用本层的if(max)极值修改上一个结点的估计值if(flag>val)val=flag;)elseif(flag<val)val=flag;)returnflag;函数返回的是本层的极值)intcomputer()/m用来存放最大的val/记录最正确走步的坐标intm=-10000,val=-10000,dep=1;intx_pos,y_pos;charch;cout<<"您希望先走

15、吗？(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

16、<3;y+)if(nowxy=0)nowxy=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=-

17、10000;nowxy=0;)nowx_posy_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

18、<<"平局!"<<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<<"您获胜！游戏结束."<

19、<endl;return0;)for(intx=0;x<3;x+)for(inty=0;y<3;y+)if(nowxy=0)nowxy=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;nowxy=0;)nowx_posy_pos=

20、1;val=-10000;m=-10000;dep=1;cout«"电脑将棋子放在:"«x_pos+1«y_pos+1«endl;PrintQP();cout«endl;num+;value();if(q=o)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,inttu