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

1、实验5:剪枝实现一字棋、实验目的学习极大极小搜索及剪枝算法实现一字棋。二、实验原理1. 游戏规则"一字棋"游戏(又叫"三子棋"或"井字棋")，是一款十分经典的益智小游戏。"井字棋"的棋 盘很简单，是一个3 X 3的格子，很像中国文字中的"井"字，所以得名"井字棋"。"井字棋"游戏的 规则与"五子棋"十分类似，"五子棋"的规则是一方首先五子连成一线就胜利；"井字棋"是一方首先 三子连成一线就胜利。2

2、. 极小极大分析法设有九个空格，由MAX min二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使 自己的棋子构成"三子成一线"(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。OXOOOXX用圆圈表示MAX用叉号代表MIN比如左图中就是MAX取胜的棋局。估价函数定义如下设棋局为P，估价函数为 e(P)。(1) 若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列 或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)(2) 若P是MAX必胜的棋局，则e(P) = +(实际上赋了 60 )。(3) 若P是B必胜的棋局

3、，则e(P)=-(实际上赋了 -20 )。比如P如下图示,则e(P)=5-4=1OX需要说明的是，+赋60，-赋-20的原因是机器若赢了，则不论玩 家下一步是否会赢，都会走这步必赢棋。剪枝算法3.上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒 推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上 提出了 -剪枝技术。- 剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1) 对于一个与节点MIN，

4、若能估计出其倒推值的上确界 ，并且这个 值不大于MIN的 父节点(一定是或节点)的估计倒推值的下确界 ，即 ，则就不必再扩展该MIN节点的其余子 节点了(因为这些节点的估值对 MIN父节点的倒推值已无任何影响了 )。这一过程称为 剪枝。(2) 对于一个或节点MAX若能估计出其倒推值的下确界 ，并且这个 值不小于MAX的 父节点(一定是与节点)的估计倒推值的上确界 ，即 ，则就不必再扩展该MAX节点的其余子 节点了(因为这些节点的估值对 MAX父节点的倒推值已无任何影响 了)。这一过程称为 剪枝。从算法中看到：(1) MAX节点(包括起始节点)的值永不减少;(2) MIN节点(包括起始节点)的值

5、永不增加。值等于其后继节点当前最大的最终倒推值。 值等于其后继节点当前最小的最终倒推值。在搜索期间，和 值的计算如下：(1) 一个MAX节点的(2) 一个MIN节点的4.输赢判断算法设计因为每次导致输赢的只会是当前放置的棋子 ，输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。三、实验代码#i nclude<iostream> using n ames pace std;int num=0;int p,q;int tmpQP 33;表示该格为空，int now

6、33; const int dep th=3;void lnit() for(i nt i=0;i<3;i+) for(i nt j=0;j<3;j+) n owij=0;/记录棋盘上棋子的个数/判断是否平局/表示棋盘数据的临时数组，其中的元素0/存储当前棋盘的状态/搜索树的最大深度/初始化棋盘状态/将初值均置为0/打印棋盘当前状态void P ri ntQ P()for(i nt i=0;i<3;i+) for(i nt j=0;j<3;j+) cout< <no wij<<'t' cout<<e ndl;/用户通过

7、此函数来输入落子的位置，比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&&n owx-1y-1=0)nowx-1y-1=-1;/站在电脑一方，玩家落子置为-1else/提醒输入错误/检查是否有一方赢棋(返回0 :没有coutvv"非法输入！&

8、quot;vvendl; goto L1；int Checkwi n()任何一方赢； 1：计算机赢； -1 ：人赢) for(int i=0;i<3;i+)/ 该方法没有判断平局if(nowi0=1&&nowi1=1&&nowi2=1)|(now0i=1&&now1i=1&&no w2i=1)|(now00=1&&now11=1&&now22=1)|(now20=1&&now11=1&&n ow02=1)/ 正方行连成线return 1;if(nowi0=-1&

9、amp;&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;

10、j<3;j+) if(nowij=0) tmpQPij=1;elsetmpQPij=nowij;/ 评估当前棋盘状态的值(同时可以/ 计算机一方 将棋盘中的空格填满 for(int i=0;i<3;i+) p+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(int i=0;i<3;i+) p+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;p+=(tmpQP00+tmpQP11+tmpQP22)/3; 线p+=(tmpQP20+tmpQP11+tmpQP02)/3; for(int i=0;i<3;i+) / 计算共有多少连成/ 计算共有多少

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

12、=(tmpQP20+tmpQP11+tmpQP02)/3;return p+q;int cut(int &val,int dep,bool max)/ 计算共有多少连成 3个 1的列/计算共有多少连成 3个 1的对/ 返回评估出的棋盘状态的值/ 主算法部分，实现 a-B 剪枝的算法，val 为上一个结点的估计值， dep 为搜索深度， max 记录上一个结点是否为上确界if(dep=depth|dep+num=9) / 如果搜索深度达到最大深 度，或者深度加上当前棋子数已经达到 9，就直接调用估计函数return value();int i,j,flag,temp; 下层求得的估计值/

13、flag 记录本层的极值， temp记录bool out=false;/out 记录是否剪枝， 初始为if(max)/ 如果上一个结点是上确界，层则需要是下确界，记录 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;elsetemp=cut(fl

14、ag,dep+1,!max); / 否则继续调用 a-B 剪枝函数 / 如果下一步棋盘的估计值小于本层节点的极false本/ 双重循环，遍历棋盘所有位置/ 如果该位置上没有棋子/ 并且上一个结点为上确界，即本层为下确界/ 该位置填上用户玩家棋子/ 如果用户玩家赢了/ 置棋盘估计值为负无穷if(temp<flag) 值，则置本层极值为更小者flag=temp;if(flag<=val) 值，则不需要搜索下去，剪枝out=true;/ 如果本层的极值已经小于上一个结点的估计else 界,轮到计算机走了。nowij=1; if(Checkwin()=1) temp=10000;else/

15、 如果上一个结点为下确界，即本层为上确/ 该位置填上计算机棋子/ 如果计算机赢了/ 置棋盘估计值为无穷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;/ 根据上一个结点是否为上确界，用本层的elseif(flag<val) val=flag; return flag;int computer()int m=-1

16、0000,val=-10000,dep=1;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<<" 棋盘如下 : &q

17、uot;<<endl;PrintQP(); if(ch='n')L5:/ 函数返回的是本层的极值/m 用来存放最大的 val / 记录最佳走步的坐标/ 计算机先走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 的棋盘状态估计值 valif(Checkwin()=1) cout<<" 电脑将棋子放在 :"<<x+1<<y+

18、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(); cou

19、t<<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

20、;/ 人先走elseL4: 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(Chec

21、kwin()=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_po

22、s+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_MFCDIg:evaluate(i nt board)完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲: 若是MAX的必胜局，则e = +INFINITY，这里为+60 若是MIN则不考虑其它因素。