α-β剪枝实现的一字棋实验报告(共10页).doc

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

1、精选优质文档-倾情为你奉上人工智能大作业极大极小算法和a -b剪枝实现一字棋学院： 班级：姓名：学号：辅导老师：日期：目录一、实验目的 (1) 学习极大极小搜索及a -b 剪枝。(2) 利用学到的算法实现一字棋。二、实验环境(1) 硬件环境：网络环境中的微型计算机。 (2) 软件环境：Windows 操作系统，Microsoft Visual C+语言。三、实验原理3.1 游戏规则一字棋游戏（又叫三子棋或井字棋），是一款十分经典的益智小游戏。井字棋 的棋盘很简单，是一个 33 的格子，很像中国文字中的井字，所以得名井字棋。井字棋游戏的规则与五子棋十分类似，五子棋的规则是一方首先五子连成一线就胜

2、利；井字棋是一方首先三子连成一线就胜利。 井字棋（英文名 Tic-Tac-Toe） 井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。3.2 极小极大分析法设有九个空格，由 MAX，MIN 二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成三子成一线(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 用圆圈表示 MAX，用叉号代表 MIN。 比如左图中就是 MAX 取胜的棋局。估价函数定义如下： 设棋局为 P，估价函数为 e(P)。(1) 若 P

3、对任何一方来说都不是获胜的位置，则 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 a -b剪枝算法上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法

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

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

6、次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。四、数据结构4.1 程序流程4.2 主要成员函数4.2.1 估值函数估价函数：int CTic_MFCDlg:evaluate(int board) 完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是 MAX 的必胜局，则 e = +INFINITY，这里为+60 若是 MIN 的必胜局，则 e = -INFINITY，这里为-20，这样赋值的原因是机器若赢了，则不考虑其

7、它因素。其它情况，棋盘上能使 CUMPUTER 成三子一线的数目为 e1棋盘上能使 PLAYER成三子一线的数目为 e2，e1-e2 作为最终权值参数： board:待评估棋盘 返回： 评估结果4.2.2 Alpha-Beta 剪枝算法AlphaBeta 剪枝主函数： int CTic_MFCDlg:AlphaBeta(int Board, int Depth, int turn, int Alpha, int Beta, int *result) 完成功能：根据输入棋盘，搜索深度，及其他参数，给出一个相应的最优解，存入 result 中。参数：board :待评估棋盘 Depth :搜索深度

8、 turn :当前是机器走(MAX 结点)还是玩家走(MIN 结点) Alpha :alpha 值，第一次调用默认-100 Beta :beta 值，第一次调用默认+100 result :输出结果 返回：若当前点为 MAX 节点，则返回 alpha 值； 若当前点为 MIN 节点，则返回 beta 值4.2.3 判断胜负int CTic_MFCDlg:isWin(int curPos)完成功能：根据输入棋盘，判断当前棋盘的结果，COMPUTER 胜？PLAYER 胜？平局？参数：board:待评估棋盘 返回：-1 表示：尚未结束 0 表示：平局 1 表示：PLAYER 胜 2 表示：COMP

9、UTER 胜 4.2.4 鼠标左键响应void CTic_MFCDlg:OnLButtonDown(UINT nFlags, CPoint point) 完成功能：鼠标左键相应，在点击的那格放置玩家棋子，之后再相应计算机走下一步4.2.5 Draw 系列函数void CTic_MFCDlg:DrawBoard(CDC *pDC)完成功能：根据 Chess 棋盘数组 画出棋盘void CTic_MFCDlg:DrawO(CDC *pDC, int Pos) 完成功能：在棋盘上画一个 O，电脑void CTic_MFCDlg:DrawX(CDC *pDC, int Pos)完成功能：在棋盘上画一个

10、 X，玩家4.2.6 COMPUTER or PLAYER 先走void CTic_MFCDlg:OnStartCom() 完成功能：计算机先走void CTic_MFCDlg:OnStartPly()完成功能：玩家先走五、实验内容5.1 基本功能简介本实验的界面采用 C+的 MFC 完成，总的界面如下，有以下功能： 1. 搜索树深度的设置；2. 机器先走或者玩家先走；3. 游戏胜负或者平局判断。 4鼠标在游戏开始之前或者结束之后点击棋盘不会有相应，并会提示用户先开始游戏； 5鼠标点击棋盘区域之外，不会有相应 6搜索深度已经设置区域 7同一棋盘格子点击只响应一次这里需要说明的是，搜索深度并非越

11、深越好，局限于估值函数是根据能够成三子一线的数目决定的，所以搜索到最后一层，如果有人胜，则出现 ，如果没人胜，则三子一线数目为 0，所以毫无意义。如果搜索深度取到 4 或者以上，会发现电脑会走出一些很 笨 的棋，就是这个原因。经测试发现，搜索深度为2时效果最好，这也是我为什么默认值取 2 的原因。5.2 流程图.5.2.1 估价函数5.2.2 Alpha-Beta 剪枝六、实验小结通过本次实验进一步对老师课堂上所讲的 AlphaBeta 剪枝有了更加深刻的了解，对它的一般实现有了初步的认识。 复习了大二时所学习的 C+语言，并且对 MFC 程序设计有了更深的了解。 七、实验源代码源代码见附件一字棋程序。专心-专注-专业