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

1、人工智能大作业-极大极小算法和a乍剪枝实现一字棋学院班级：姓名：学号：辅导老师：日期： 目录TOC o 1-5 h z HYPERLINK l bookmark6 一、实验目的3 HYPERLINK l bookmark8 二、实验环境3 HYPERLINK l bookmark12 三、实验原理3游戏规则3极小极大分析法3Q-卩剪枝算法4输赢判断算法设计5 HYPERLINK l bookmark16 四、数据结构5程序流程5 HYPERLINK l bookmark18 主要成员函数5 HYPERLINK l bookmark20 估值函数5 HYPERLINK l bookmark22

2、Alpha-Beta剪枝算法6 HYPERLINK l bookmark24 判断胜负6鼠标左键响应6 HYPERLINK l bookmark26 Draw系列函数6 HYPERLINK l bookmark32 COMPUTERorPLAYER先走7 HYPERLINK l bookmark38 五、实验内容7基本功能简介7流程图8 HYPERLINK l bookmark40 5.2.1估价函数8 HYPERLINK l bookmark42 Alpha-Beta剪枝9 HYPERLINK l bookmark44 六、实验小结10 HYPERLINK l bookmark46 七、实验

3、源代码10、实验目的学习极大极小搜索及a-卩剪枝。利用学到的算法实现一字棋。二、实验环境(1)硬件环境：网络环境中的微型计算机。(2)软件环境：Windows操作系统，MicrosoftVisualC+语言。三、实验原理游戏规则一字棋游戏(又叫三子棋或井字棋)，是一款十分经典的益智小游戏。井字棋的棋盘很简单，是一个3X3的格子，很像中国文字中的井字，所以得名井字棋。”井字棋游戏的规则与五子棋十分类似，五子棋的规则是一方首先五子连成一线就胜利；井字棋是一方首先三子连成一线就胜利。井字棋(英文名Tic-Tac-Toe)井字棋的出现年代估计已不可考，西方人认为这是由古罗马人发明的；但我们中国人认为，

4、既然咱们都发明了围棋、五子棋，那发明个把井字棋自然是不在话下。这些纯粹是口舌之争了，暂且不提。极小极大分析法设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成三子成一线(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。用圆圈表示MAX,用叉号代表MIN。比如左图中就是MAX取胜的棋局。估价函数定义如下：设棋局为P,估价函数为e(P)。若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数)若P是MAX必胜的棋局，则e(P)=+x(实际上赋了60

5、)。若P是B必胜的棋局，则e(P)=-x(实际上赋了-20)。需要说明的是，+8赋60,-g赋-20的原因是机器若赢了，则不论玩家下一步是否会赢，都会走这步必赢棋。上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，至使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了*卩剪枝技术。a-卩剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：对于一个与节点MIN,若能估计出其倒推值的上确界卩，并且这个卩值

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

7、点当前最大的最终倒推值。一个MIN节点的卩值等于其后继节点当前最小的最终倒推值。3.4输赢判断算法设计因为每次导致输赢的只会是当前放置的棋子,输赢算法中只需从当前点开始扫描判断是否已经形成三子。对于这个子的八个方向判断是否已经形成三子。如果有，则说明有一方胜利，如果没有则继续搜索，直到有一方胜利或者搜索完整个棋盘。四、数据结构程序流程Y.电脑先匕赛结束负平）赛结束负平根据玩家鼠标点击位置下棋丘赛结束，提示書果信息调用AlphaBeta函数计算下一步落子位置调MAlphaBeta函数计算下一步落子位置用户输入搜索深度（默认为2）选择玩家先或电脑先开始游戏显示棋盘4.2主要成员函数估值函数估价函数

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

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

10、ER胜？PLAYER胜？平局?4.2.4鼠标左键响应参数：board:待评估棋盘返回：-1表示：尚未结束0表示：平局1表示：PLAYER胜2表示：COMPUTER胜voidCTic_MFCDlg:OnLButtonDown(UINTnFlags,CPointpoint)完成功能：鼠标左键相应，在点击的那格放置玩家棋子，之后再相应计算机走下一步4.2.5Draw系列函数voidCTic_MFCDlg:DrawBoard(CDC*pDC)完成功能：根据Chess棋盘数组画出棋盘voidCTic_MFCDlg:DrawO(CDC*pDC,intPos)完成功能：在棋盘上画一个O,电脑voidCTic

11、_MFCDlg:DrawX(CDC*pDC,intPos)完成功能：在棋盘上画一个X,玩家4.2.6COMPUTERorPLAYER先走voidCTic_MFCDlg:OnStartCom()完成功能：计算机先走voidCTic_MFCDlg:OnStartPly()完成功能：玩家先走五、实验内容基本功能简介本实验的界面采用C+的MFC完成，总的界面如下，有以下功能：搜索树深度的设置；机器先走或者玩家先走；游戏胜负或者平局判断。4鼠标在游戏开始之前或者结束之后点击棋盘不会有相应，并会提示用户先开始游戏；5鼠标点击棋盘区域之外，不会有相应6搜索深度已经设置区域7.同一棋盘格子点击只响应一次这里需

12、要说明的是，搜索深度并非越深越好，局限于估值函数是根据能够成三子一线的数目决定的，所以搜索到最后一层，如果有人胜，则出现，如果没人胜，则三子一线数目为0，所以毫无意义。如果搜索深度取到4或者以上，会发现电脑会走出一些很笨的棋，就是这个原因。经测试发现，搜索深度为2时效果最好，这也是我为什么默认值取2的原因。5.2流程图.5.2.1估价函数泉否判斷了每一.三子连线可能取下一种三子连线情况若机器未出现三子连洙井且有可能出现Result+=l若玩家未出现三子连洙井且有可能出现Result+=lC退回ResultJEM厂START莎姑化血suit为。若玩家出现三子连珠,赋-孔作无穷小Result+=-20若机器现三于连洙.赋丸柞无穷大Result+=605.2.2Alpha-Beta剪枝Y-START接收参数及初始化前节点杲极值的节点-N有可能的有可能的袪？scoreAlpha生成新节点（即放下一步棋）主成新节点即放下一步棋）取极小值Beta=score取极大憤Alpha=score递归搜索子节点，得到估价值孔ore递归瘦索子节点，得