人工智能α-β剪枝实现的一字棋实验报告(共12页).doc
精选优质文档-倾情为你奉上实验5：a -b剪枝实现一字棋一、实验目的 学习极大极小搜索及a -b 剪枝算法实现一字棋。二、实验原理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. a -b剪枝算法上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了a-b 剪枝技术。 a -b 剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。 具体的剪枝方法如下： (1) 对于一个与节点 MIN，若能估计出其倒推值的上确界 b，并且这个 b 值不大于 MIN 的父节点(一定是或节点)的估计倒推值的下确界 a，即 a³b，则就不必再扩展该MIN 节点的其余子节点了(因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了)。这一过程称为 a 剪枝。 (2) 对于一个或节点 MAX，若能估计出其倒推值的下确界 a，并且这个 a 值不小于 MAX 的父节点(一定是与节点)的估计倒推值的上确界 b，即 a³b，则就不必再扩展该 MAX 节点的其余子节点了(因为这些节点的估值对 MAX 父节点的倒推值已无任何影响 了)。这一过程称为 b 剪枝。 从算法中看到： (1) MAX 节点(包括起始节点)的 a 值永不减少； (2) MIN 节点(包括起始节点)的 b 值永不增加。 在搜索期间，a 和 b 值的计算如下： (1) 一个 MAX 节点的 a 值等于其后继节点当前最大的最终倒推值。 (2) 一个 MIN 节点的 b 值等于其后继节点当前最小的最终倒推值。4输赢判断算法设计因为每次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。三、实验代码#include<iostream>using namespace std;int num=0; /记录棋盘上棋子的个数int p,q; /判断是否平局int tmpQP33; /表示棋盘数据的临时数组，其中的元素0表示该格为空，int now33; /存储当前棋盘的状态const int depth=3; /搜索树的最大深度void Init() /初始化棋盘状态 for(int i=0;i<3;i+)for(int j=0;j<3;j+) nowij=0; /将初值均置为0 void PrintQP() /打印棋盘当前状态 for(int i=0;i<3;i+) for(int j=0;j<3;j+)cout<<nowij<<'t' cout<<endl; void playerinput() /用户通过此函数来输入落子的位置，比如：用户输入3 1，则表示用户在第3行第1列落子。 int x,y;L1: cout<<"请输入您的棋子位置(x y):"<<endl; cin>>x>>y; if(x>0&&x<4&&y>0&&y<4&&nowx-1y-1=0) nowx-1y-1=-1; /站在电脑一方，玩家落子置为-1 else cout<<"非法输入!"<<endl; /提醒输入错误 goto L1; int Checkwin() /检查是否有一方赢棋（返回 0：没有任何一方赢；1：计算机赢；-1：人赢） /该方法没有判断平局 for(int i=0;i<3;i+) 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; 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; return 0;int value() /评估当前棋盘状态的值（同时可以用p或q判断是否平局） p=0; q=0; for(int i=0;i<3;i+) /计算机一方 将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为1 for(int j=0;j<3;j+) if(nowij=0) tmpQPij=1; else tmpQPij=nowij; for(int i=0;i<3;i+) /计算共有多少连成3个1的行 p+=(tmpQPi0+tmpQPi1+tmpQPi2)/3; for(int i=0;i<3;i+) /计算共有多少连成3个1的列 p+=(tmpQP0i+tmpQP1i+tmpQP2i)/3; p+=(tmpQP00+tmpQP11+tmpQP22)/3; /计算共有多少连成3个1的对角线 p+=(tmpQP20+tmpQP11+tmpQP02)/3; for(int i=0;i<3;i+) /人一方 /将棋盘中的空格填满自己的棋子，既将棋盘数组中的0变为-1 for(int j=0;j<3;j+) if(nowij=0) tmpQPij=-1; else tmpQPij=nowij; for(int i=0;i<3;i+) /计算共有多少连成3个-1的行 q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3; for(int i=0;i<3;i+) /计算共有多少连成3个1的列 q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3; q+=(tmpQP00+tmpQP11+tmpQP22)/3; /计算共有多少连成3个1的对角线 q+=(tmpQP20+tmpQP11+tmpQP02)/3; return p+q; /返回评估出的棋盘状态的值int cut(int &val,int dep,bool max) /主算法部分，实现a-B剪枝的算法，val为上一个结点的估计值，dep为搜索深度，max记录上一个结点是否为上确界 if(dep=depth|dep+num=9) /如果搜索深度达到最大深度，或者深度加上当前棋子数已经达到9，就直接调用估计函数 return value(); int i,j,flag,temp; /flag记录本层的极值，temp记录下层求得的估计值 bool out=false; /out记录是否剪枝，初始为false if(max) /如果上一个结点是上确界，本层则需要是下确界，记录flag为无穷大；反之，则为记录为负无穷大 flag=10000; /flag记录本层节点的极值 else flag=-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 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; /置棋盘估计值为无穷 else temp=cut(flag,dep+1,!max);/否则继续调用a-B剪枝函数 if(temp>flag) flag=temp; if(flag>=val) out=true; nowij=0; /把模拟下的一步棋还原，回溯 if(max) /根据上一个结点是否为上确界，用本层的极值修改上一个结点的估计值 if(flag>val) val=flag; else if(flag<val) val=flag; return flag; /函数返回的是本层的极值int computer() int m=-10000,val=-10000,dep=1; /m用来存放最大的val int x_pos,y_pos; /记录最佳走步的坐标 char ch; 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(int x=0;x<3;x+) for(int y=0;y<3;y+) if(nowxy=0) nowxy=1; cut(val,dep,1); /计算机试探的走一步棋，棋盘状态改变了，在该状态下计算出深度为dep-1的棋盘状态估计值val if(Checkwin()=1) cout<<"电脑将棋子放在:"<<x+1<<y+1<<endl; PrintQP(); cout<<"电脑获胜! 游戏结束."<<endl; return 0; if(val>m) /m要记录通过试探求得的棋盘状态的最大估计值 m=val; x_pos=x;y_pos=y; val=-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; return 0; playerinput(); /玩家走一步棋 PrintQP(); cout<<endl; num+; value(); if(p=0) cout<<"平局!"<<endl; return 0; if(Checkwin()=-1) cout<<"您获胜! 游戏结束."<<endl; return 0; goto L5; else /人先走 L4: playerinput(); PrintQP(); cout<<endl; num+; value(); if(q=0) cout<<"平局!"<<endl; return 0; if (Checkwin()=-1) cout<<"您获胜! 游戏结束."<<endl; return 0; for(int x=0;x<3;x+) for(int y=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; return 0; if(val>m) m=val; x_pos=x;y_pos=y; val=-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(q=0) cout<<"平局!"<<endl; return 0; goto L4; return 0; int main() computer();system("pause");return 0;4. 主要函数1 估值函数估价函数：int CTic_MFCDlg:evaluate(int board) 完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是 MAX 的必胜局，则 e = +INFINITY，这里为+60 若是 MIN 的必胜局，则 e = -INFINITY，这里为-20，这样赋值的原因是机器若赢了，则不考虑其它因素。其它情况，棋盘上能使 CUMPUTER 成三子一线的数目为 e1棋盘上能使 PLAYER成三子一线的数目为 e2，e1-e2 作为最终权值参数： board:待评估棋盘 返回： 评估结果2.Alpha-Beta 剪枝算法AlphaBeta 剪枝主函数： int CTic_MFCDlg:AlphaBeta(int Board, int Depth, int turn, int Alpha, int Beta, int *result) 完成功能：根据输入棋盘，搜索深度，及其他参数，给出一个相应的最优解，存入 result 中。参数：board :待评估棋盘 Depth :搜索深度 turn :当前是机器走(MAX 结点)还是玩家走(MIN 结点) Alpha :alpha 值，第一次调用默认-100 Beta :beta 值，第一次调用默认+100 result :输出结果 返回：若当前点为 MAX 节点，则返回 alpha 值； 若当前点为 MIN 节点，则返回 beta 值.判断胜负int CTic_MFCDlg:isWin(int curPos)完成功能：根据输入棋盘，判断当前棋盘的结果，COMPUTER 胜？PLAYER 胜？平局？参数：board:待评估棋盘 返回：-1 表示：尚未结束 0 表示：平局 1 表示：PLAYER 胜 2 表示：COMPUTER 胜 五、实验截图六、实验总结通过本次实验进一步对老师课堂上所讲的a -b剪枝有了更加深刻的了解，对它的一般实现有了初步的认识。搜索深度并非越深越好，局限于估值函数是根据能够成三子一线的数目决定的，所以搜索到最后一层，如果有人胜，则出现 ¥ ¥，如果没人胜，则三子一线数目为 0，所以毫无意义。这也是为什么大多数情况下都是平局的原因。专心-专注-专业
