人工智能五子棋设计.doc

毕业设计论文博弈算法的设计及其实现摘 要计算机诞生的目的之一是要帮助人类思考，人工智能就是以此为目标的计算机科学，以实现人类智能为最终目标。个人认为现阶段，人工智能的应用仍然以计算机自动处理事务为主，实现真正人工智能仍然遥远。机器博弈是人工智能研究的一个重要分枝，它实现计算机自动对弈，它的核心是博弈算法，计算机通过判断当前棋盘的状态，然后按照博弈的规则试着产生很多走法，而选择其中一个相对比较好的走法。本设计以五子棋游戏规则实现，五子棋游戏的棋盘表示简单，1515的格子，棋子也只有两种，若不考虑禁手，规则也很简单，只要一方有五个棋子连成一条线则赢，故很适合用来实现算法。在本次设计中，实现了几种经典算法，同时，根据实际游戏规则，对这些算法作一定程度的改进，使它们更加简单高效。本设计采用C+语言实现，以visual c+作为开发工具。关键词：人工智能，自动处理，机器博弈，五子棋，visual C+ABSTRACTArtifical Intelligence(AI) is the intelligence of machines and the branch of computer science that aims to create it.Personally think that at this stage, the application of artificial intelligence to automatic processing affairs mainly, realize the true artificial intelligence is still far away. The game machine is an important branch ofartificial intelligence research, It realizes the automatic computer game. game algorithm is its core Computer looks at current state of the chess board, according rules of the game to try to put chess, and choice a good way. I implement this design by Gobang, Gobang game rule is very imple, I realized several classical algorithm of game machine, and made some improvement of these algorithms. The design using C+ language, using visual C+ 2005 as a development tool.KEYWORDS:AI, Automatic processing,The Game Machine,Gobang,Visual C+6目录第1章 引言51.1 人工智能51.2 人机博弈和五子棋51.3 Visual C+6第2章 需求分析72.1 使用范围要求72.2 功能要求72.3 系统平台要求7第3章 人机界面设计8第4章 面向对象分析114.1 对象设计114.2 动态模型124.3 功能模型12第5章 面向对象设计145.1 类设计145.2 控制流程15第6章 详细设计及编码176.1 全局数据176.2 游戏循环176.3 界面设计及事件处理176.4 人类玩家的Think操作19第7章 计算机智能设计207.1 棋局估值207.2 极大极小值算法217.3 Alpha-beta算法247.4 Alpha-beta算法的窗口效应287.5 极小窗口搜索/PVS算法297.6 预估排序和历史启发307.7 有限范围限定337.8 多核优化33第8章 总结结论358.1 各算法效率对比358.2 成果与不足36参考文献37致谢38第1章 引言1.1 人工智能提到人工智能，可能最著名的便是1997年超级计算机“深蓝”战胜国际象棋冠军卡斯帕罗夫的事，可以说“深蓝”的获胜是人工智能影响力的一个里程碑。对于什么是人工智能，有很多定义，我认为就是能自动完成人类所能完成的一些思维活动。如果从这个意义上说的话，计算机学科所要解决的所有问题都与人工智能有关。它的发展历史和计算机科学的发展历史是联系在一起的，但也不仅仅局限于计算机科学，也涉及到心理学、哲学、语言学、医学等很多门学科。它所包含的内容有：知识表示、自动推理和搜索方法、机器学习和知识获取、知识处理系统、自然语言理解、计算机视觉、智能机器人、自动程序设计等方面。1.2 人机博弈和五子棋人机博弈就是人和计算机下棋，其重点在于计算机如何实现对弈，它是人工智能研究的一个重要分枝，五子棋是一种对弈游戏，本设计的目的就是通过五子棋这种对弈游戏初步探索实现博弈算法，为将来的人工智能研究打下一个基础，其实现方法可以从以下几方面概述：1、 棋盘状态 用一种数学模型来表示当前棋局的状态，不同的对弈游戏有不同的表示方法，本设计用五子棋这种游戏来实现，它的棋盘状态比较简单，可以用一个15*15的二维数组表示15*15的棋盘，某棋盘上位置的状态就用该数组中单元的数字表示，比如1表示黑子，0表示白子，-1表示空位。2、 对弈规则 每种对弈游戏都有不同的规则，规定了棋子的走法（如象棋）或者能下子的位置以及胜负的判定。五子棋的规则很简单，如果不考虑禁手，任意空位都可以放棋子，只要一方有五个棋子连成一线，则判胜。3、 搜索技术 要让计算机在下棋中有智能，搜索技术是至关重要的，简单的说就是让计算机试着某步走法，这一步走了之后，再往后走若干步，按照某种规则给这一步评分，最后，在所有走法中选择一个相对最佳的走法。4、 棋局估值 就是对某一种棋盘局面的优劣作出评价，简单地就是说走某一步棋后，这一步棋走得好不好。它在博弈技术中也是很重要的，从某种意义上来说，搜索也是为了估值，或者说对估值作修正。1.3 Visual C+ 本次的开发工具为Microsoft visual c+ 2005，它是微软公司推出的win32的开发工具，本次实现之所以选用Visual C+作为开发工具，除因个人使用习惯外，主要是它生成的代码高效，具有灵活方便的类管理，以及界面设计的可视化特点。另外，在Visual C+ 2005中引入了OpenMp的支持，OpenMp为快速开发具有多核优化的程序提供简单方便的支持，使得博弈程序更加高效。第2章 需求分析2.1 使用范围要求五子棋规则简单，男女老幼都可以玩，不但能让人们在对弈过程中得到娱乐，而且还能开发智力。2.2 功能要求1、支持人机对战。2、能设置计算机智能等级。3、能保存棋局状态，同时也能读入上一次保存的棋局状态，并且能够接着上一次继续下棋。4、能悔棋，即玩家在下错子后能回到上一步。5、背景音乐和下棋音效。2.3 系统平台要求编程语言：C+操作系统：windows开发工具：microsoft Visual C+7毕业设计论文博弈算法的设计及其实现第3章 人机界面设计图3.1 五子棋程序界面如图3.1，在左边的为1515的棋盘，右边的“黑子”和“白子”下接列表框设定持黑子和白子的玩家类型，各有三项，分别是“人”，“计算机”，“当选择“人”后，就可以用鼠标在棋盘下放该类型的棋子，当为“计算机”，则由计算机自动产生走法并在棋盘上下该种类型的棋子，并且会弹出一个选择智力级别的对话框。图3.2 计算机智力等级设定对话框在玩的过程中，如果不想玩了，可以把当前棋局保存下来，按保存按钮，此时弹出保存棋局对话框图3.3 保存棋局对话框要载入以往的棋局继续玩，点击载入按钮，此时显示载入棋局对话框，选择以往的棋局文件即可。图3.4 打开棋局对话框如果不想玩此局了，则可按新局按钮，此时弹出“确认新局”对话框让用户确认：图3.5 重新开始对话框选择是将开始新局，否返回到旧局继续下。如果退出程序，此时显示“确认退出”对话框。图3.6 是否退出对话框选择“是”按钮则退出，“否”继续下。10第4章 面向对象分析4.1 对象设计根据需求分析中的要求，初步的对象设计如下：11对手下棋棋盘玩家12人玩家计算机玩家图4.1各对象说明如下：1、棋盘对象：表示1515的五子棋棋盘，表示上面放了哪些子以及它们的位置，或者是每一个位置放了什么子。其属性如下：（1） Board，记录棋盘上各棋子的位置信息。（2） BlackPlayer，表示持黑棋的玩家。（3） WhitePlayer，表示持白棋的玩家。（4） CurrentPlayer，指针，表示当前该下子的玩家。2、玩家对象：表示下棋者，可以是人，计算机，一个棋盘对象对应两个玩家对象。其属性如下：（1）Side，表示该玩家所持什么棋子。3、人玩家对象，该类继承自玩家类，这个对象代表利用程序界面进行下棋的人。4、计算机玩家对象，该对象继承自玩家对象，这个对象通过计算产生一个走法。4.2 动态模型棋盘的动态模型持白子玩家下子持黑子玩家下子开始黑子玩家胜利do:显示胜利信息开始新局持黑子玩家下子等待持黑子玩家下子do:接收下子持黑子玩家下子持白子玩家下子白子玩家胜利do:显示胜利信息开始新局持白子玩家下子和局do:显示和局信息开始新局等待持白子玩家下子do:接收下子图4.2 动态模型图4.3 功能模型1、系统输入输出值棋盘状态棋局文件悔棋请求下子位置棋盘状态棋盘玩家图4.3.1 功能模型图2、下棋数据流图下棋数据流图（0层）该局结束1棋盘坐标棋盘接收下子是否结束棋盘坐标23玩家接收棋局状态并产生走法棋局信息无效棋盘坐标图4.3.2 下棋数据流图说明：接收棋局状态并产生走法：该操作由相应的玩家对象负责，玩家接收当前棋局的状态并产生下子的位置，即棋盘坐标。不同类的玩家该操作有所不同。接收下子：该操作由棋盘对象负责，它接收玩家发来的下子位置，同时判断是否合法，不合法则不作任何操作，合法则改变棋盘状态，以及把当前玩家更改为另一方。是否结束：该操作判断当前游戏是否结束，以及哪一方结束。36第5章 面向对象设计5.1 类设计 由五子棋程序面向对象分析可得出该程序一共有四个类。1、棋盘类(1)属性board：表示1515棋盘，可用一个二维数组表示int board1515;pBlackPlayer,pWhitePlayer,pCurrentPlayer：分别表示持黑子的玩家和持白子的玩家以及指向当前应下子玩家的指针。stack chessStack，记录下子位置的堆栈，以便于悔棋操作。（2）操作bool PutChess(int x,int y,int side)，接受下子，如果下子位置以及棋子正确则改变棋盘，并把当前玩家指向对方。Undo()，接受玩家的悔棋，恢复棋盘到该玩家上次应下子的状态。SaveBoard(char filename)，把当前的棋局保存到filename指定的文件中。LoadBoard(char filename)，从指定的文件装入棋局。void NewRound(void),开始新局清空所有棋子，清空历史走法，把当前轮次玩家置为黑方。int IsGameOver();/游戏是否结束，返回1表示黑方胜利，返回2表示白方胜利，返回3表示和局，0表示游戏仍然进行。其C的类定义如下：class CChessBoard int board1515;/表示1515棋盘stack chessStack;CPlayer *pBlackPlayer,*pWhitePlayer,*pCurrentPlayer;Int IsGameOver(void);/判断游戏是否已经结束，没有则返回0，否则返回哪方胜利 void NewRound(void);public: bool PutChess(int x,int y,char side);/所指定位置可以放相当的棋子返回true，否则false bool Undo(void);bool SaveBoard(char filename);/保存棋盘到指定的文件中，如果成功返回truebool LoadBoard(char filename);/从filename中装入棋盘，如果成功返回true。 2、玩家类，它表示玩家，它是一个纯虚类，为“人”、“计算机”玩家的公共接口。（1）属性：Side，表示该玩家所持什么棋子。（2）操作：POINT Think(char board1515)，根据传入的棋盘状态产生走法。其C定义如下：class CPlayer int Side;/该玩家所持何子public: virtual POINT Think(char board15)=0;/根据传入的棋盘信息产生一种走法 cPlayer(char side) Side=side; cPlayer(); ;5.2 控制流程1、由于在Windows环境下程序采用事件驱动，因此，整个程序采用事件驱动机制，而这一控制最好放在消息循环中。2、在界面建立时把设置玩家对象的列表框都选择为人玩家对象，并建立人玩家对象，并调用该函数在改变设置玩家对象的下拉列表框时调用，用来设置好玩家对象。3、改变玩家对象时所进行的操作，用户在改变玩家对象的下拉列表框中选择了另一种玩家对象时，系统会调用相应的事件处理函数，在该函数中删除原有的玩家对象，并创建一个新的玩家对象。4、在游戏循环中，每当有一个玩家由Think()操作得到了一个下子位置，然后就调用棋盘类的PutChess()来下子，该函数检查下子位置是否合法，如果不合法，则什么也不做，直接返回。如果合法，则更新棋盘数据，画该棋子，如果该方胜利，则显示胜利信息并开始新局，否则把当前玩家设为对方。第6章 详细设计及编码6.1 全局数据CChessBoard类的对象chessBoard为一全局对象，表示棋盘。6.2 游戏循环游戏进程的调度在游戏循环中完成，在windows程序中，最适合的位置就是消息循环处理中。而基于对话框的程序有自己的消息循环，在消息循环中要调用ContinueDodal()函数，帮游戏循环合适在这一函数中处理，代码如下：BOOL CFiveChessDlg:ContinueModal()POINT point=chessBoard.pCurrentPlayer-Think(chessBoard.board);if(chessBoard.PutChess(point)this-Invalidate();/重绘棋盘int side=chessBoard.IsGameOver();if(side)/游戏结束显示游戏结束信息return CDialog:ContinueModal();6.3 界面设计及事件处理 应用程序框架采用基于MFC的对话框程序，使用AppWizard建立好后，添加好各控件，对话框的类名为CFiveChessDlg。如下图所示：图6.3.1 五子棋程序界面1、 黑方，白方下拉列表框黑白下拉列表框在CFiveChessDlg类中类型为CComboBox类的成员对象， 名称分别为m_comboBlack、m_comboWhite;为两个下拉列表框里面有“人”和“计算机”两项，默认是“人”这一项，用户重新选择玩家类型时，则改变玩家类型，如果是计算机玩家，则弹出设置计算机等级对话框（用CLevelDlg对话框类表示），确认后创建相应等级的计算机玩家。图6.3.2 设置计算机智力对话框2、 悔棋、新局、保存、载入、退出按钮在棋盘类（CChessBoard）中用一个栈来保存下棋历史，该栈中数据元素为POINT类型，悔棋时进行出栈操作，每次出栈两个棋子位置，将它们对应棋盘坐标设置为无子(NONE)。新局操作将棋盘所有位置设置为无子(NONE)，清空下子历史栈，将当前玩家设置为黑方。保存按钮按下后先弹出一个保存文件的对话框。文件扩展名为fsv，用户指定文件名按确定后，先写入4字节的文件标识(f,i,v,e),然后写入棋盘数据(board1515)，再写入下子位置历史栈，栈因为顺序是相反的，为以后载入方便，这里又建立了一个栈，将数据倒置后再保存。载入与保存一致，先读取文件标识，如果标识不对，则不载入，然后载入棋盘数据，再载入历史栈，然后根据历史栈中最后一个模棋子设置好当前玩家。退出实际上是对话框的OK按钮，点击后直接退出。3、 棋盘的绘制棋盘的绘制在CFiveChessDlg类中的重绘函数（OnPaint）中处理，先用画线函数画好棋盘网格，15*15个格，从坐标（15，15）处绘制，每格30象素。棋盘绘制好后绘制棋子，扫描全局对象chessBoard中棋盘数据board1515，绘制出所有棋子。另外，从历史栈中取出最后一次下子坐标，将棋子外线用红色绘制。4、 鼠标消息的处理为记录下人玩家的下子位置，需要处理鼠标消息，这通过重载OnLButtonDown函数实现，在CFiveChessDlg中添加了bool弄成员变量m_bMouse来记录鼠标是否被按下，mx,my记录按下的位置。6.4 人类玩家的Think操作玩家通过Think操作得出下子位置，人类下棋通过鼠标，当鼠标按下，CFiveChessDlg中的OnLButtonDown被执行，记录下鼠标是否按下bMouse，以及按下位置（mx,my）。所以该Think操作就是查看鼠标是否按下，如果按下则取得按下位置返回。如果没有按下就返回一个无效坐标（-1,-1），这样，因为返回的是无效下子位置，所以不会改变当前玩家，仍然是由该玩家下子。一直在正确位置按下了鼠标为止，然后清除掉bMouse标志（表示我已经下过棋子了，需要重新接收鼠标按下）。第7章 计算机智能设计机器智能设计需要解决的关键问题是估值和搜索技术。7.1 棋局估值人们在下棋过程中，走哪一步棋好，哪一步棋坏，有一定的评判标准，这个评判标准就是估值。计算机估值也就是对这种好坏的一个量化，最简单的是静态估值，它仅从当前棋局来考虑，五子棋的静态估值最简单直观的便是根据相连的棋子数来评价棋局好坏。所以仅需要扫描棋局中二子相连，三子相连，四子相连，五子相连的数量，下面是constant.h中定义的各种情况的分数。const int MAX_VALUE=99999;const int HTWO=20;/冲2分数const int TWO=40;/活2分数const int HTHREE=100;/冲3分数const int THREE=300;/活3分数const int HFOUR=1000;/冲4分数const int FOUR=2000;/活4分数MAX_VALUE是最大值表示会赢的局面分数，冲表示一端处于边界或者被对方棋子所堵的情况，活表示两端都有空位，如果两端都没有空位，则不可能形成五子相连，没有意义，不计分数。另外，每个位置也给予不同的分数，如下面数组所示：const int CEvaluation:m_nPosValue1515=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,2,2,2,2,2,2,2,2,2,2,2,1,0,0,1,2,3,3,3,3,3,3,3,3,3,2,1,0,0,1,2,3,4,4,4,4,4,4,4,3,2,1,0,0,1,2,3,4,5,5,5,5,5,4,3,2,1,0,0,1,2,3,4,5,6,6,6,5,4,3,2,1,0,0,1,2,3,4,5,6,7,6,5,4,3,2,1,0,0,1,2,3,4,5,6,6,6,5,4,3,2,1,0,0,1,2,3,4,5,5,5,5,5,4,3,2,1,0,0,1,2,3,4,4,4,4,4,4,4,3,2,1,0,0,1,2,3,3,3,3,3,3,3,3,3,2,1,0,0,1,2,2,2,2,2,2,2,2,2,2,2,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0;为方便以后扩展，估值单独用一个类(CEvaluation)来实现，其下有一个公共的虚函数value()用来给指定的棋局估值。其定义如下：int value(int board15,int side);board传入棋局状态，value给出估值，所得值是相对于黑方来说的，黑方局势越好，估值越大，反之，白方就要尽可能让这个值越小。计算值的过程实际上就是统计连续相同二子，三子，四子，五子的过程，依次按左下方，下方，右下方，右方扫描棋盘上每个棋子连续相连数目，然后计算分数，最后加上每个棋子所在位置的分数。可以看出，上面的效率并不高，实际上，父棋局的值估计好后，其子棋局与父棋局仅多一个棋子，所以其它棋子不需要再重复计算，只需要计算由于这一棋子所带来的分数变化即可。故有一个重载版的估值函数：int value(int board15,int side,int pvalue,int y,int x);其中pvalue是父棋局的估值，(x,y)指出了下子的位置7.2 极大极小值算法有了估值算法，我们可以简单地试着产生一个最大估值的走法，如下图所示：12n图7.2.1 深度为1的对弈树根结点表示当前棋盘局势，此时该电脑下子，它试着产生每一种可能走法，对于五子棋，最多15*15种，每一种走法都用估值引擎估值，如果此时电脑执黑子，它会选择估值最大的一种走法（估值引擎中棋局的值是黑方的价值减去白方的价值），因为这种走法对自己最有利，如果执白子，则选择估值最小的走法。其算法表示如下：POINT Search(int board15,int side,CEvaluation *pe) POINT pos,best; if(side=BLACK) best=-MAX_VALUE; else best=MAX_VALUE; for(int y=0;y15;y+)for(int x=0;xvalue(board,side=BLACK?WHITE:BLACK);boardyx=NONE; if(valuebest) best=value; pos.x=;pos.y=y; return pos;有了这个算法，计算机勉强有点智能，可以下一下棋了，但它还是比较笨，只管眼前这一步，而不能看到两步，三步，或者以后更多步的结果。要让计算机足够聪明，必须采用某种搜索算法。与估值引擎一样，为了以后方便扩展，单独设计了一个CSearch的纯虚类来作为公共接口。class CSearchpublic:virtual POINT Search(int board15,int side,int depth,CEvaluation *pE)=0;/ ;在上面深度为1的算法中，我们看到，每一个结点产生子结点，要在这子结点中选择一个对自己最有利的子结点，所以，对于黑方来说，总是选择子结点值为最大的结点来走，而不会选择其它结点，所以，该最大值的子结点值就是该结点的值。白方也一样，如下图所示：n1n2nknn11n1mn1k图7.2.2 深度为3的对弈树根结点n为当前棋局状态，它产生了子结点n1nk，并且要在子结点中选择一个对自己最有利的一个节点来下子，如果此时n节点该黑方走，就会选择其中最大值的节点。但是此时n1nk的节点值此时还不知，比如说n1的值必须要通过计算n1的子结点n11n1k，一直到达叶子结点为止，n结点为黑方，则n1为白方，它会选择所有子结点值为最小的作为自己的结点值，n2,n3,nk结点的值计算也一样，最后，n2,n3,nk当中最大的一个结点就作为n的结点值，也就是需要确定的走法。程序中极大极小搜索引擎的类为CMaxMinSearch，它继承至CSearch，按指定的深度，搜索产生一个走法：其搜索引擎伪码表示如下：int generate(board,int side,int depth) int best; 游戏结束返回估值 深度为0估值返回 Best=极大极小值 for(each possible pos) boardyx=side; int value=generate(board,anotherside,depth-1); boardyx=NONE; if(side=BLACK) best=max(value,best); else best=min(value,best); return best;CmaxMinSearch类在其公共接口中调用这个函数，选择最佳的一个走法，其Search函数如下：POINT CMaxMinSearch:Search(int board15,int side,int depth,CEvaluation *pe);它调用generate函数计算得出子节点的值，然后选择一个最佳子节点的坐标返回，作为下子的位置。7.3 Alpha-beta算法极大极小值算法的效率不高，如下图（8-1）所示:n1n2nknn21n2mn2kn为极大值节点（黑方）n1到nk为极小值节点（白方）n1=50n11=43图7.3.1 Alpha截枝n节点此代表黑方该下子的节点，它要在它的子节点中找一个值最大的子节点max(n1,n2,nk)作为自己的值（或下子），此时它得到其子节点n1的值为50，然后计算n2节点的值，此时n2为白方下子的节点，它要搜索一个值最小的子节点作为自己的值，这时它搜索计算得出其子节点n21的值为43，此时，我们就可以得出结论，因为n2要取最小子节点值作为自己的值，所以n2的值不会大于43，所以n2更不会大于前面的兄弟节点n1，所以n2一定不会被n选作为最佳子节点，故，在搜索n2的子结点n21n2k的过程中，只要n2有子节点的值小于50，则n2就不必再搜索了，后面n3，n4nk也一样，只要它们的某子结点值小于前面兄弟结点的最大值，则不必须再搜索了。我们将取极大值节点（上图中n）所产生子节点的最大值用变量alpha表示，如果子节点（极小值节点）在搜索过程中，产生的孙子节点值小于alpha，则子节点不需要搜索了，这叫做alpha截枝。图7.3.2n1n2nknn21n2mn2kn为极大值节点（黑方）n1到nk为极小值节点（白方）n1=50nxnx1nxknxmnx极小值节点（白方）极大值节点再推广到搜索深度很深的情况，如上图（图8-2）所示，取极大的值节点n的不知道哪一代孙子节点nx，它的祖先为n2m，n2，n，它为取极小值节点，假设它的某子节点的值小于n1=50，假如是nx1=40，那么nx是否应该放弃其子节点的搜索而截枝呢？我们可以这样推论：n的子节点现在搜索得到的最大值是50，alpha=50,对于n的子节点n2nk，它们在搜索过程中，所产生的不被截枝的任一子节点必须大于50（否则必被截枝），故n2m未被截枝大于50,n2m是取极大值的节点，所以其子节点中必有大于50的节点，故可得到在n2m这一层所得到的最大节点值alpha50，由此可以再推而广之，n2m的子孙中，凡是取极大值的节点，它们的子孙节点的最大值都应该50，到了nx这一层，nx是取极小值的节点，它的父亲是取极大值的节点，所以alpha也应该50，故nx1=40应该被截枝。n1n2nknn21n2mn2kn为极小值节点（白方）n1到nk为极大值节点（黑方）n1=20n11=33图7.3.3 Beta 截枝再来看另一方的情况，如上图（图8-3）情况与图8-1相反，n为取极小值节点，它的某子节点的值为20(n1)，搜索其后继子节点，如图中的n2，n2的子节点中某子节点n21的值为33，而n2取极大值，n2的值至少为33，故n2的父节点不可能选择n2，所以n2中一旦搜索发现其子节点值大于兄弟节点中的最小值，就没有搜索必要了。我们将取极小值节点的子节点中最小值用变量beta表示，某子节点在搜索孙子节点的过程中，如果孙子节点的值大于beta，则该子节点不需要再进行搜索，这叫beta截枝。再推而广之，任何一层取最小值的节点，它的子节点值大于beta，则应该截枝。综合两种情况，由此而得到alpha-beta算法，下面用伪码表示:int generate(board,int side,int depth,int alpha,int beta)游戏结束估值返回;到叶子节点估值返回;if(side=BLACK)/此节点该黑方，取极大值for(Each Possible Move)if(alpha=beta) return alpha;boardyx=side;int value=alphbeta(board,anotherside,depth-1,alpha,beta);boardyx=NONE;if(valuealpha)alpha=value;/子节点的最大值记录到alpha中return alpha;/返回最大值elsefor(each possible move)if(alpha=beta)return beta;boardyx=side;int value=generate(board,anotherside,depth-1,alpha,beta);boardyx=NONE;if(valuebeta)beta=value;/最小子节点的最return beta;其外层调用函数search代码如下，不同的是search返回坐标值：POINT CAlphaBeta:Search(int board15,int side,int depth,CEvaluation *pE)POINT pos=-1,-1;int alpha=-MAX_VALUE,beta=MAX_VALUE;if(side=BLACK)for(int i=0;ialpha)alpha=value;pos.x=x;pos.y=y;elsefor(int i=0;i15*15;i+)int y=i/15;int x=i%15;if(boardyx)continue;int cboard1515;memcpy(cboard,board,sizeof(cboard);cboardyx=WHITE;int value=generate(cboard,BLACK,depth-1,pE,alpha,beta);if(valuealpha)value=generate(cboard,WHITE,depth-1,pe,value,beta);将白方处的代码：int value=generate(board,BLACK,depth-1,pe,alpha,beta);改为：int value=generate(cboard,BLACK,depth-1,pe,beta-1,beta);if(valuealpha)value=generate(cboard,WHITE,depth-1,pe,alpha,value);7.6 预估排序和历史启发下面再来讨论第二种优化思路，一开始就搜索较好的节点，从而引发更高效的剪枝。这可以采用子节点预估值排序和历史启发两种方式实现一、 预估排序对于五子棋，最粗略的好一判断标准就是看棋盘上同一方的棋子连续相连的个数，在大多数情况也确实是这样，我们的估值函数就是这样编写的，所以，对于要搜索的子节点，可以对这些子节点先进行粗略的估值，将这些子节点按他们的估值进行排序，然后，按排序后的节点顺序进行搜索。程序中用CSortedAlphaBeta类实现了排序的AlphaBeta算法，定义了结构：struct CPointScorePOINT pos;int value;bool operator (const CPointScore &b)return valueb.value;该结构保存子节点某一走法（记录在pos中）的粗略估值，用stl:vector psArray保存所有子节点及其估值，用STL模板库中的sort函数进行排序，该排序算法需要向量中的元素有重载的“”操作函数，用来比较排序。所以在结构中重载了“”操作符函数。预估值排序的Alpha-Beta算法实现在CSortedAlphaBeta类中。也可以将预估值排序与PVS算法相结合，与预估排序的Alpha-Beta算法大致相同。预估值排序的PVS实现在CSortedPVS类中。二、历史启发历史启发简单地说就是根据部分已经搜索的结果来调整将要搜索的节点顺序。所要解决的问题又有两个，一是如何保存已经搜索过的历史记录，二是如果快速取得这些保存的记录。1、hash表由于五子棋的子节点很多（每层最多15*15个），不可能保存所有的搜索节点，故只能保存部分节点，当节点很多时，当前搜索的节点是否被搜索过，如何快速地取得该节点，这个时间最好是常量。显而易见，哈稀表很适合完成这项工作。在实现中，用结构HashItem来保存棋局信息，定义如下：struct HashItemunsigned long long check_sum;/64位hash校验值int value;/棋局的历史搜索得分int depth;/得到得分的搜索深度;check_sum为校验值，用来标识不同的棋局状态，我们知道每一棋局用二维数组int board1515表示，check_sum就是用这一个二维数组计算出来的值。具体原理篇幅所限，不再赘述，请参见hash表的相关文章。value就是棋局的得分，depth用来表示搜索得到该得分时的深度，因为在历史搜索时，某些节点的值可能是比较靠近叶子节点时得到的。这里的设计思想是，如何历史得分的深度比当前高，证明历史得分比当前所期望的精度还要高（深度越深精度越高），可以直接采用历史得分，否则，只能像预估值一样，作为搜索时的一个参考（参与排序）。Hash类的实现在CBoardHash类中，该类定义如下：class CBoardHashint nSize;/hash表大小HashItem *buf;/hash表_int64 check6431515;/64位校验生成随机数unsigned long hash3231515;/32位hash值生成随机数public:CBoardHash(int size);CBoardHash(void);unsigned long hashCode(int board15);/根据棋盘生成32位hash值unsigned long hashCode(unsigned long parHash,int side,int y,int x);_int64 checkSum(int board15);_int64 checkSum(unsigned long long parCheck,int side,int y,int x);HashItem getHashItem(unsigned long key);void setHashItem(unsigned long key,HashItem &it);这里介绍它们的公共接口，hashCode和checkSum有两个重载版本，一个接受棋盘数组，根据棋局信息生成hash码和校验值，hash码用来在hash表中定位，校验值用来检查根据hash码定位于表中的信息是否就是当前的棋局信息（通过当前棋局调用checkSum函数与表项中的check_sum比较）。为让ha