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

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

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

2、左图中就是 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)对于一个与节点 MIN，若能估计出其倒推值的上确界，并且这个 值不大于 MIN 的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展该 MIN 节 点的其余子节点了(因为这些节点的估值对 MIN 父节点的倒推值已无任何影响了)。这一过程称为 剪枝。(

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

5、输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。三、实验代码#include using namespace std;int num=0;m)endl;return 0;goto L5;else endl;return 0;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电脑

6、获胜!游戏结束.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+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;4.主要函数 1 估值函数 估价函数：int CTic_MFCDlg:evaluate(int board)完

7、成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是 MAX 的必胜局，则 e=+INFINITY，这里为+60 若是 MIN 的必胜局，则 e=-INFINITY，这里为-20，这样赋值的原因是机器若赢了，则不考虑其它因素。其它情况，棋盘上能使 CUMPUTER 成三子一线的数目为 e1 棋盘上能使 PLAYER成三子一线的数目为 e2，e1-e2 作为最终权值 参数：board:待评估棋盘 返回：评估结果 剪枝算法 AlphaBeta 剪枝主函数：int CTic_MFCDlg:AlphaBeta(int Board,int Depth,int turn,int Alpha,

8、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 胜 五、实验截图 六、实验总结 通过本次实验进一步对老师课堂上所讲的-剪枝有了更加深刻的了解，对它的一般实现有了初步的认识。搜索深度并非越深越好，局限于估值函数是根据能够成三子一线的数目决定的，所以搜索到最后一层，如果有人胜，则出现 ，如果没人胜，则三子一线数目为 0，所以毫无意义。这也是为什么大多数情况下都是平局的原因。