#α-β剪枝实现的一字棋实验评测报告

1、人工智能大作业 极大极小算法和- 剪枝实现一字棋学院：班级：姓名：学号：辅导老师：日期： 目录一、实验目的 3二、实验环境 3三、实验原理 3游戏规则 3极小极大分析法 3- 剪枝算法 4输赢判断算法设计 5四、数据结构 5程序流程 5主要成员函数 5估值函数 5Alpha-Beta 剪枝算法 6判断胜负 6鼠标左键响应 6Draw 系列函数 6COMPUTER or PLAYER 先走 7五、实验内容 7基本功能简介 7流程图 .85.2.1 估价函数 8Alpha-Beta 剪枝 9六、实验小结 10七、实验源代码 10、实验目的(1 学习极大极小搜索及 - 剪枝(2 利用学到的算法实现一

2、字棋。二、实验环境(1 硬件环境：网络环境中的微型计算机。(2 软件环境： Windows 操作系统， Microsoft Visual C+ 语言。三、实验原理游戏规则一字棋游戏又叫三子棋 或井字棋)，是一款十分经典的益智小游戏。 井字棋 的棋盘很简单，是一个33的格子，很像中国文字中的 井字，所以得名 井字棋 。井字棋 游戏的规则与 五子棋 十 分类似， 五子棋 的规则是一方首先五子连成一线就胜利；井字棋 是一方首先三子连成一线就胜利。井字棋 ，谁就取得了胜利。用圆圈表示 MAX ，用叉号代表 MIN 。 比如左图中就是 MAX 取胜的棋局。 估价函数定义如下： 设棋局为 P，估价函数为

3、e(P。(1 若 P 对任何一方来说都不是获胜的位置，则e(P=e(那些仍为MAX空着的完全的行、列或对角线的总数 -e(那些仍为 MIN 空着的完全的行、列或对角线的总数 2 / 9（2 若 P 是 MAX 必胜的棋局，则 e（P + 若 P 是 B 必胜的棋局，则 e（P - =5-4=1剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估 出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上 的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：（1 对于一个与节点 MIN ，若能估计出其倒推值的上确界 ，并且这个 值不大

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

5、值的计算如下：（1 一个 MAX 节点的 值等于其后继节点当前最大的最终倒推值。（2 一个 MIN 节点的 值等于其后继节点当前最小的最终倒推值。输赢判断算法设计因为每次导致输赢的只会是当前放置的棋子 , 输赢算法中只需从当前点开始扫描判断是 否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方 胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。四、数据结构程序流程主要成员函数估值函数估价函数： int CTic_MFCDlg:evaluate(int board 完成功能：根据输入棋盘，判断当前棋盘的估值，估价函数为前面所讲：若是 MAX 的必胜局，则 e

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

7、t 完成功能：根据输入棋盘，搜索深度，及其他参数，给出一个相应的最优解，存入 result中。 参数：board :待评估棋盘Depth :搜索深度turn :当前是机器走 (MAX 结点 还是玩家走 (MIN 结点 Alpha :alpha 值，第一次调用默认 -100Beta :beta 值，第一次调用默认 +100 result : 输出结果返回：若当前点为 MAX 节点，则返回 alpha 值； 若当前点为 MIN 节点，则返回 beta 值判断胜负int CTic_MFCDlg:isWin(int curPos 完成功能：根据输入棋盘，判断当前棋盘的结果， COMPUTER 胜？ P

8、LAYER 胜？平局？参数：board:待评估棋盘返回：-1 表示：尚未结束0 表示：平局1 表示： PLAYER 胜2 表示： COMPUTER 胜鼠标左键响应void CTic_MFCDlg:OnLButtonDown(UINT nFlags, CPoint point 完成功能：鼠标左键相应，在点击的那格放置玩家棋子，之后再相应计算机走下一步Draw 系列函数void CTic_MFCDlg:DrawBoard(CDC *pDC 完成功能：根据 Chess 棋盘数组 画出棋盘void CTic_MFCDlg:DrawO(CDC *pDC, int Pos 完成功能：在棋盘上画一个 O，电

9、脑void CTic_MFCDlg:DrawX(CDC *pDC, int Pos 完成功能：在棋盘上画一个X ，玩家COMPUTER or PLAYER先 走void CTic_MFCDlg:OnStartCom( 完成功能：计算机先走 void CTic_MFCDlg:OnStartPly( 完成功能：玩家先走五、实验内容5.1 基本功能简介本实验的界面采用 C+ 的 MFC 完成，总的界面如下，有以下功能：搜索树深度的设置；机器先走或者玩家先走；游戏胜负或者平局判断。4鼠标在游戏开始之前或者结束之后点击棋盘不会有相应，并会提示用户先开始游戏5鼠标点击棋盘区域之外，不会有相应6搜索深度已经设置区域7同一棋盘格子点击只响应一次这里需要说明的是，搜索深度 并非越深越好，局限于估值函数是 根据能够成三子一线的数目决定的 ，所以搜索到最后一层，如果有人 胜，则出现 ，如果没人胜，则 三子一线数目为 0，所以毫无意义。如果搜索深度取 到4 或者以上，会发现电脑会走出一些 很 笨的棋，就是这个原因。经测试发现，搜索深度为 2时效果最好，这也是我为什么默认值取2 的原因。5.2 流程图 .5