人工智能α-β剪枝实现的一字棋实验报告重点讲义资料

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

2、 , MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成 “三子成一线”(同一行或列或对角线全是(1)若P对任何一方来说都不是获胜的位置，则e(P)=e哪些仍为MAX空 着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对 角线的总数)(2)若P是MAX 必胜的棋局，则 e(P)= +吧(实际上赋了 60)。(3)若P是B必胜的棋局，则e(P)= -6(实际上赋了 -20)。3 .支-P剪枝算法上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值， 至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了 豆-p剪枝 技术。Q

3、邛剪枝技术的基本思想或算法是,边生成博弈树边计算评估各节点的倒 推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节 点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下:(1)对于一个与节点 MIN ,若能估计出其倒推值的上确界 肌并且这个P 值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界 a,即a>P , 则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对 MIN父 节点的倒推值已无任何影响了)。这一过程称为 &剪枝。(2)对于一个或节点 MAX ,若能估计出其倒推值的下确界 。，并且这个a

4、 值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界 P,即a>P, 则就不必再扩展该 MAX节点的其余子节点了 (因为这些节点的估值对 MAX 父节点的倒推值已无任何影响 了)。这一过程称为P剪枝。从算法中看到：(1) MAX节点(包括起始节点)的a值永不减少；(2) MIN节点(包括起始节点)的P值永不增加。在搜索期间，口和值的计算如下:(1) 一个MAX节点的：值等于其后继节点当前最大的最终倒推值。(2) 一个MIN节点的P值等于其后继节点当前最小的最终倒推值。4.输赢判断算法设计因为每次导致输赢的只会是当前放置的棋子 ，输赢算法中只需从当前点开始 扫描判断是否已经形成三

5、子。对于这个子的八个方向判断是否已经形成三子。 如 果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整 个棋盘。三、实验代码#include<iostream>using namespace std;int num=0;int p,q;int tmpQP33;表示该格为空，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/存储当前棋盘的状态/搜索树的最大

6、深度/将初值均置为0/初始化棋盘状态16void 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

7、>0&&x<4&&y>0&&y<4&&nowx-1y-1=0) nowx-1y-1=-1;else/ 站在电脑一方，玩家落子置为 -1cout<<" 非法输入 !"<<endl;goto L1;/ 提醒输入错误int Checkwin()任何一方赢； 1 ：计算机赢； -1 ：人赢)for(int i=0;i<3;i+)/ 检查是否有一方赢棋（返回 0：没有/ 该方法没有判断平局if(nowi0=1&&nowi1=1&&now

8、i2=1)|(now0i=1&&now1i=1&&now 2i=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)|(

9、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+)自己的棋子，既将棋盘数组中的for(int j=0;j<3;j+)0 变为 1/ 评估当前棋盘状态的值（同时可以/ 计算机一方将棋盘中的空格填满if(nowij=0)tmpQPij=1;elsetmpQPij=nowij;/ 计算共有多少连成3 个 1 的行/ 计算共有多少连成3 个 1 的列/ 计算共有多少连成3 个 1 的对角fo

10、r(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+) / 人一方/ 将棋盘中的空格填满自己的棋子，既将棋盘数组中的 0 变为 -1for(int j=0;j<3;j+)if(nowij=0)tmpQPij=-1;elsetmpQPij=nowij;/ 计算共有多少连成

11、3 个-1 的行/ 计算共有多少连成3 个 1 的列/ 计算共有多少连成3 个 1 的对/ 返回评估出的棋盘状态的值/ 主算法部分， 实现 a-B 剪枝的算法，max 记录上一个结点是否为上确界/ 如果搜索深度达到最大深for(int i=0;i<3;i+)q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3;for(int i=0;i<3;i+)q+=(tmpQP0i+tmpQP1i+tmpQP2i)/3;q+=(tmpQP00+tmpQP11+tmpQP22)/3;角线q+=(tmpQP20+tmpQP11+tmpQP02)/3;return p+q;int cut(i

12、nt &val,int dep,bool max)val 为上一个结点的估计值， dep 为搜索深度，if(dep=depth|dep+num=9)9，就直接调用估计函数/flag 记录本层的极值， temp 记录下/out 记录是否剪枝， 初始为 false/ 如果上一个结点是上确界，本flag 为无穷大；反之，则为记录为负无穷大度，或者深度加上当前棋子数已经达到return value();int i,j,flag,temp;层求得的估计值bool out=false;if(max)层则需要是下确界，记录flag=10000;/flag 记录本层节点的极值elseflag=-100

13、00;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)值，则置本层极值为更小者fla

14、g=temp;if(flag<=val)值，则不需要搜索下去，剪枝out=true;/ 如果下一步棋盘的估计值小于本层节点的极/ 如果本层的极值已经小于上一个结点的估计轮到计算机走了。elsenowij=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;/ 把模

15、拟下的一步棋还原，回溯if(max)极值修改上一个结点的估计值if(flag>val)/ 根据上一个结点是否为上确界，用本层的val=flag;elseif(flag<val)val=flag;return flag;/ 函数返回的是本层的极值int computer()/m 用来存放最大的 val/ 记录最佳走步的坐标int m=-10000,val=-10000,dep=1;int x_pos,y_pos;char ch;cout<<" 您希望先走吗?(y/n)"cin>>ch;while(ch!='y'&&a

16、mp;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)

17、;/ 计算机试探的走一步棋，棋盘状态改变了，在该状态下计算出深度为 dep-1 的棋盘状态估计值 valif(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;v

18、al=-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<<"平局!"<<

19、;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(in

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

21、;dep=1;cout«"电脑将棋子放在:"«x_pos+1 «y_pos+1 «endl;PrintQP();cout«endl;num+;value();if(q=o)cout«"平局!"«endl;return 0;)goto L4;)return 0;)int main()computer();system("pause");return 0;4.主要函数1估值函数估价函数：int CTic_MFCDlg:evaluate(int board口)完成功能：根

22、据输黄正盘，判断当前棋盘的估值，估价函数为前面所讲:若是 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,