（图为目前中国象棋界AI最牛B的巫师象棋）
摘要
计算机博弈是人工智能研究的一个重要分支，被专家门称为人工智能界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成果，这些成果在人工智能领域产生了重要影响。国际象棋计算机博弈研究已经有了五十多年的历史，IBM公司在1997年开发出了超级计算机“深蓝”战胜了当时世界国际象棋大师卡斯帕罗夫，标志其水平已达到国际象棋世界冠军水平。而中国象棋的历史更为悠久，虽然中国象棋计算机博弈研究起步晚于国际象棋，但起点高，国际象棋计算机博弈研究的成果为我们提供了很多的借鉴技术。近年来随着研究的不断深入，中国象棋计算机博弈越来越成为继国际象棋后计算机博弈研究的热点之一。
本文在对目前主流的计算机博弈技术进行全面的综述后，对构成计算机博弈系统的四个组成部分进行了优化和改进，特别是针对静态估值算法不能应对局势变化的固有缺点，提出了动态局势再评估算法。在此之上实现了一个中国象棋计算机博弈系统，论文主要研究了以下3方面的问题：
第一、对计算机博弈系统的四个组成部分及基础技术进行了研究，包括数据结构，着法生成，搜索算法，估值算法。
第二、研究了建立在Alpha-Beta搜索算法基础之上的各种优化技术。主要讨论了窗口探测，静寂搜索，历史启发，深层迭代，NullMove5个方面的优化方法，并根据实验结果结合置换表技术提出了具体的组合方案。
第三、论文针对目前广泛使用的静态估值算法不能应对局势变化的固有缺点，提出了动态局势再评估算法。通过引入“局势因子”，使得估值算法根据当前局面形势做出攻防策略。
关键词：人工智能；中国象棋；博弈算法；动态局势再评估；局势因子
Abstract
Computergameisanimportantbranchofartificialintelligenceresearch.Itisdescribedasafruitflyoftheartificialintelligencebyexperts.That’stosayhuman’sresearchtothecomputergamehasachievedmassiveresearchresults.Theseachievementshaveplayedanimportantinfluenceonamorewidespreaddomain.Througoverseasresearchers’explorationofchessgamblingsystemformorethan50years,IBMCorporationdevelopedsupercomputer”DarkBlue”in1997，andhasdefeatedworldchessmasterKsparov;whiletheChinesechesshistoryismoreglorious.TheresearchofChinesechesscomputergameislaterthantheresearchofchesscomputergame,butitbasedonthecomputergame’sresearchresults.Withthedeeperstudyofresearch,Chinesechesscomputergamebecomesoneofthemostactivepartsofcomputergameresearcharearecently.
AftersummarizingrelatedresearchesonChinesechesscomputergame.Somekeyproblemsarestudiedanddiscussedinthisdissertation.Basedonabovework，anintegratedChinesechesscomputergamesystemaredesignedanddeveloped.Thewholeworkmainlyfocusesonthefollowingthreeaspects:
1.IntroducethekeycomponentpartsofaChinesechesscomputergamesystemwhichinvolvedatestructure,generatelegalmoves,searchalgorithmsandevaluatealgorithms.
2.MakeastudyontheoptimizationofsearchalgorithmbasedontheAlpha-BetaalgorithmwhichincludedPrincipalVariationSearch,quiescencesearch,historyheuristic,interativedeepening,null-movepruningandsoon.
3.Thispaperprovidesanalgorithmcalled“dynamicsituationevaluatealgorithm”whichavoidsthedrawbackofstaticevaluate.Astheintroductionof“decisionfactor”,computercanmakedecisionsbysituation.
Keywords:artificialintelligence;Chinesechess;gamealgorithm;dynamicsituationevaluatealgorithm;decisionfactor
目录
第一章绪论...8
1.1选题背景和研究意义...8
1.2中国象棋计算机博弈的发展历程...9
1.3国内外研究现状...10
1.4本文的主要工作和论文结构...11
第二章背景知识...13
2.1数据结构...13
2.1.1棋盘表示...13
2.1.2置换表...14
2.2着法生成...15
2.3搜索算法...16
2.3.1博弈树的基本概念...16
2.3.2极大极小算法...17
2.3.3负极大值法...19
2.3.4Alpha-Beta搜索算法...20
2.4估值算法...22
2.5本章小结...23
第三章搜索算法的优化...24
3.1窗口探测...24
3.1.1渴望搜索...24
3.1.2极小窗口算法...25
3.2静寂搜索...26
3.3历史启发...26
3.4深层迭代...27
3.5NullMove.29
3.6内存优化...29
3.7本章小结...30
第四章动态局势再评估算法...31
4.1静态评估算法详述...31
4.1.1对子力和攻击性的评估...31
4.1.2对棋子位置附加值的评估...31
4.1.3对灵活性的评估...32
4.1.4对棋子的协调性和保护性的评估...32
4.1.5静态估值函数...33
4.2静态估值函数的缺陷...33
4.3局势因子及动态局势再评估函数...33
4.4动态局势再评估算法的步骤...36
4.5本章小结...36
第五章中国象棋计算机博弈系统——出棋制胜的设计与实现...38
5.1系统设计...38
5.1.1中国象棋通用引擎协议层(UCCI)38
5.1.2“出棋制胜”软件系统结构图...39
5.2详细设计...39
5.2.1棋盘棋子表示...39
5.2.2着法生成...40
5.2.3搜索算法...43
5.2.4评估算法...45
5.2.5置换表...45
5.4本章小结...47
第六章总结...48
致谢...49
参考文献...50
Contents
Chapter1Introduction.8
1.1ResearchTopics’BackgroundandSignificance.8
1.2ChineseChessComputerGame’sDevelopingProcess.9
1.3TheStatusQuoatHomeandAbroad..10
1.4TheMainWorkandStructureofthisthesis.11
Chapter2BackgroundKnowledge.13
2.1DateStructure.13
2.1.1ChessBoardExpression.13
2.1.2TransposingTable.14
2.2MovesGeneration.15
2.3SearchAlgorithms.16
2.3.1gametree’sconcept16
2.3.2MinimaxAlgorithm..17
2.3.3NegamaxAlgorithm..19
2.3.4Alpha-BetaAlgorithm..20
2.4EvaluateAlgorithm..22
2.5ChapterSummary.23
Chapter3TheOptimizationofSearchAlgorithm..24
3.1WindowDetection.24
3.1.1EagerSearch.24
3.1.2PrincipalVariationSearch.25
3.2QuiescenceSearch.26
3.3HistoryHeuristic.26
3.4InterativeDeepening.27
3.6MemoryOptimization.29
3.7ChapterSummary.30
Chaper4DynamicSituationEvaluateAlgorithm..31
4.1StaticEvaluateAlgorithm..31
4.1.1TheEvaluationofTheChessman’sValue.31
4.1.2TheEvaluationofTheChessman’sPosition.31
4.1.3TheEvaluationofTheChessman’sMovability.32
4.1.4TheEvaluationofTheChessman’sCompatibility.32
4.1.5StaticEvaluateMethod.33
4.2StaticEvaluateMethod’sDisadvantage.33
4.3DecisionFactorandDynamicSituationEvaluateAlgorithm..33
4.4TheStepsofDynamicSituationEvaluateAlgorithm..36
4.5ChapterSummary.36
Chaper5ChineseChessComputerGameSystem..38
5.1SystemDesign.38
5.1.1UniversalChineseChessProtocol(UCCI)38
5.1.2TheStructureofTheSystem..39
5.2DetailedDesign.39
5.2.1ChessBoardExpression.39
5.2.2MovesGeneration.40
5.2.3SearchAlgorithms.43
5.2.4EvaluateAlgorithm..45
5.2.5TransposingTable.45
5.3TheExperimentalResultsandDiscussRelatedIssues.46
5.4ChapterSummary.47
Chapter6Summary.48
Acknowledgement49
References.50
计算机博弈是人工智能研究的一个重要分支，被专家门称为人工智能界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成果，这些成果在人工智能领域产生了重要影响。国际象棋计算机博弈研究已经有了五十多年的历史，IBM公司在1997年开发出了超级计算机“深蓝”战胜了当时世界公认第一的国际象棋大师卡斯帕罗夫，标志其水平已超过国际象棋世界冠军。而中国象棋的历史更为悠久，早在2000多年前的战国时代就已经有了关于象棋的记载。中国象棋计算机博弈的难度绝不会低于国际象棋，表1.1是几种棋类游戏空间复杂度和树复杂度对比，其中中国象棋的空间复杂度是国际象棋的100倍，而树复杂度则达到了1027倍。
表1.1几种棋类空间复杂度和树复杂度对比
人工智能的先驱者们曾认真地表明:如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心;那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。因此对于中国象棋人机博弈问题的研究意义重大。
计算机中国象棋是在计算机国际象棋博弈的基础上发展起来的。
第一个棋弈程序写于电脑被真正发明之前，这是一个非常有趣的事实。它是由数学家阿伦·图灵(AlanTuring)所编写的，他知道可编程电脑即将出现，一旦发明出来，就有下棋的能力。图灵的伟大成就是领导专家小组破译了纳粹德国的“谜”密码，因此对第二次世界大战的决定性结束作出了贡献。战争结束不久，他就写下了能够让机器下棋的指令。由于当时还没有一台机器能够执行这些指令，于是他就自己执行（即图灵根据他所写的算法去运算，严格根据运算得出的结果去走棋），充当一个“人类CPU”，每走一步需要半个多小时。
50年代中期，这台机器下了三局棋。第一局是自己对自己，白胜。第二局是对一位让王后的强棋手，这局棋进行了10个小时，结果人类大师胜。第三局机器的对手是一位刚学棋一个星期的的年轻姑娘，结果程序23回合得胜。这是在智力博弈中人类首次负于电脑。
1958年，匹兹堡大学的三位科学家奈维尔、肖恩和西蒙(Newell,ShawandSimon)有重大发现：可以从搜索树中剔除相当大的部分而不影响最后结果，他们把这叫Alpha-Beta算法。很重要指出的是，这是一个纯数学领域的技巧，独立于任何国际象棋知识而生效。
1958年，IBM704成为第一台能同人下棋的计算机，名为“思考”思考速度每秒200步。60年代中期，科学家德里夫斯断言，计算机将无法击败一位年仅10岁的棋手。
1967年，MIT的Greenblatt等人在PDP-6机器上利用软件工具开发的MacHackVI程序，参加麻省国际象棋锦标赛，写下了计算机正式击败人类的记录。
从1970年起，ACM(AssociationforComputingMachinery)开始举办每年一度的全美计算机国际象棋大赛。从1974年起，三年一度的世界计算机国际象棋大赛开始举办。
1975年，电脑科学家肯·汤普森(KenThompson)觉得不能等待速度快5一25倍的百万美元级超级电脑来用于提高下棋能力。他和贝尔实验室的同事一起决定建造一台专门用途的机器，使用了价值大约20，000美元的几百个芯片。他们把这台机器叫做“尤物”(belle)，它只会下国际象棋。它能够每秒搜索大约18万个局面(而当时的超级电脑只能搜索5000个)。“尤物”在比赛中可以搜索八至九层那么深，因此可以和大师同场竞技。从1980年到1983年它赢得了世界电脑国际象棋和所有其它电脑竞赛冠军，直到被价钱贵上千倍的克雷X-MPs巨型机(CrayX-Mps)取代为止。
80年代中期，电脑科学家、卡梅隆大学的汉斯·贝利纳(HansBerliner)教授接手肯·汤普森放下的工作。贝利纳的几个学生包括华人许锋雄等自行研究叫“芯测”的机器，后来则是“深思”(DeepThought)。它只花5000美元但每秒搜索50万个局面。就在它诞生的同一年，就因在一次比赛中击败了一位大师而震惊了国际象棋界，成了第一台国际象棋大师级的计算机。许锋雄等后来加入了IBM，和其他人合作制造了IBM现在的“深蓝”(DeepBlue)。1997年深蓝在“回敬赛”中战胜棋王卡斯帕罗夫，标志者计算机国际象棋博弈达到了一个新的里程碑。
计算机中国象棋的研究历史较短，文献和报道均很少。台湾学者在七十年代末开始了计算机中国象棋的研究工作，并在八十年代初开发和出版了苹果机(6502)和IBMPC机(8088)象棋程序。1983年南开大学开发了残局程序，并在随后的几年里开发了全局程序。但由于中国象棋在计算机实现方面比国际象棋更加复杂，而且中国象棋博弈技术研究落后于国际象棋，所以中国象棋软件还远未达到世界冠军水平。但近年来通过许多中国象棋软件编程爱好者和多个象棋开发团队的努力，使中国象棋软件水平有了长足的进步，慢棋已达到业余大师水平，快棋可以和象棋大师对抗。当然要设计出打败人类的中国象棋软件，还需要象开发国际象棋软件那样有大量的商业金钱投入，比如要组建由中国象棋特级大师和最优秀象棋软件开发设计人员组成的开发团队，使用世界上最先进的超级计算机等。
图1.1知名象棋程序一览[1]
2006年8月，“浪潮杯”全国首届机器博弈锦标赛暨研讨会于北京举行，仅设有中国象棋的比赛。赛后，组织了5个软件对5位象棋大师的人机大战，最终软件方取得了胜利。其后，“棋天大圣”作为软件的冠军挑战中国棋王许银川，两战皆和。这次比赛拉开了国内机器博弈发展的序幕，从此，越来越多的学者开始投入到这个人工智能学科中非常重要的领域中。
本文的主要内容是在分析计算机博弈关键技术的基础上，将博弈搜索和动态局势再评估算法应用到中国象棋计算机博弈系统的设计与实现上。论文主要研究以下4部分的内容：
(1)数据结构，包括棋盘表示，置换表
(2)着法生成，产生所有合法着法
(3)搜索算法，基于Alpha-Beta搜索算法的优化
(4)估值算法，提出一种可行的动态局势再评估算法
本文后继章节安排如下：
第二章、对计算机博弈系统的四个组成部分及基础技术进行了研究，为后续章节及中国象棋计算机博弈程序设计打下基础。
第三章、研究了建立在Alpha-Beta搜索算法基础之上的各种优化方法。主要讨论了窗口探测，静寂搜索，历史启发，深层迭代，NullMove5个方面的优化方法，并根据实验结果结合置换表技术提出了具体的组合方案。
第四章、论文针对目前广泛使用的静态估值算法不能应对局势变化的固有缺点，提出了动态局势再评估算法。通过引入“局势因子”，使得估值算法根据当前局面形势做出攻防策略。
第五章、结合第三章提出的搜索方案和第四章的动态局势再评估算法，搭建中国象棋计算机博弈系统。并对搜索方案和动态局势再评估算法进行实验验证。
最后总结本文的研究工作和结果，并就本文的后续研究提出自己的思考、见解和展望。
本章主要介绍构建一个计算机博弈系统所需的基础知识和框架，为实现中国象棋博弈程序打下基础。
计算机象棋对弈是一种双人完备信息的博弈过程[2]，其核心思想并不复杂，实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合[3]。博弈程序的任务就是对博弈树进行搜索找出当前最优的一步走棋，而当前最优的判断由估值算法给出。
根据上述过程，一个完整的计算机象棋博弈系统包含一下四部分：
1，数据结构：由棋盘表示，置换表等组成；
2，着法生成器：产生指定局面下所有合法的着法；
3，搜索算法：对博弈树进行搜索，由着法生成器生成扩展节点；
4，估值算法：依据特定局面博弈双方的优劣形势给出的一个估值。
其中，搜索算法和估值算法是计算机博弈的核心，这四个部分相互配合运转起来，就可以实现计算机象棋博弈系统。
典型的中国象棋棋盘如图2.1，中国象棋的棋盘有9列10行，共90个点。
一般来说，棋盘既可以用9*10的二维数组表示，也可以用一维数组表示。现在我们来比较一下这两种表示方法:
(l)，二维数组，表示比较直观，譬如棋盘横坐标从左开始0到8，纵坐标从上到下为0到9的话，棋盘左上角的点就是Board[0][0]，整个棋盘坐标用Board[9][10]来定义，这样表示比较直观。
图2.1中国象棋棋盘数组表示[4]
(2)一维数组，举个例子，棋盘第一行0，1，2，3，4，5，6，7，8，第二行9，10，11，12，13，14，15，16，17，如此类推，用一维数组表示坐标。计算棋盘上某个点的横坐标纵坐标，只需作N%9和N/9计算便可。
比较两种方式，由于在搜索、评价时，访问用一维数组的方式访问棋盘比用二维数组的方式快(少了一次地址偏移操作)，采用的一维数组有速度上的优势。
引入位棋盘可以进一步提高着法生成和盘面估值的效率。国际象棋着法生成中最著名的辅助方法莫过于位棋盘了。位棋盘是由前苏联KASS工A小组于60年代提出的数据结构。国际象棋的位棋盘其实就是一个64位长度的变量，用来记录国际象棋棋盘上的某些布尔值。因为国际象棋棋盘上有64格，所以用64位二进制数正好与之对应。位棋盘就是棋盘的每一格用0或1来表示，用来判断每个格子的状态是“是”还是“否”。而中国象棋棋盘总共有90个点，故可以用3个32位的字来表示。
一个完整的中国象棋棋盘局面需要用14个比特棋盘来表示：红帅，黑将，红仕，黑士等等。另外再用两个比特棋盘来表示“所有红子”和“所有黑子”的位棋盘，可以加快运算速度。还可以通过再加入位棋盘来表示被某种棋子所攻击到的棋子，这样可以进一步走法产生的效率。
在象棋里，有很多着法可以到达相同的位置。有不同的路线可以达到同样位置的，这种现象称为“置换”(Transposing)。
置换表存储的是已经搜索过的结果，它通常使用类似于散列表(HashDictionary)的数据结构来达到最快的查询速度。在搜索某个局面时，结果(包括局面分析的值、搜索深度、最佳着法等)就存储到置换表里。当搜索新的局面时，我们先从置换表里找，如果已经有这种局面，那么就可以利用它，省去重复的搜索。
这种处理有以下很多好处：
1.加快速度。在置换情况发生得很多时(特别是残局局面里，棋盘上棋子很少时)，90%以上的局面可以在表中找到。
2.任意深度。假设你需要对某个局面搜索到一个指定的深度，例如4步(也就是两个回合)，如果置换表里有这个局面而且已经搜索了6步，那么你不仅可以跳过这次搜索，还可以得到比预期更精确的结果。
3.用途广泛。通常每个象棋程序都配有“开局库”(OpeningBook)，即包含一些常见局面及其最好的着法，这些通常是从已有的记载中提炼的。有了开局库，程序就不必在开局阶段就做傻事了。既然开局库的操作过程和置换表是一样的(即搜索局面)，那么为什么不在棋局一开始就把开局库装入我们的置换表里去呢？如果这样做，即使棋局暂时脱离了开局库，后来又回到开局库里的局面，那么置换表里保留了这样的局面，我们仍旧有机会用到它。
走法产生是指将一个局面的所有可能的走法罗列出来的那一个模块，也
就是告诉其他部分下一步可以往哪里走的模块。由于各种棋类规则的不同，
走法产生的复杂程度也有很大的区别。例如，五子棋的棋盘上任意的空白点
都是合法的下子点。这样在五子棋的走法模块当中只要扫描棋盘，寻找所有
的空白，就可以罗列出所有符合规则的下一步下子点。
对于中国象棋，生成走法的时候，也可以有两种方法:棋盘扫描法和预
置表法。而且由于象棋的规则更加的复杂，所以就要根据具体的规则来设计
走法，比如象只可以走田字，马只可以走日字，兵不可后退只能前进一步，
用棋盘扫描法就要根据棋子的具体走法在棋盘上反复扫描有效区域，制约条
位置、针对棋子的全部可能分布，事先给出可能的吃子走法和非吃子走法的
关系写入一个预置表中，再通过查表，便很快可以得到可行的着法，虽然这
样需要占用一定的空间，但相对现在的硬件环境应该说还是可以接受的，它
可以将着法生成的速度提高几个数量级。
在进行走法产生的时候，往往伴随着搜索进行。对于一个局面的所有直
接后继，你可以有两种选择:一次产生一种走法然后搜索之;或者一次产生
其所有走法然后搜索之。由于存在着剪枝算法，对一个局面的某一走法搜索
之后往往可能不再需要搜索其他后继，也就是说:可能不用产生全部走法就
能够完成搜索。一次产生一种走法看起来似乎更有效率。但是，由于剪枝算
法的剪枝效率很大程度上依赖于节点的排列顺序，往往一次产生所有节点，
然后以某种方法调整其排列顺序会使搜索效率大大提高。所以，在实际使用
中，绝大部分程序都是一次产生一个局面的全部走法，然后调整其搜索顺序。
本章在阐述了博弈树概念的基础上，分析了基本的博弈树搜索算法，为后继章节中搜索算法优化打下基础。
如果参加博弈的不是一个主体，而是对抗性的敌我双方，则搜索的进程不仅仅取决于其中一方的意愿，而是取决于对方应付的策略。由此而产生的搜索树，通常称为博弈树[5]。图2.2就是一颗红方走棋时展开的4层博弈树。
图2.2红方走棋时展开的4层博弈树
吴昊注释：博弈树算法在我以后的一些Round中，比如在黑白棋中，我还会聊到的。
极大极小值算法是解决博弈树问题的基本方法。
在象棋博弈中，极大极小值算法体现在始终站在博弈一方的立场选择着法。因为一方所追求的利益恰是另一方极力避免的，所以在这一方行棋的时候，选择价值极大的儿子节点着法，另一方行棋则选择价值极小的儿子节点着法。这就是一个极大极小过程。
图2.3极大极小搜索
在图2.3中，最底层为当前搜索深度(5层)下对各个可能出现的棋面进行估值的结果，按照由底向上推理，先由黑方选择从第5层各个子节点中选择较小的值推出第4层各个父节点，然后红方从第4各个节点中选择教大的值向上推出第3层各个父节点，依次交替类推，推出第一层的节点值，从而选择出博弈路径。
以下是极大极小算法的C伪码(并给出相应的注释):
普通的极大极小值算法有点麻烦，一方试图取极小值，而另一方试图取极大值，也就是说我们总要检查哪一方要取极大值。负极大值法是一种可以避免此类判断的算法，负极大值算的值是各子节点的值的负数的极大值。如要这个算法正确运作。例如象棋，估值函数必须对谁走棋敏感，也就是说对于一正的估值的话，则对于一个该黑方走棋的局面返回负的估值。这样才能保证原来取极大值还是取极大值，原来取极小值则转变成取儿子节点负数的极大值。
以下是负极大值法的C伪码(并给出相应的注释):
极大极小算法有个弱点，从简单的例子中还不能明显地看出来——要检查的各种路线的数量是指数形式的，这就意味者工作量会以几何级数增长。
1.每方有多少种可能的着法，这个数称为分枝因子(BranchFactor)，用B表示；
2.考虑的深度用N表示，通常说“N层”，“N”是整数，层表示一个棋手走的一步棋。
例如在象棋中，通常在中局阶段分枝因子大约为35种着法，在黑白棋中大约为8。由于极大极小算法的复杂度是O(BN)，所以对一个局面搜索4层就需要检查150万条路线。再增加上去，5层就会把搜索树膨胀到5000万，6层则达到18亿！
1958年，匹兹堡大学的三位科学家奈维尔、肖恩和西蒙(Newell,ShawandSimon)有重大发现：可以从搜索树中剔除相当大的部分而不影响最后结果，他们把这叫Alpha-Beta算法。很重要指出的是，这是一个纯数学领域的技巧，独立于任何国际象棋知识而生效，即它是一个无损，通用的剪枝技巧。
Alpha-Beta算法的原理是根据当前的信息确定儿子节点的上下界Alpha，Beta，然后根据儿子节点的儿子节点返回值进行剪枝操作。其具体过程如图2.4所示：
图2.4Alpha-Beta剪枝示意图
图2.4左半部分是一颗极大极小树的片段，节点下面的数字为该节点的值，搜索开始时，A为MAX局面，要从所有的儿子节点中返回最大值，首先搜索第一个子节点B，假定得到返回值10，那么此时可以确定A的值必定>=10。接着搜索C的第一个子节点D，得到值8，因为C为MIN局面，返回所有子节点最小值，此时可以确定C的值必定<=8。不论E,F等其他C的子节点可以取道多大的值，C的值都会小于B，不会被A选中，即可剪去对等其他C的子节点的搜索。此为Alpha剪枝(下界剪枝)。
图2.4右半部分是是一颗极大极小树的片段，节点下面的数字为该节点的值，搜索开始时，A为MIN局面，要从所有的儿子节点中返回最小值，首先搜索第一个子节点B，假定得到返回值10，那么此时可以确定A的值必定<=10。接着搜索C的第一个子节点D，得到值12，因为C为MAX局面，返回所有子节点最大值，此时可以确定C的值必定>=12。不论E,F等其他C的子节点可以取道多小的值，C的值都会大于B，不会被A选中，即可剪去对等其他C的子节点的搜索。此为Beta剪枝(上界剪枝)。
如果能尽早的找到值较大的子节点，则能在搜索中剪去很多兄弟节点。所以说Alpha-Beta算法的效率很大程度上受子节点顺序的影响。
1975年Knuth和Moore给出了Alpha-Beta正确性的数学证明。Alpha-Beta剪枝算法的节点数目为:
ND=2BD/2-1(D为偶数)
ND=2B(D+1)/2+B(D-1)/2-1(D为奇数)
其中D为搜索深度，B为分枝因子。在不使用Alpha-Beta剪枝时，需要搜索的节点数目是ND=BD，即极大树。所以最理想情况下Alpha-Beta算法搜索深度为D的节点数相当于搜索深度为D/2的不做任何剪枝节点数。
以下是Alpha-Beta算法的C伪码，用负极大值法实现。
现有的计算机的运算能力仍然十分有限，不可能一直搜索到分出输赢的那一步，在有限搜索深度的末端，我们用一些静态的方法，来估计局面的优劣，这就是估值函数，而估值算法的好坏往往决定了整个系统的棋力。目前主要的估值算法有两种，线性静态估值和基于人工神经网络的动态估值，而后者正是目前该领域研究的主要方向。
在第四章，本文提出了一种基于静态评估的动态局势再评估算法，经实验分析，证实了该算法在很大情况下会优与传统的线性静态评估算法。
本章是对构成整个中国象棋计算机博弈系统的关键性技术的一个总体介绍。阐述了各个部分的基本思想，无论是哪种棋类，他们都是由以上几个部分组成的，即：数据结构，着法生成，搜索算法和估值算法。数据结构和着法生成是整个系统的底层，而搜索算法和估值算法是整个系统的核心，估值算法往往决定了系统的棋力，搜索算法则解决如何尽快的找到能导致最优解(估值最大)的那步着法，其中搜索算法和估值算法是后续章节的主要内容，也是本文研究的重点。