《毕业设计（论文）-计算机五子棋游戏对弈系统设计.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）-计算机五子棋游戏对弈系统设计.doc（54页珍藏版）》请在三一文库上搜索。
1、目 录1 绪论11.1 选题背景11.2 计算机博弈介绍11.3 五子棋基本知识介绍31.4 开发及运行环境31.4.1 开发环境31.4.2 运行环境31.5 本文结构32 系统总体设计52.1 系统架构52.2 系统功能划分52.3 系统总体逻辑流程52.4 关键技术点52.4.1 AI算法62.4.2 界面生成62.4.3 网络连接62.4.4 系统交互性63 人机对弈中AI的实现73.1 数据结构73.2 走法产生73.3 搜索算法及增强83.3.1 传统Alpha-Beta算法介绍83.3.2 NegaScout算法及Minimal Window103.3.3 置换表（Transpo
2、sition Table）113.3.4 历史启发（History Heuristic）123.4 估值函数154 界面的设计与实现174.1 设计思想174.2 主要类及其关系174.2.1 用户界面设计的6个核心类174.2.2 消息消息传递图184.3 主体界面195 联机功能的实现235.1 消息机制的架构235.2 各种消息说明236 总结和展望286.1 总结286.2 未来展望28参考文献29翻译部分31英文原文31中文译文41致谢49 中国矿业大学2008届本科生毕业设计（论文） 第52页1 绪论1.1 选题背景人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学。它与生物工
3、程、空间技术一起被并列为二十一世纪三大尖端技术。它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作。目前，各发达国家都把人工智能任务重点列入本国的高科技发展计划当中，投入巨大的人力和物力。作为一门边缘学科，它有诸多的研究领域：专家系统、决策支持系统、机器学习、机器视觉、自然语言理解等等，计算机博弈也是其中之一，博弈就是对策，这是自然界中的普遍现象，它不仅存在于游戏、下棋之中，而且存在于政治、经济、军事和生物竞争中，博弈的参加者可以是个人、集体、一类生物和机器，他们都力图用自己的智力去击败对手。作为人工智能研究的一个重要分支，计算机博弈是检验人工智能发展水平的一个重要方面。它的
4、研究为人工智能带来了很多重要的方法和理论，产生了广泛的社会影响和学术影响14。本文以计算机五子棋博弈系统作为研究课题。主要是考虑到当前网络上流传的五子棋游戏功能并不尽善尽美，其中最主要的问题就是人机对战和网络对战没有结合在一起实现；同时还存在游戏界面简单、计算机智能水平不足、也没有诸如保存棋谱和背景音乐等极有用的附加功能，所以不能吸引玩家兴趣。现在每一款成功的商业软件都越来越向功能多元化和界面简单友好化方向发展，所以我决定开发一个能够进行人机、网络对战，同时又具备许多附加功能的五子棋系统。1.2 计算机博弈介绍计算机五子棋对弈是一种完备信息博弈15（Games of Perfect Infor
5、mation），意思是指参与双方在任何时候都完全清楚每一个棋子是否存在，位于何处。只要看看棋盘，就一清二楚。象棋、围棋等都属于完全知识博弈。要想实现人和计算机双方对弈，不妨假设人是甲方，计算机是乙方，人和计算机对弈的过程可以如下表达：假设首先由甲方走棋，他面对的是一个开始局面1，从这个局面可以有M种走法分别形成了局面2，3，M+1。如图1.1所示。假设甲选择了形成局面2的走法，轮到乙下棋。乙面对局面2，又可以有N种可能的走法，形成N种新的局面K+1,K+2,K+N，如图1.2所示。 甲：123M+1图1.1甲方面对的局势乙：23.2 Alpha-Beta剪枝实例图乙：1K+1K+2K+N图1.
6、2 乙方面对的局势如果甲选择形成局面3，4，N+1走法，乙方都对应有若干种走法。这样甲乙双方轮流下棋，棋盘局面发展变化就形成如图1.3所示的一棵树状，通常称为博弈树。 甲：1乙：2乙：3甲：4乙：8乙：9甲：5乙：10乙：11甲：6甲：7乙：12乙：13乙：14乙：15图1.3 博弈树的例子图1.3 博弈树的例子博弈树最终的叶结点有甲赢乙输，甲输乙赢，甲乙平手三种。下棋者总是从当前局面出发选择最有利于自己的走法下一子，如甲在局面1，他将从乙2、乙3等局面中选择最有利于自己的走法；同样，乙在局面2时也从甲4、甲5等局面中选择最有利自己的走法。为了从很多的局面中选出最有利的，就需要一个搜索算法和一
7、个对局面形势进行判断的函数。搜索算法通常使用极大极小算法、Alpha-Beta剪枝技术，对形势的好坏，用估值函数进行判断，这些将在论文中介绍。1.3 五子棋基本知识介绍五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“連珠”，英译为“Renju”，英文称之为“Gobang”或“FIR”（Five in a Row的缩写），亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”，又有古典哲学的高深学问“阴阳易理”；它既有简单易学的特性，为人民群众所喜
8、闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。它是中西文化的交流点，是古今哲理的结晶。现在世界上有许多五子棋的变种，在某种程度上，它们都是对棋手的限制，主要是抑制黑方先行者的优势。在本文中，并没有涉及职业五子棋中对于黑方的禁手限制，而是讨论通常的自由式的五子棋对弈。本论文中五子棋基本规则如下：（1）棋盘：采用国际上标准的15*15路线的正方形棋盘。（2）下法：两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的交叉点（又称为空点）走子，规定执黑者先行。（3）胜负判断：网络对弈时黑、白某方在横、竖或斜方向上出现五子连
9、珠时判该方胜。人机对弈时由于估值函数的特殊性，计算机只要发现某方局面估值的绝对值大于8000即判该方胜（如活三、冲四等棋型出现时，系统可能就提示游戏结束了）。1.4 开发及运行环境1.4.1 开发环境l Intel Core T2300 1.66GHz，1GB内存，60G硬盘l Microsoft Windows XP Homel Microsoft Visual Studio 2008l Visual Assist X 10.4.1640.01.4.2 运行环境l Intel Pentium 2及以上处理器，128M以上内存l Microsoft Windows 2000及以上操作系统l 8
10、00*600或以上的屏幕分辨率1.5 本文结构本论文一共分为六大章，具体结构如下：第一章介绍了选题背景、计算机博弈和五子棋基本知识、开发运行环境及文章结构。第二章简略地叙述系统的总体设计。第三章重点讲述人机对弈中的AI，包括数据结构表示、走法产生、搜索算法以及估值核心。第四章阐述UI界面设计。主要包括界面设计思想和核心界面盘点。第五章讨论联机功能的实现，核心技术在于五子棋消息系统。第六章则是全文总结及展望。2 系统总体设计2.1 系统架构智能五子棋是使用Visual Studio 2008开发的基于对话框的MFC程序。本程序由37个类、6个结构体、12个全局函数以及若干其它变量、枚举类型、宏等
11、组成。其中核心类11个，包括用于实现单机AI算法的4个类：CEvaluation（估值核心）、CHistoryHeuristic（历史启发增强）、CTranspositionTable（置换表增强）和CNegaScout_TT_HH（核心的NegaScout算法类）；用于实现网络通信的CFiveSocket类和用于用户界面交互的6个类：CChessBoard（棋盘类）、CFiveDlg（主对话框类）、CMusic类（音乐类）、CTabChatDlg（聊天页面类）、CTabHCGameDlg（单机游戏页面类）和CTabMusicDlg（迷你音乐播放器页面类）。2.2 系统功能划分系统主体分为三大
12、功能模块：界面模块、网络连接模块及单机AI算法模块。逻辑上，网络连接模块与单机AI算法模块相互独立，而界面模块则时时负责与这两大模块交互，接受用户所有的消息以及对界面进行相应输出和更新。2.3 系统总体逻辑流程系统启动运行用户选择游戏模式单机版网络版看棋谱播放音乐保存棋谱两人聊天保存棋谱播放音乐游戏结束游戏结束图2.1 系统流程图2.4 关键技术点通过对系统功能的分析和设计，在实现过程中需要解决如下几个关键技术点：2.4.1 AI算法包括估值核心和搜索算法。其中搜索算法涉及技术有：Alpha-Beta剪枝、NegaScout算法、历史启发（History Heuristic）、置换表（Tran
13、sposition Talbe）和Zobrist哈希方法等。2.4.2 界面生成涉及MFC控件14种（Button、Check Box、ComboBox、Edit Control、Group Box、Radio Button、Static Text、Picture Control、Slider Control、Spin Control、Progress Control、Hot Key、Tree Control、Tab Control）；系统托盘（用户可控制其显示和隐藏）22；拖放功能（Drag and Drop）20；老板键功能（用户可自行设定）；输赢平和下子声音提示、聊天声音发送及整点报时；
14、自动窗口闪烁；读写注册表；简单多线程搜索音乐等等。2.4.3 网络连接使用的WinSock版本号为2.2。程序中使用CFiveSocket类负责收发网络消息。该类派生自MFC的CAsyncSocket类。网络通信基于客户机/服务器（Client/Server）模式，但它的工作方式却更类似于P2P16。因为客户端在与服务器断开后，自己也可以选择做服务器，而原来的服务端也可以迅速转换角色，反过来做客户端。所以，在逻辑上可以说这种工作方式是类似于P2P的。因为通信双方既可以做服务端也可以做客户端。2.4.4 系统交互性如摘要中提到的，本程序非常注重界面的友好性和操作的简单性。如老板键功能，可以使程序
15、“招之即来，挥之即去”。棋盘右键快捷菜单可以使用户迅速地对相应功能进行设置。棋谱的“静默保存”模式，省去了用户在每局棋结束之后，必须：点击保存按钮-设定文件名-点击“确定”按钮，这一系列烦琐工作，程序在后台静静地为用户处理好了一切。系统特别重视出错处理，能够对“形形色色”的错误作出对应的提示，避免在错误发生以后，用户不知所措，其中绝大多数错误以ToolTip的形式呈现给用户。3 人机对弈中AI的实现3.1 数据结构单机AI算法中用到的核心数据结构总结为如下几个：（1）程序包括一个记录棋盘数据二维数组BYTE m_FiveBoard1515和一个走步记录栈std:vector m_vecStep
16、List。m_FiveBoard数组中存储当前棋盘格子落子颜色，而m_vecStepList存储走步STONEPOS值，它主要用于支持悔棋功能。STONEPOS结构体定义如下：typedef struct _tagStonePosition BYTE x, y; / x, y是棋盘坐标值，取值范围0,14 STONEPOS;（2）用数字“0”和“1”来表示不同颜色的棋子，其中黑色棋子用“0”表示，白色棋子用“1”表示。没有棋子的格子用0xFF表示。这三个数值都有相应的宏，以避免出差错：#define BLACK 0#define WHITE 1#define NOSTONE 0xFF（3）搜索
17、算法还用到了一个重要的走法结构体STONEMOVEtypedef struct _tagStoneMove STONEPOS stonePos; / 棋子位置int score; / 走法得分 STONEMOVE;3.2 走法产生相对于象棋等游戏来说，五子棋的走法产生规则是十分简单的：棋盘上所有空白的位置都是合法的落子点（本论文并没有讨论禁手规则，详见第一章1.3节规则说明）。搜索类CNegaScout_TT_HH的CreatePossibleMove函数用来完成走法产生4。/ 用以产生局面position中所有可能的走法/ position是包含所有棋子位置信息的二维数组/ nPly指明当前
18、搜索的层数，每层将走法存在不同的位置，以免覆盖/ nSide指明产生哪一方的走法，WHITE为白方，BLACK为黑方int CreatePossibleMove( BYTE position1515, int nPly, int nSide )inti, j;m_nMoveCount = 0;for( i = 0; i GRID_NUM; +i )for( j = 0; j GRID_NUM; +j )if( positionij = NOSTONE )m_MoveListnPlym_nMoveCount.stonePos.x = j;m_MoveListnPlym_nMoveCount.st
19、onePos.y = i;/ 使用位置价值表评估当前走法的价值m_MoveListnPly+m_nMoveCount.score = g_arrPosValueij;/ 为了提高剪枝效率,对走法队列进行(从大到小的)排序MergeSort_Desc( m_MoveListnPly, m_nMoveCount );return m_nMoveCount; / 返回合法走法的个数3.3 搜索算法及增强3.3.1 传统Alpha-Beta算法介绍在极大极小树搜索的过程中，实际相当一部分结点的搜索并不会影响最终搜索树的值，Bruno在1963年首先提出了Alpha-Beta算法，1975年Knuth和
20、Moore给出了Alpha-Beta的数学正确性证明。Alpha-Beta算法通过下界（Alpha）上界（Beta）对搜索树值的最终范围进行了划定，当某些子树其值被证明会在上述界限之外，无法影响整颗树的值时，便可进行剪枝5。Alpha-Beta剪枝算法的效率与子结点扩展的先后顺序相关，在最理想情况下，其生成的结点数目为：ND=2BD/2-1（D为偶数）ND=2B（D+1）/2+B(D-1)/2-1 (D为奇数)其中，B为Branch Factor，D为深度由于不使用Alpha-Beta剪枝算法时，ND=BD，所以最理想情况下Alpha-Beta算法搜索深度为D的结点数仅相当于不使用Alpha-
21、Beta时搜索深度为D/2的结点数。但在最坏的情况下，Alpha-Beta算法产生的结点数与极大极小算法完全一样9！下图3.1是以NegaMax形式（每层之间更改Alpha,Beta值符号，使Alpha剪枝在代码中也简化成Beta剪枝的形式表现出来）表现的Alpha-Beta算法伪代码7：int AlphaBeta( 局面p; int , int ) / 计算局面p的的极大极小值int a, t, i;生成局面p的后继局面p1, p2, ., pw;if( w = 0 ) return ( Evalutate(p) ); / 叶结点返回估值a = ;for( i = 1; i = ) retu
22、rn ( a ); / (Beta)剪枝return ( a );图3.1 NegaMax形式的Alpha-Beta类C伪代码下图3.2为Alpha-Beta剪枝实例图：6674 极小值结点A (-, )(-, -6)BC-5-3-7-1-4-2-6-6-4FGEDL(-, )(-,)(-, -6)(-, -6)(-, 6)Beta 剪枝(6, )Alpha 剪枝(-, -6)(-, -6)(-, -6) 极大值结点图3.2 Alpha-Beta剪枝实例图在上图中，最左边的分枝先以初始窗口（-,）进行搜索。完成对D的左子结点估值后，D的估值至少为6，故以窗口（-,-6）对D中间子结点进行搜索。
23、在节点E，Alpha已经被更新为-6了（因为对结点B的左子结点D的遍历已经完成）。因此B的右子结点E的搜索窗口为（-,6）。在对E的左子结点完成遍历后，Alpha值被调整为新值7（beta），因此可以对E的右子结点L进行（Beta）剪枝。我们也可以将这个过程从负极大值观点上看成是确定min(6,max(7 ,L)或者是max(-6,-max(7,L)的值。不管L的值是多少，我们获得的值总是6，或者用负极大值形式来说-6。同理，可以分析出对C的右子树进行类似的Alpha剪枝。3.3.2 NegaScout算法及Minimal WindowMinimal Window：是指窗口为0的Alpha、B
24、eta限制范围，譬如N,N+1，因为不可能存在一个整数既大于N又小于N+1，所以这个范围内不可能存在真实结果。同时因Minimal Window的Alpha、Beta限制范围最小，所以产生剪枝的概率也比正常的搜索窗口的大10。采用Minimal Window的意义：如果搜索一个子结点的时候，当其值大于Beta，即产生Beta剪枝的概率比较大的时候，我们可以先用Beta-1,Beta进行搜索，如果搜索的结果Fail High，即说明了结果=Beta，这时我们可以立刻进行Beta剪枝，相反如果结点Fail Low，则说明结果不可能大于Beta，也就是说无法剪枝，那么我们刚才用Beta-1,Beta
25、的MinimalWindow就无法得到真实结果，所以我们必须重新用Alpha,Beta进行搜索。虽然当无法Beta Cutoff需要重新搜索的时候，实际比原来多出了Minimal Window Beta-1,Beta的搜索过程，但是由于Minimal Window内的子树产生剪枝的概率比较大，所以实际增加的搜索结点数相对比较少，同时当Move Ordering比较好的时候，大部分结点能够产生Beta剪枝的概率相当大，这样我们就可以避免更繁重的全Alpha-Beta窗口搜索。在采用Minimal Window的NegaScout算法中，每次递归扩展的时候，第一个节点用正常的Alpha-Beta窗
26、口扩展，而后面的都用Minimal Window进行扩展，这样的话如果说最优的孩子结点最先扩展，则此后的其他孩子结点通过Alpha值对应的Minimal Window进行搜索都可以轻松剪枝，并且由于采用了Minimal Window，Alpha-Beta窗口缩到最小，剪枝也更容易，搜索节点也更少，反之，如果发现该扩展结点使用Minimal Window不产生剪枝（即值小于Beta），且值仍大于Alpha，我们才用正常的Alpha-Beta窗口进行再搜索(re-search)。NegaScout算法伪代码如下图3.37：int NegaScout( 局面p; int , int ) / 计算局面
27、p的的极大极小值int a, b, t, i;生成局面p的后继局面p1, p2, ., pw;if( w = 0 ) return ( Evalutate(p) ); / 叶结点返回估值a = ;b = ;for( i = 1; i 1& t 1&d = ) return ( a ); / (Beta)剪枝 b = a + 1; / 设置新的空窗return ( a );图3.3 NegaScout剪枝实例图（加粗部分是与图3.1不同之处）本系统在实现时是就是使用NegaScout算法，并辅之以置换表(Transposition Table)和历史启发（History Heuristic）进行
28、增强。在后面的章节中将给出部分源代码。3.3.3 置换表（Transposition Table）在一棵搜索树中，不少结点之间虽然是经过不同的路径到达的，但其状态是完全一致的。通过建立Transposition Table保存已搜索结点的信息，那么再次遇到相同状态的结点时便可以套用之前的搜索结果。在Transposition Table中，记录的信息为最优着法、得分、深度等。为了快速检测当前结点是否已经搜索过，我们一般对当前状态进行编码，然后利用Hash表的方式进行查找，这里采用的编码方式是Zobrist Hash方法13。Zobrist Hash方法：在程序启动或棋局开始的时候，建立一个多维
29、数组（在五子棋中是三维）ZpieceTypeboardWidthboardHeight，其中pieceType是棋子种类，五子棋中为黑、白两种；boardWidth为棋盘宽度，五子棋为15；boardHeight为棋盘高度，五子棋为15。然后，将此数组中填满随机数。若要求某一局面的哈希值，则将棋盘上所有棋子在数组Z中对应的随机数相加，即可得到。对于搜索过程中的每一个结点，Zobrist方法用增量式计算方法，无须每次都加总所有棋子。在程序根部，作一次加总操作求出根节点的哈希值，当搜索一个新结点时只要将该位置对应的随机数和根结点哈希值相加即可。当对这个局面搜索完成后，再将搜索过程加上的值减去，就恢
30、复了当前结点的哈希值。这是根据两次异或同一个数结果保持不变的原理，避免重新计算整个棋盘的Hash值，并且位的异或在计算机内部运算中速度极快。显然，增量式计算哈希值的方法在思想上同Alpha-Beta过程中的的MakeMove/UnMakeMove是一致的。Transposition Table是一种空间换取时间的思想。Transposition Table结合Alpha-Beta搜索：在Alpha-Beta搜索的过程中，一个结点会出现以下三种情况之一：（1）Fail High，结点值至少=Beta，但不知道其具体值。（2）Fail Low，结点值至多=Alpha，但不知道具体值。（3）Exac
31、t，Alpha=结点分值=Beta，此值为准确值。一般只有Exact类型，才可作为当前结点的准确值存入Transposition Talbe，但Fail High(=Alpha)所对应的边界值仍可帮助我们作进一步的剪枝，所以我们在Transposition Table用字段entry_type表示类型，其中Exact类型为准确值，其余的是表示值的范围12。在搜索过程中，首先检查Transposition Table中保存的结果能否直接代表当前结点的值或使当前结点产生Alpha、Beta剪枝，不能的话则继续进行该结点的搜索。Transposition Table的作用：（1）如果在Transpo
32、sition Table访问中能直接得到结果的话，则可以避免该结点以下子树的搜索，减少了搜索时间。（2）如果在Transposition Table中能查找到当前结点信息，并且存储深度比当前结点大，那么实际上是增加了当前子树的搜索深度，也即增加了结果的准确性。3.3.4 历史启发（History Heuristic）在介绍NegaScout算法中曾经提到，Alpha-Beta搜索的剪枝效率，几乎完全取决于节点的排列顺序（Move Ordering）。在节点排列顺序处于理想状态的情况下，Alpha-Beta搜索需要遍历的节点数仅为极大极小算法所需遍历的结点数的平方根的两倍左右。也就是说对一棵极大
33、极小树来说，如果极大极小搜索需遍历106个结点求得结果，那么处于理想状态的Alpha-Beta搜索仅需遍历约2000个结点就可求得结果。而在结点的排序最不理想的情况下，Alpha-Beta搜索要遍历的结点数同极大极小算法一样多。如何调整待展开的走法排列的顺序，是提高搜索效率的关键。根据部分已经搜索的结果来调整将要进行搜索的结点顺序是一个可行的方向。在基于Alpha-Beta的搜索中，一个好的走法可以定义如下4：（1）由其产生的结点引发了剪枝。（2）未引发剪枝，但是其兄弟走法中最值者。在搜索的过程中，每当找到一个好的走法，就将与该走法相对应的历史得分作一个增量，一个多次被搜索并确认为好的走法的历
34、史纪录就会较高，当搜索中间结点时，将走法根据其历史得分排列顺序，以获得较佳的排列顺序。本系统在实现时使用NegaScout算法并配合上面介绍过的置换表（Transposition Table）和历史启发（History Heuristic）增强，核心搜索算法源代码如下6-13：/ 主调例程必须将alpha设为COMP_LOSS,将beta设为COMP_WINint CNegaScout_TT_HH:NegaScout_MAX( int depth, int alpha, int beta ) / 用于偶数层(从算起)int count, i;int a, b, t;int score;if(
35、depth 0 )i = IsGameOver( CurPosition, depth );if( i != 0 )return i; / 已分出胜负,返回极值/ 查询置换表看是否有当前节点的有效数据score = LookUpHashTable( alpha, beta, depth, 0 ); if( score != 66666 ) return score; / 命中,直接返回查得数据if( depth Evaluate( CurPosition, 0 );/ 将估值存入置换表EnterHashTable( EXACT, score, depth, 0 );return score;c
36、ount = CreatePossibleMove( CurPosition, depth, 0 );if( depth = m_nMaxDepth ) / 在根节点设定进度条gbTabHCGame.m_ThinkProgress.SetRange( 0, count );gbTabHCGame.m_ThinkProgress.SetStep( 1 );for( i = 0; i count; +i ) / 取所有走法的历史得分m_MoveListdepthi.score = GetHistoryScore( &m_MoveListdepthi );/ 将走法的历史得分从大到小排序MergeS
37、ort_Desc( m_MoveListdepth, count );int bestmove = -1;a = alpha;b = beta;int eval_is_exact = 0;for( i = 0; i a & t 0 ) / FAIL-HIGH: a = -NegaScout_MIN( depth-1, -beta, -t ); /* 重新搜索 */eval_is_exact = 1; / 设数据类型为精确值if( depth = m_nMaxDepth ) / 保留最佳走法m_cmBestMove = m_MoveListdepthi;bestmove = i; / 记住最佳走
38、法的位置/ 恢复当前节点的哈希值Hash_UnMakeMove( &m_MoveListdepthi, CurPosition );/ 撤销子节点UnMakeMove( &m_MoveListdepthi ); if( a = beta ) / 将下边界存入置换表EnterHashTable( LOWER_BOUND, a, depth, 0 );/ 将当前走法汇入历史记录EnterHistoryScore( &m_MoveListdepthi, depth );return a; /* 剪枝 */b = a + 1; /* 设置新的空窗 */if( bestmove != -1 ) / 将最
39、佳走法汇入历史记录EnterHistoryScore( &m_MoveListdepthbestmove, depth );if( eval_is_exact ) / 将搜索结果放进置换表EnterHashTable( EXACT, a, depth, 0 );else EnterHashTable( UPPER_BOUND, a, depth, 0 );return a; / 返回最佳值3.4 估值函数在搜索之外，估值函数是最重要的部分，因为对实际局面的评价好坏，影响着今后局势发展的趋势。更高的目标结点估值函数值是搜索树所追求的目标，与研究对象变化规律越接近的估值函数，由越能反映未来局势的变
40、化。由于大部分研究对象不存在绝对准确体现最终结果的估值函数，所以使估值函数值尽量能刻画研究对象是估值函数的主要目标，这就需要大量的领域相关的知识。一般来说领域知识常以感性的形式存在，在计算机实现的过程中，则必须将其理性化，也就是说建立研究对象的数学模型。同时在实现这个数学模型的过程中，必须考虑运算的耗费，因为运算量太大的估值计算，往往影响了整个搜索的速度，降低了搜索的深度，而运算量少的一些近似估值，通过搜索深度的增加，仍能大大弥补近似估值所丢失的不准确性。在数学上，估值函数是对一个盘面定性的静态评价，其计算方法为：EvaluationScore = KiFi(P)，其中Ki为特征系数，Fi(P
41、)为特征函数，P为当前棋盘。也就是说估值函数分别对当前棋盘的若干个特征进行计算，获得其特征值，所有这些特征值及其特征系数乘积的累加，得出最后的评价函数值。智能五子棋估值函数先对棋盘上五、四、三、二等各种棋型进行分析。最基本的棋型优先顺序为：五连 活四 冲四 活三 眠三 活二 眠二。具体的过程如下：对棋盘上所有棋子在水平、垂直、左斜和右斜方向上进行分析。得出各个方向上各种棋型的数量，然后对分析结果进行统计，得到每种棋型的数量。如果已五连，直接返回极值（极值并不是真正数学意义上的无穷大/小，在本系统中绝对值大于8000的数值看成是极值，下同）。两个冲四看成一个活四。如果有活四的棋型，返回极值。如果轮到某一方落子，而此时某一方出现冲四棋型，返回极值。如果有冲四和活三的棋型，返回极值。如果轮到某一方落子，而此时某一方出现多于1个的活三棋型，返回极值。如果没有返回极值，则对所有眠三加10，所有活三加4，所有眠二加1。最后双方棋子价值都加上棋子位置价值表（如下表所示）。最后要指出的是，程序中用到的是负极大值形式的Alpha-Beta搜索算法，因此为了所搜索算法正确动作，估值函数对轮到谁下棋敏感。当轮到白棋走时，估值