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

5：α-卩剪枝实现一字棋一、试验目的CZ-β剪枝算法实现一字棋。二、试验原理玩耍规章“一字棋“玩耍(又叫“三子棋“或“井字棋“)，是一款格外经典的益智小玩耍。“井字3X3的格子，很像中国文字中的“井“字，所以得名“井字棋“。“井字棋”玩耍的规章与“五子棋“格外类似，“五子棋“的规章是一方首先五子连成一线就成功；“井字棋“是一方首先三子连成一线就成功。微小极大分析法MAX,MIN二人对弈，轮到谁走棋谁就往空格上放一只自棋子)，谁就取得了成功。OXOOXMAX,MINMAX取胜的棋局。P,估价函数为e(P)0假设P对任何一方来说都不是获胜的位置，则e(P)=e(MAX空着的完全的行、列或对角线的总数)-eMlN空着的完全的行、列或对角线的总数)假设P是MAXe(P)=+s(实际上賦了60)o假设P是B必胜的棋局，则巳(P)=(实际上赋了-20)oOX比方P如以以以下图示■则 OX需要说明的是，+s60,-S20的缘由是机器假设赢了，则不管玩家下一步是否会赢，都会走这步必贏棋。a-卩剪枝算法上述的微小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使微小极大分析法效率较低。于是在微小极大分析法的根底上提出了a-p剪枝技术。α-β剪枝技术的根本思想或算法是,边生成博弈树边计算评估各节点的倒推值，并且依据评估出的倒推值围，准时停顿扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜寻效率。具体的剪枝方法如下：MIN,β,并且这个β值不大于MINa,即a≥β,则就不必再扩展该MINMIN父节点的倒推值已无任何影响了)。这a剪枝。对于一个或节点MAX,假设能估量出其倒推值的下确界a,并且这个a值不小于MAX的父节点(确定是与节点)的估量倒推值的上确界β,即a≥β,则就不必再扩展该MAX节点的其余子节点了(由于这些节点的估值对HAXβ剪枝。从算法中看到：MAX节点(包括起始节点)的a值永不削减；MIN节点(包括起始节点)的β值永不增加。在搜寻期间，OC和B值的计算如下：一个MAXa值等于其后继节点当前最大的最终倒推值。一个MlNβ值等于其后继节点当前最小的最终倒推值。输贏推断算法设计由于每次导致输赢的只会是当前放置的棋子，输贏算法中只需从当前点开头扫描推断是否已经形成三子。对于这个子的八个方向推断是否已经形成三子。如果有，则说明有一方成功，假设没有则连续搜寻，直到有一方成功或者搜寻完整个棋盘。三、试验代码#inCIUeIe<iostream>USingnamespacestd；intnum=0;intp.q；inttmpQP[3][3]:O表示该格为空，intnow[3][3];COnStintdepth-3；VOidInito{for(inti=0;i<3;i++)for(intj=0;j<3;j+÷)now[i][j]=0;}VOidPrintQPo{for(inti=0;i<3;i+÷){for(intj=0;j<3;j+÷)cout<<now[i][j]<<, tr；

〃记录棋盘上棋子的个数〃推断是否平局//表示棋盘数据的临时数组，其中的元素//存储当前棋盘的状态〃搜寻树的最大深度//初始化棋盘状态//将初值均置为O〃打印棋盘当前状态cout<<endl;}}VOidPIayerinPUtO{ 31,31列落子。intX,y；Ll：COlIt<<“请输入您的棋子位置(Xy):w<<endl;cin>>x>>y;if(x>0&&x〈4&&y>0&&y〈4&&now[x-l][y-l]=0)now[χ-l][y-l]=-l;else{cout<<,”非法输入!∙<<endl;gotoLl:

//站在电脑一方，玩家落子置为T//提示输入错误}}intCheCkWino有任何一方赢；1：计算机贏；T：人贏){for(inti≡0;i<3;i++){

//检查是否有一方赢棋(返回0：没〃该方法没有推断平局if((now[i][0]==l&&now[i][1J==IfiAnowtiJ[2]==1)∣(now[0][i]==l&&now[l][i]≡=l&&now⑵[i]==l)II(now[0][0]==l⅛ftnow[l][1]==1&&now[2][2]=1)∣I(now[2][0]==lMnow[l][l]=l⅛fcnow[0][2]==1)) 〃正方行连成线return1;if ((now[i][0]==-l&&now[i][l]==-l⅛ftnow[i][2]==-l)∣∣(now[0][i]==-l&&now[l][i]==-l&&now[2][i]==-l)II(now[0][0]==-l⅛ftnow[l][l]==-lftftnow[2][2]==-l)∣(now[2][0]==-l&&now[l][l]==-l&&now[0]⑵==T))returnT；

//反方行连成线}return0；}intvalue{以用P或q推断是否平局)p=0;q0;

〃评估当前棋盘状态的值(同时可for(inti=0；i<3；i++){ 01for(intj=0;j<3；j++){if(now[i][j]==0)tmpQP[i][j]=l;elsetmpQP[i][j]=now[i][j]；}}for(inti=0；i<3；i++) //31的行p+=(tmpQP[i][0]+tmpQP[i][l]+tmpQP[i][2])∕3;for(inti=0；i<3；i++) //31的列p+=(tmpQP[0][i]÷tmpQP[l][i]÷tmpQP[2][i])∕3;p+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP⑵⑵)/3； //31的对角线p+≡(tmpQP[2][0]÷tmpQP[l][l]÷tmpQP[0][2])/3；for(inti=0;i<3;i++){ //人一方//将棋盘中的空格填满自己的棋子,既将棋盘数组中的0变为-Ifor(intj=0;j<3;j++){if(now[i][j]==0)tmpQP[i][j]=-l;elsetmpQP[i][j]=now[i][j]；}}for(inti=0;i<3;i+÷)的行q+≡(tmpQP[i][0]+tmpQP[i][l]+tmpQP[i][2])∕3;for(inti=0;i<3;i++)的列q+≡(tmpQP[0][i]÷tmpQP[l][i]+tmpQP[2][i])∕3;q+=(tmpQP[0][0]+tmpQP[1][1]+tmpQP⑵⑵)/3；角线

//计算共有多少连成3个-1//31//3个1的对q+≡(tmpQP[2][0]÷tmpQP[l][l]÷tmpQP[0][2])/3；returnp+q； //返回评估出的棋盘状态的值}intcut(int&val,intdep,boolmax){ //a~B剪枝的算法，val为上一个结点的估量值，dep为搜寻深度，max记录上一个结点是否为上确界if(dep==depthdep+num==9)或者深度加上当前棋子数已经到达9,就直接调用估量函数returnValUeo:

//假设搜寻深度到达最大深度,inti,j,flag,temp；记录下层求得的估量值 //flag记录本层的极值tempboolout=false;false

//out记录是否剪枝，初始为if(max)

//假设上一个结点是上确界，本层则需要是下确界，记录flag为无穷大；反之，则为记录为负无穷大flag=10000; //flag记录本层节点的极值else

fla萨-10000；for(izz0;i<3&&!out；i++){ //双重循环，遍历棋盘全部位for(j=0；j<3&&!out；j++){if(now[i][j]==0){if(max){轮到用户玩家走了。

〃假设该位置上没有棋子〃并且上一个结点为上确界，即本层为下确界.now[i][j]=-l;if(CheckWin==-1)temp=T0000;

〃该位置填上用户玩家棋子〃假设用户玩家贏了〃置棋盘估量值为负无穷else

temp=cut(flag,dep÷l,!max):

//a-B剪枝函数if(te叩〈flag)极值，则置本层极值为更小者

//假设下一步棋盘的估量值小于本层节点的flag=temp;if(flag<=val)计值，则不需要搜寻下去，剪 点的估枝走了。

out=true;}else{界，轮到计算机now[i][j]=l;if(CheckwinO==I)temp=10000;else

//假设上一个结点为下确界，即本层为上确〃该位置填上计算机棋子〃假设计算机赢了//置棋盘估量值为无穷temp=cut(flag,dep+1,!max);//否则连续调用a~B剪枝函数if(temp>flag)flag=temp;if(flag>=val)out=true；}now[i][j]=0;Xpos=x;ypos=y;

//把模拟下的一步棋复原，回溯VaI=-IOO00；now[x][y]=0;}}}now[xPOSl[ypos]=l:VaI=-IOO00；m=-10000；dep=l;cout<<,”电脑将棋子放在:υ<<xpos+l<<ypos+l<<endl;PrintQPo；cout<<endl；num++；ValUeo;if(p==0){cout<<,τ平局!“<<endl;return0；}PlayerinPUto://玩家走一步棋PrintQPo；cout<<endl；num++；ValUeo;if(p==0){cout<<,τ平局!“<<endl;return0；}if(CheCkWin==-1){cout<<n您获胜!玩耍完毕.<endl;return0；}gotoL5；}else{L4：PlayerinPUto；PrintQPo；cout<<endl；num++；ValUeo;if(q==0){cout<<,τ平局!“<<endl;return0；

//人先走}if(CheCkWinO=-I){COUt<<lrreturn0；}for(intX二0；x<3；x++){for(inty=0；y<3；y++){if(now[x][y]==0){now[x][y]=l;CUt(VaI,dep1)；if(CheckwinO==I){1cout<<υ

电脑将棋子放在:M<<x+l<<y+l<<endl;PrintQPo；cout<<υ电脑获胜！玩耍完毕.“<<endhreturn0；}if(val>m){m=val;Xpos=x;ypos=y;}VaI=-IOO00；now[x][y]=0;}}}now[xPOSl[ypos]=l:VaI=-IOO00；m=-10000；dep=l;cout<<,”电脑将棋子放在:,”<<xpos+l<<ypos÷l<<endl:PrintQPo；cout<<endl;num++；ValUeo;if(q==0){COUt<<“平局!“<<endl;return0；}gotoL4；}return0；intmain{COmPUtero；SyStem(rτpauSeH)；return0；}4. 主要函数1intCTiCMFCDlg::evaluate(intboard[])完成功能：依据输入題盘，推断当前棋盘的估值，估价函数为前面所讲：MAXe二+INFINITY,这里为+60CUMPUTERel棋盘上能使PLAYERe2,CUMPUTERel棋盘上能使PLAYERe2,el-e2作为最终权值board:待评估棋盘参数：返评估结果回：2.AIPha-BetaAlPhaBeta剪枝主函数：intCTiCMFCDlg::AIPhaBeta〔intBOarC1[]t

intDepth,intturn,intAlPhat

intBetaT

int*result〕完成功能：依据输入棋盘，搜寻深度，及其他参数，给出一个相应的最优解，存入result中。参数：board:待评估棋盘DePth:搜寻深度turn:当前是机器走〔MAX结点〕还是玩家走〔MlN结点〕AIPha:alphaTOoBeta:beta值，第一次调用默认+100靜点•步棋〕result:输岀结果返回：假设当前点为MAXalpha值;MINbeta值3•推断胜败intCTiCMFCDlg::isWin(intCUrPOS)Ig输入棋盘，推断当前棋盘的结果，COMPLITER胜？PLAYER胜？平局？局？参数:board：待评估棋盘返回：-1表示：尚未完毕表示：平局表示：PLAYER胜表示:COMPUTER胜棋盘如下:请输入您的棋子位置乂棋盘如下:请输入您的棋子位置乂0000000000-1010-1010 0-1 00 0入您的棋子位置Jv＞