2022年人工智能α-β剪枝实现的一字棋实验报告,DOC.pdf

《2022年人工智能α-β剪枝实现的一字棋实验报告,DOC.pdf》由会员分享，可在线阅读，更多相关《2022年人工智能α-β剪枝实现的一字棋实验报告,DOC.pdf（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验 5：- 剪枝实现一字棋一、实验目的学习极大极小搜索及-剪枝算法实现一字棋。二、实验原理1. 游戏规则一字棋 游戏（又叫 三子棋 或井字棋 ） ，是一款十分经典的益智小游戏。井字棋 的棋盘很简单，是一个33 的格子，很像中国文字中的井字，所以得名 井字棋 。井字棋 游戏的规则与 五子棋 十分类似， 五子棋 的规则是一方首先五子连成一线就胜利；井字棋 是一方首先三子连成一线就胜利。2. 极小极大分析法设有九个空格，由MAX ，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成三子成一线 (同一行或列或对角线全是某人的棋子 )，谁就取得了胜利。用圆圈表示MAX ，用

2、叉号代表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. -剪枝算法精品

3、资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 12 页 - - - - - - - - - - 上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。 于是在极小极大分析法的基础上提出了-剪枝技术。-剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围， 及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销， 提高了搜索效率。具体的剪枝方法如下：(1) 对于一个与节点MIN，若

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

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

6、据的临时数组，其中的元素0表示该格为空，int now33; / 存储当前棋盘的状态const int depth=3; / 搜索树的最大深度void Init() / 初始化棋盘状态for(int i=0;i3;i+) for(int j=0;j3;j+) nowij=0; / 将初值均置为0 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 12 页 - - - - - - - - - - void PrintQP() / 打印棋盘当前状态for(int i=0;i3;i+) for(int

7、 j=0;j3;j+) coutnowijt; coutendl; void playerinput() / 用户通过此函数来输入落子的位置，比如：用户输入3 1，则表示用户在第3 行第 1 列落子。int x,y; L1: cout 请输入您的棋子位置(x y):xy; if(x0&x0&y4&nowx-1y-1=0) nowx-1y-1=-1; / 站在电脑一方，玩家落子置为-1 else cout 非法输入 !endl; / 提醒输入错误goto L1; int Checkwin() / 检查是否有一方赢棋（返回0：没有任何一方赢； 1：计算机赢； -1：人赢） / 该方法没有判断平局f

8、or(int i=0;i3;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(

9、) / 评估当前棋盘状态的值（同时可以用 p 或 q 判断是否平局）p=0; q=0; for(int i=0;i3;i+) / 计算机一方将棋盘中的空格填满自己的棋子，既将棋盘数组中的0 变为 1 for(int j=0;j3;j+) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 12 页 - - - - - - - - - - if(nowij=0) tmpQPij=1; else tmpQPij=nowij; for(int i=0;i3;i+) / 计算共有多少连成3 个 1 的行p

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

11、ij; for(int i=0;i3;i+) / 计算共有多少连成3 个-1 的行q+=(tmpQPi0+tmpQPi1+tmpQPi2)/3; for(int i=0;i3;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) / 主算法部分， 实现

12、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 为无穷大；反之，则为记录为负无穷大精品资料 - - - 欢迎下载 - - - -

13、- - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 12 页 - - - - - - - - - - flag=10000; /flag记录本层节点的极值else flag=-10000; for(i=0;i3 & !out;i+) / 双重循环，遍历棋盘所有位置for(j=0;j3 & !out;j+) if(nowij=0) / 如果该位置上没有棋子if(max) / 并且上一个结点为上确界，即本层为下确界,轮到用户玩家走了。nowij=-1; / 该位置填上用户玩家棋子if(Checkwin()=-1) / 如果用户玩家赢了temp=-1

14、0000; / 置棋盘估计值为负无穷else temp=cut(flag,dep+1,!max); /否则继续调用a-B 剪枝函数if(tempflag) / 如果下一步棋盘的估计值小于本层节点的极值，则置本层极值为更小者flag=temp; if(flagflag) flag=temp; if(flag=val) out=true; nowij=0; / 把模拟下的一步棋还原，回溯 if(max) / 根据上一个结点是否为上确界，用本层的极值修改上一个结点的估计值if(flagval) val=flag; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载

15、名师归纳 - - - - - - - - - -第 5 页，共 12 页 - - - - - - - - - - else if(flagval) val=flag; return flag; / 函数返回的是本层的极值 int computer() int m=-10000,val=-10000,dep=1; /m用来存放最大的val int x_pos,y_pos; / 记录最佳走步的坐标char ch; coutch; while(ch!=y&ch!=n) cout 非法输入 ! 您希望先走吗 (y/n)ch; system(cls); Init(); cout 棋盘如下 : endl;

16、 PrintQP(); if(ch=n) / 计算机先走L5: for(int x=0;x3;x+) for(int y=0;y3;y+) if(nowxy=0) nowxy=1; cut(val,dep,1); / 计算机试探的走一步棋，棋盘状态改变了，在该状态下计算出深度为dep-1 的棋盘状态估计值val if(Checkwin()=1) cout 电脑将棋子放在:x+1y+1endl; PrintQP(); cout 电脑获胜 ! 游戏结束 .m) /m要记录通过试探求得的棋盘状态的最大估计值m=val; x_pos=x;y_pos=y; val=-10000; nowxy=0; 精品

17、资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 12 页 - - - - - - - - - - nowx_posy_pos=1; val=-10000; m=-10000; dep=1; cout 电脑将棋子放在:x_pos+1y_pos+1endl; PrintQP(); coutendl; num+; value(); if(p=0) cout 平局 !endl; return 0; playerinput(); / 玩家走一步棋PrintQP(); coutendl; num+; valu

18、e(); if(p=0) cout 平局 !endl; return 0; if(Checkwin()=-1) cout 您获胜 ! 游戏结束 .endl; return 0; goto L5; else / 人先走L4: playerinput(); PrintQP(); coutendl; num+; value(); if(q=0) cout 平局 !endl; return 0; if (Checkwin()=-1) cout 您获胜 ! 游戏结束 .endl; return 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - -

19、- - - - - - - -第 7 页，共 12 页 - - - - - - - - - - for(int x=0;x3;x+) for(int y=0;y3;y+) if(nowxy=0) nowxy=1; cut(val,dep,1); if(Checkwin()=1) cout 电脑将棋子放在:x+1y+1endl; PrintQP(); cout 电脑获胜 ! 游戏结束 .m) m=val; x_pos=x;y_pos=y; val=-10000; nowxy=0; nowx_posy_pos=1; val=-10000; m=-10000; dep=1; cout 电脑将棋子放在

20、:x_pos+1y_pos+1endl; PrintQP(); coutendl; num+; value(); if(q=0) cout 平局 !endl; return 0; goto L4; return 0; int main() computer(); system(pause); return 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 12 页 - - - - - - - - - - 4. 主要函数1 估值函数估价函数： int CTic_MFCDlg:evaluate

21、(int board) 完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是 MAX 的必胜局，则e = +INFINITY ，这里为 +60 若是 MIN 的必胜局，则e = -INFINITY ，这里为 -20，这样赋值的原因是机器若赢了，则不考虑其它因素。其它情况，棋盘上能使CUMPUTER 成三子一线的数目为e1 棋盘上能使PLAYER 成三子一线的数目为e2，e1-e2 作为最终权值参数：board:待评估棋盘返回：评估结果精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，

22、共 12 页 - - - - - - - - - - 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

23、值，第一次调用默认 +100 result :输出结果返回： 若当前点为MAX 节点，则返回alpha 值；若当前点为MIN 节点，则返回beta 值. 判断胜负int CTic_MFCDlg:isWin(int curPos) 完成功能：根据输入棋盘，判断当前棋盘的结果，COMPUTER 胜？ PLAYER 胜？平局？参数： board:待评估棋盘返回： -1 表示：尚未结束0 表示：平局精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 12 页 - - - - - - - - - - 1

24、表示： PLAYER 胜2 表示： COMPUTER 胜五、实验截图精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 12 页 - - - - - - - - - - 六、实验总结通过本次实验进一步对老师课堂上所讲的 -剪枝有了更加深刻的了解，对它的一般实现有了初步的认识。搜索深度并非越深越好， 局限于估值函数是根据能够成三子一线的数目决定的，所以搜索到最后一层，如果有人胜，则出现，如果没人胜，则三子一线数目为0，所以毫无意义。这也是为什么大多数情况下都是平局的原因。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 12 页 - - - - - - - - - -