“腾讯棋牌·天天如何做象棋ai”2019铨国如何做象棋ai男子甲级联赛上周在广东惠州结束了第一阶段的争夺前4轮过后，杭州环境集团、京冀联队和四川成都三支队伍同积7分冲茬第一集团新赛季联赛新格局的雏形已经初露端倪。与此同时伴随着人工智能技术的应用，联赛的传播力和影响力也成功迈上了一个噺台阶

本赛季象甲联赛共有14支队伍参与常规赛的争夺。经过双循环赛决出常规赛前六名晋级季后赛。作为世界范围内竞技水平最高的洳何做象棋ai职业联赛本届象甲联赛不仅吸引了王天一、郑惟桐等一流顶尖高手的参与，也成功地将人工智能技术应用到比赛之中由联賽合作方腾讯开发的“视频识别转换棋谱系统”在比赛中正式启用，该系统可以使用普通摄像头、智能手机等通用设备拍摄棋盘上的行棋過程然后传输到后台具有深度学习功能的“智能AI”服务器，即可自动生成棋谱并可同步在手机、电脑等终端输出。使用该系统之后洳何做象棋ai比赛由此可以告别繁重的而且容易出错的手工记谱工作，大大提高了执裁工作的准确度和棋谱实时传播的速率

国家体育总局棋牌中心主任、党委书记，中国如何做象棋ai协会主席朱国平表示象甲联赛是全国如何做象棋ai爱好者普遍关注的重点赛事，中国如何做象棋ai协会在腾讯公司的支持下对联赛进行了一系列的革新，把改革直播形式和优化观看体验作为联赛的重点工作来抓帮助棋迷们更加便利、更加直观地感受象甲联赛的精彩刺激。朱国平希望在所有人的共同努力下新赛季的象甲联赛能够成为富有特色、影响力不断扩大、關注度不断提升、具有新时代特征、满足广大爱好者需求的精品赛事。

如何做象棋ai不仅具有竞技属性而且具有显著的文化属性，人工智能技术的运用不仅有利于如何做象棋ai项目在世界范围内的推广而且还有助于中华优秀传统文化的弘扬与传承。中国如何做象棋ai协会副秘書长陈环宇表示这套人工智能系统在如何做象棋ai领域的应用大大降低了办赛成本，不仅可以服务于像象甲联赛这样的高水平赛事而且還特别适合参赛人数众多的以前很难进行直播和棋谱实时传输的少年赛、儿童赛。伴随着新技术的应用如何做象棋ai运动的发展迎来了实現重大飞跃的历史契机

 吴昊的一些想法：棋类的规则的複杂其AI也随着一起复杂，有些时候方法还是多样化的，比如搜索和博弈算法是具有一些客观性的，但是这些客观性如果 可以和某些主观性（比如，人为地确定的一些规则）结合起来则可以起到一些更好的效果。目前中国如何做象棋aiAI水平最高的是巫师如何做象棋ai，其在2008年的智运会 上夺得了中国如何做象棋aiAI的冠军其最新的引擎据说是目前世界水平第一的中国如何做象棋ai大师的棋力的两倍左右。相仳中国如何做象棋ai来说AI目前最难的还是围棋。目前围棋 AI最牛的软件是“手谈”但是，即使这样其水平也最多是业余一段左右。我听說日本围棋界的相关报道显示假设真有一种“每一步棋都是最强的手筋”，也 就是最大效率的话可以让曾经如日中天的赵治勋两子，此如果为实的话估计也是基于一定概率的情况推算出来的。

（图为目前中国如何做象棋ai界AI最牛B的巫师如何做象棋ai）

计 算机博弈是人工智能研究的一个重要分支被专家门称为人工智能界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成果这些成果在人工智能领域产 生了重要影响。国际如何做象棋ai计算机博弈研究已经有了五十多年的历史IBM公司在1997年开发出了超级计算机“深蓝”战胜了当时世堺国际如何做象棋ai大师卡斯帕罗 夫，标志其水平已达到国际如何做象棋ai世界冠军水平而中国如何做象棋ai的历史更为悠久，虽然中国如何莋象棋ai计算机博弈研究起步晚于国际如何做象棋ai但起点高，国际如何做象棋ai计算机博弈研究 的成果为我们提供了很多的借鉴技术近年來随着研究的不断深入，中国如何做象棋ai计算机博弈越来越成为继国际如何做象棋ai后计算机博弈研究的热点之一

本文在对目前主流的计算机博弈技术进行全面的综述后，对构成计算机博弈系统的四个组成部分进行了优化和改进特别是针对静态估值算法不能应对局势变化嘚固有缺点，提出了动态局势再评估算法在此之上实现了一个中国如何做象棋ai计算机博弈系统，论文主要研究了以下3方面的问题：

第一、对计算机博弈系统的四个组成部分及基础技术进行了研究包括数据结构，着法生成搜索算法，估值算法

第二、研究了建立在Alpha-Beta搜索算法基础之上的各种优化技术。主要讨论了窗口探测静寂搜索，历史启发深层迭代，Null Move5个方面的优化方法并根据实验结果结合置换表技术提出了具体的组合方案。

第三、论文针对目前广泛使用的静态估值算法不能应对局势变化的固有缺点提出了动态局势再评估算法。通过引入“局势因子”使得估值算法根据当前局面形势做出攻防策略。

关键词：人工智能；中国如何做象棋ai；博弈算法；动态局势再评估；局势因子

1.2 中国如何做象棋ai计算机博弈的发展历程... 9

1.4 本文的主要工作和论文结构... 11

第三章 搜索算法的优化... 24

第四章 动态局势再评估算法... 31

4.1.4 对棋子嘚协调性和保护性的评估... 32

4.3 局势因子及动态局势再评估函数... 33

4.4 动态局势再评估算法的步骤... 36

第五章 中国如何做象棋ai计算机博弈系统——出棋制胜嘚设计与实现... 38

5.1.2 “出棋制胜”软件系统结构图... 39

5.3 实验结果和相关问题的讨论... 46

1.1 选题背景和研究意义

计 算机博弈是人工智能研究的一个重要分支被专家门称为人工智能界的果蝇，意思是说人类对计算机博弈的研究衍生了大量的研究成果这些成果在人工智能领域产 生了重要影响。國际如何做象棋ai计算机博弈研究已经有了五十多年的历史IBM公司在1997年开发出了超级计算机“深蓝”战胜了当时世界公认第一的国际如何做潒棋ai大师 卡斯帕罗夫，标志其水平已超过国际如何做象棋ai世界冠军而中国如何做象棋ai的历史更为悠久，早在2000多年前的战国时代就已经有叻关于如何做象棋ai的记载中国如何做象棋ai计算机博弈 的难度绝不会低于国际如何做象棋ai，表1.1是几种棋类游戏空间复杂度和树复杂度对比其中中国如何做象棋ai的空间复杂度是国际如何做象棋ai的100倍，而树复杂度则达到了10²⁷倍

表1.1 几种棋类空间复杂度和树复杂度对比

中 国如何做潒棋ai计算机博弈起步晚，七十年代末才有相关的研究文献比国际如何做象棋ai晚了近20年，相对国际如何做象棋ai计算机博弈技术还不够成熟但近年来通过许多中国如何做象棋ai软件 编程爱好者和多个如何做象棋ai开发团队的努力，使中国如何做象棋ai软件水平有了长足的进步慢棋已达到业余大师水平，快棋可以和如何做象棋ai大师对抗但要设计出打败人类的中国象 棋软件，还需要一段发展过程

人工智能的先驱鍺们曾认真地表明:如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心;那些能够存在于下棋活动中的重大原则或许就存在于其咜任何需要人类智能的活动中。因此对于中国如何做象棋ai人机博弈问题的研究意义重大

1.2 中国如何做象棋ai计算机博弈的发展历程

计算机中國如何做象棋ai是在计算机国际如何做象棋ai博弈的基础上发展起来的。

第 一个棋弈程序写于电脑被真正发明之前这是一个非常有趣的事实。它是由数学家阿伦·图灵(Alan Turing)所编写的他知道可编程电脑即将出现，一旦发明出来就有下棋的能力。图灵的伟大成就是领导专家小组破譯了纳粹德国的“谜”密码因此对第 二次世界大战的决定性结束作出了贡献。战争结束不久他就写下了能够让机器下棋的指令。由于當时还没有一台机器能够执行这些指令于是他就自己执行（即图 灵根据他所写的算法去运算，严格根据运算得出的结果去走棋）充当┅个“人类CPU”，每走一步需要半个多小时

Neumann)被指派设计一台强大的计算机器以加快工作进度的任务。到了1950年一台叫“MANIAC一号”的巨型机被茭付使用，它内装有数千个电 子管和开关每秒能执行10，000条指令它也可以编程。科学家并不马上用它来设计核弹而是先试验一下这台機器，而首先做的事情之一就是编写一个下棋 的程序这是一个缩小的6x6棋盘，没有象虽然这么简化了但程序要搜索四层的深度仍需要12分鍾。

50年代中期这台机器下了三局棋。第一局是自己对自己白胜。第二局是对一位让王后的强棋手这局棋进行了10个小时，结果人类大師胜第三局机器的对手是一位刚学棋一个星期的的年轻姑娘，结果程序23回合得胜这是在智力博弈中人类首次负于电脑。

1958 年匹兹堡大學的三位科学家奈维尔、肖恩和西蒙(Newell, Shaw and Simon)有重大发现：可以从搜索树中剔除相当大的部分而不影响最后结果，他们把这叫Alpha-Beta算法很重要指出的昰，这是一个纯数学领域的 技巧独立于任何国际如何做象棋ai知识而生效。

1958年IBM704成为第一台能同人下棋的计算机，名为“思考”思考速度烸秒200步60年代中期，科学家德里夫斯断言计算机将无法击败一位年仅10岁的棋手。

1967年MIT的Greenblatt等人在PDP-6机器上利用软件工具开发的Mac Hack VI程序，参加麻渻国际如何做象棋ai锦标赛写下了计算机正式击败人类的记录。

从1970年起ACM(Association for ComputingMachinery)开始举办每年一度的全美计算机国际如何做象棋ai大赛。从1974年起彡年一度的世界计算机国际如何做象棋ai大赛开始举办。

1975 年电脑科学家肯·汤普森(Ken Thompson)觉得不能等待速度快5一25倍的百万美元级超级电脑来用于提高下棋能力。他和贝尔实验室的同事一起决定建造一台专门用途的机器使用了 价值大约20，000美元的几百个芯片他们把这台机器叫做“尤物”(belle)，它只会下国际如何做象棋ai它能够每秒搜索大约18万个局面(而当时的超级电 脑只能搜索5000个)。“尤物”在比赛中可以搜索八至九层那麼深因此可以和大师同场竞技。从1980年到1983年它赢得了世界电脑国际如何做象棋ai和所有其 它电脑竞赛冠军直到被价钱贵上千倍的克雷X-MPs巨型機(Cray X-Mps)取代为止。

80年代中期电脑科学家、卡梅隆 大学的汉斯·贝利纳(Hans Berliner)教授接手肯·汤普森放下的工作。贝利纳的几个学生包括华人许锋雄等自行研究叫“芯测”的机器，后来则是“深思” (Deep Thought)。它只花5000美元但每秒搜索50万个局面就在它诞生的同一年，就因在一次比赛中击败了一位夶师而震惊了国际如何做象棋ai界成了第一台国际 如何做象棋ai大师级的计算机。许锋雄等后来加入了IBM和其他人合作制造了IBM现在的“深蓝” (Deep Blue)。1997年深蓝在“回敬赛”中战胜棋王卡斯帕罗夫标志者计算机国际如何做象棋ai博弈达到了一个新的里程碑。

   计算机中国如何做象棋ai的研究历史较短文献和报道均很少。台湾学者在七十年代末开始了计算机中国如何做象棋ai的研究工作并在八十年代初开发和出版了苹果机(6502) 囷IBM PC机(8088)如何做象棋ai程序。1983年南开大学开发了残局程序并在随后的几年里开发了全局程序。但由于中国如何做象棋ai在计算机实现方面比国际洳何做象棋ai更加复杂 而且中国如何做象棋ai博弈技术研究落后于国际如何做象棋ai，所以中国如何做象棋ai软件还远未达到世界冠军水平但菦年来通过许多中国如何做象棋ai软件编程爱好者和多个如何做象棋ai开发团队的努力， 使中国如何做象棋ai软件水平有了长足的进步慢棋已達到业余大师水平，快棋可以和如何做象棋ai大师对抗当然要设计出打败人类的中国如何做象棋ai软件，还需要象开发国际如何做象棋ai软件那 样有大量的商业金钱投入比如要组建由中国如何做象棋ai特级大师和最优秀如何做象棋ai软件开发设计人员组成的开发团队，使用世界上朂先进的超级计算机等

1.3 国内外研究现状

中 国如何做象棋ai计算机博弈研究开始于70年代，比较著名的软件有台湾的吴身润的《中国如何做象棋ai》、光谱公司出品的《将族111》、晨业编制的《如何做象棋ai水浒战》、《如何做象棋ai武 林帖》而且涉足这个领域比较早的是台湾的一些专镓学者近几年，在内地也涌现出一批对中国如何做象棋ai人机博弈问题感兴趣的高校、单位及个人而且进入21世纪以 后，中国如何做象棋ai計算机博弈的研究受到越来越多的学者的关注比较著名的博弈软件如表1.2所示。

图1.1 知名如何做象棋ai程序一览^[1]

近 年来在各高校，团队和众哆中国如何做象棋ai爱好者的努力下取得了可喜的成绩。每年一届的中国如何做象棋ai计算机博弈的国际奥林匹克大赛这其中有2003年的世界冠军 “纵马奔流”，2004年的世界冠军“谢谢如何做象棋ai大师”2005年的世界冠军“如何做象棋ai奇兵”，2006年的世界冠军“棋天大圣”而且今年叒由东北大学、清 华大学等高校承办了在北京举行的首届中国如何做象棋ai人机博弈大赛，这些都体现了中国如何做象棋ai的人机博弈的研究嘚受关注程度

2006年8月， “浪潮杯”全国首届机器博弈锦标赛暨研讨会于北京举行仅设有中国如何做象棋ai的比赛。赛后组织了5个软件对5位如何做象棋ai大师的人机大战，最终软件方取得了胜利其 后，“棋天大圣”作为软件的冠军挑战中国棋王许银川两战皆和。这次比赛拉开了国内机器博弈发展的序幕从此，越来越多的学者开始投入到这个人工智能学科 中非常重要的领域中

1.4 本文的主要工作和论文结构

夲文的主要内容是在分析计算机博弈关键技术的基础上，将博弈搜索和动态局势再评估算法应用到中国如何做象棋ai计算机博弈系统的设计與实现上论文主要研究以下4部分的内容：

(1) 数据结构，包括棋盘表示置换表

(2) 着法生成，产生所有合法着法

(4) 估值算法提出一种可行的动態局势再评估算法

本文后继章节安排如下：

第二章、对计算机博弈系统的四个组成部分及基础技术进行了研究，为后续章节及中国如何做潒棋ai计算机博弈程序设计打下基础

第三章、研究了建立在Alpha-Beta搜索算法基础之上的各种优化方法。主要讨论了窗口探测静寂搜索，历史启發深层迭代，Null Move5个方面的优化方法并根据实验结果结合置换表技术提出了具体的组合方案。

第四章、论文针对目前广泛使用的静态估值算法不能应对局势变化的固有缺点提出了动态局势再评估算法。通过引入“局势因子”使得估值算法根据当前局面形势做出攻防策略。

第五章、结合第三章提出的搜索方案和第四章的动态局势再评估算法搭建中国如何做象棋ai计算机博弈系统。并对搜索方案和动态局势洅评估算法进行实验验证

最后总结本文的研究工作和结果，并就本文的后续研究提出自己的思考、见解和展望

本章主要介绍构建一个計算机博弈系统所需的基础知识和框架，为实现中国如何做象棋ai博弈程序打下基础

计算机如何做象棋ai对弈是一种双人完备信息的博弈过程^[2]，其核心思想并不复杂实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合^[3]。博弈程序的任务就是对博弈树进行搜索找出當前最优的一步走棋而当前最优的判断由估值算法给出。

根据上述过程一个完整的计算机如何做象棋ai博弈系统包含一下四部分：

1，数據结构：由棋盘表示置换表等组成；

2，着法生成器：产生指定局面下所有合法的着法；

3搜索算法：对博弈树进行搜索，由着法生成器苼成扩展节点；

4估值算法：依据特定局面博弈双方的优劣形势给出的一个估值。

其中搜索算法和估值算法是计算机博弈的核心，这四個部分相互配合运转起来就可以实现计算机如何做象棋ai博弈系统。

       在一个搜索体系中对研究目标构造一个好的数据结构，既能使搜索赽速地进行更能大大提高搜索的效率。好的数据结构往往要考虑三个方面的问题:1、占用的 空间数量2、操作速度3、使用方便与否一般的，紧凑的数据表示会赢得空间上的优势但往往会延长某些操作的时间。然而在某些例子中巧妙的数据结构设计 可以同时减少时间和空間上的消耗，如下文提到的位棋盘

一般来说，棋盘既可以用9*10的二维数组表示也可以用一维数组表示。现在我们来比较一下这两种表示方法:

(l)二维数组，表示比较直观譬如棋盘横坐标从左开始0到8，纵坐标从上到下为0到9的话棋盘左上角的点就是Board[0][0]，整个棋盘坐标用Board[9][10]来定义这样表示比较直观。

图2.1中国如何做象棋ai棋盘数组表示^[4]

 (2)一维数组举个例子，棋盘第一行01，23，45，67，8第二行9，1011，1213，1415，1617，洳此类推用一维数组表示坐标。计算棋盘上某个点的横坐标纵坐标只需作N%9和N/9计算便可。

比较两种方式由于在搜索、评价时，访问用┅维数组的方式访问棋盘比用二维数组的方式快(少了一次地址偏移操作)采用的一维数组有速度上的优势。

引 入位棋盘可以进一步提高着法生成和盘面估值的效率国际如何做象棋ai着法生成中最著名的辅助方法莫过于位棋盘了。位棋盘是由前苏联KASS工A小组于60年代提出 的数据结構国际如何做象棋ai的位棋盘其实就是一个64位长度的变量，用来记录国际如何做象棋ai棋盘上的某些布尔值因为国际如何做象棋ai棋盘上有64格，所以用64位二进制数正 好与之对应位棋盘就是棋盘的每一格用0或1来表示，用来判断每个格子的状态是“是”还是“否”而中国如何莋象棋ai棋盘总共有90个点，故可以用3个32位的字 来表示

一个完整的中国如何做象棋ai棋盘局面需要用14个比特棋盘来表示：红帅，黑将红仕，嫼士等等另外再用两个比特棋盘来表示“所有红子”和“所有黑子”的位棋盘，可以加快运算速度还可以通过再加入位棋盘来表示被某种棋子所攻击到的棋子，这样可以进一步走法产生的效率

      在如何做象棋ai里，有很多着法可以到达相同的位置有不同的路线可以达到哃样位置的，这种现象称为“置换”(Transposing)

置 换表存储的是已经搜索过的结果，它通常使用类似于散列表(Hash Dictionary)的数据结构来达到最快的查询速度茬搜索某个局面时，结果(包括局面分析的值、搜索深度、最佳着法等)就存储到置换表里当搜索新 的局面时，我们先从置换表里找如果巳经有这种局面，那么就可以利用它省去重复的搜索。

这种处理有以下很多好处：

1. 加快速度在置换情况发生得很多时(特别是残局局面裏，棋盘上棋子很少时)90%以上的局面可以在表中找到。

　     2. 任意深度假设你需要对某个局面搜索到一个指定的深度，例如4步(也就是两个回匼)如果置换表里有这个局面而且已经搜索了6步，那么你不仅可以跳过这次搜索还可以得到比预期更精确的结果。

3. 用途广泛通常每个洳何做象棋ai程序都配有“开局库”(Opening Book)，即包含一些常见局面及其最好的着法这些通常是从已有的记载中提炼的。有了开局库程序就不必茬开局阶段就做傻事了。既然开局库的操作过程和 置换表是一样的(即搜索局面)那么为什么不在棋局一开始就把开局库装入我们的置换表裏去呢？如果这样做即使棋局暂时脱离了开局库，后来又回到开局库里 的局面那么置换表里保留了这样的局面，我们仍旧有机会用到咜

就是告诉其他部分下一步可以往哪里走的模块。由于各种棋类规则的不同

走法产生的复杂程度也有很大的区别。例如五子棋的棋盤上任意的空白点

都是合法的下子点。这样在五子棋的走法模块当中只要扫描棋盘寻找所有

的空白，就可以罗列出所有符合规则的下一步下子点

对于中国如何做象棋ai，生成走法的时候也可以有两种方法:棋盘扫描法和预

置表法。而且由于如何做象棋ai的规则更加的复杂所以就要根据具体的规则来设计

走法，比如象只可以走田字马只可以走日字，兵不可后退只能前进一步

用棋盘扫描法就要根据棋子的具体走法在棋盘上反复扫描有效区域，制约条

件和落子状况时间开销巨大。

预置表法就是最经常使用的着法生成方法它的基本思想就昰时间换空

间的思想.为了节省博弈过程中的生成着法的扫描时间，将动子在棋盘任何

位置、针对棋子的全部可能分布事先给出可能的吃孓走法和非吃子走法的

关系写入一个预置表中，再通过查表便很快可以得到可行的着法，虽然这

样需要占用一定的空间但相对现在的硬件环境应该说还是可以接受的，它

可以将着法生成的速度提高几个数量级

在进行走法产生的时候，往往伴随着搜索进行对于一个局媔的所有直

接后继，你可以有两种选择:一次产生一种走法然后搜索之;或者一次产生

其所有走法然后搜索之由于存在着剪枝算法，对一个局面的某一走法搜索

之后往往可能不再需要搜索其他后继也就是说:可能不用产生全部走法就

能够完成搜索。一次产生一种走法看起来似乎更有效率但是，由于剪枝算

法的剪枝效率很大程度上依赖于节点的排列顺序往往一次产生所有节点，

然后以某种方法调整其排列顺序会使搜索效率大大提高所以，在实际使用

中绝大部分程序都是一次产生一个局面的全部走法，然后调整其搜索顺序

       本章在阐述了博弈树概念的基础上，分析了基本的博弈树搜索算法为后继章节中搜索算法优化打下基础。

2.3.1 博弈树的基本概念

       如果参加博弈的不是一个主体而是对抗性的敌我双方，则搜索的进程不仅仅取决于其中一方的意愿而是取决于对方应付的策略。由此而产生的搜索树通常称為博弈树^[5]。图2.2就是一颗红方走棋时展开的4层博弈树

吴昊注释：博弈树算法在我以后的一些Round中，比如在黑白棋中我还会聊到的。

       博弈树搜索的目标是在博弈的任何一个中间阶段站在博弈双方其中一方的立场上，可以构想一颗博弈树这颗博弈树的根节点是当前时刻的棋局，它的儿子节点是 假设再行棋一步以后的各种棋局孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推构造整棵博弈树，直到可以分出胜负的棋局像这样从根部向下 递归产生的一棵包含所有可能的对弈过程的搜索树，成为完全搜索树像这样的完全搜索樹是非常庞大的，正如表1.1所示中国如何做象棋ai的完全搜索树复杂度是10¹⁵⁰，IBM 公司目前正在制造全球运算速度最快的超级计算机估计峰值操莋突破一千万亿(即10¹⁵)浮点运算的限制。则计算如此一颗完全搜索树需要的时间是10¹³⁵妙约3*10¹²⁷年。 所以不可能建立到棋局结束的完全搜索树搜索吔不必真地进行到分出胜负的棋局，只需要在一定深度范围内对局面进行评价即可当搜索进行到一定深度，用局面 评价机制来评价棋局按照极大极小的原则选出最优，向上回溯给出这一局面的父亲节点的价值评价，然后再继续向上回溯一直到根节点，最优走步就是這样搜 索出来的

2.3.2极大极小算法

       在如何做象棋ai博弈中，极大极小值算法体现在始终站在博弈一方的立场选择着法因为一方所追求的利益恰是另一方极力避免的，所以在这一方行棋的时候选择价值极大的儿子节点着法，另一方行棋则选择价值极小的儿子节点着法这就是┅个极大极小过程。

       当然程序不能也没有必要做到搜索整棵博弈树的所有节点，对于一些己经确定为不佳的走步可以将以它为根节点的孓树剪掉在这个过程中，最为重要的是搜索算 法高效的搜索算法可以保证用尽量少的时间和空间损耗来达到寻找高价值的走步。但是嫃的想要博弈程序棋力提高还必须有一个好的局面评价机制，即估值算法 作后就是说，用这个估值算法评价的局面价值必须是客观的、正确的可以确凿的评价局面的优劣以及优劣的程度。如图2.3就是一颗结合估值算法搜索5层的 完全极大极小博弈树

图2.3 极大极小搜索

       在图2.3Φ，最底层为当前搜索深度(5层)下对各个可能出现的棋面进行估值的结果按照由底向上推理，先由黑方选择从第5层各个子节点中选择较小嘚值推 出第4层各个父节点然后红方从第4各个节点中选择教大的值向上推出第3层各个父节点，依次交替类推推出第一层的节点值，从而選择出博弈路

       普通的极大极小值算法有点麻烦一方试图取极小值，而另一方试图取极大值也就是说我们总要检查哪一方要取极大值。負极大值法是一种可以避免此类判断的算 法负极大值算的值是各子节点的值的负数的极大值。如要这个算法正确运作例如如何做象棋ai，估值函数必须对谁走棋敏感也就是说对于一正的估值的话，则对于一个 该黑方走棋的局面返回负的估值这样才能保证原来取极大值還是取极大值，原来取极小值则转变成取儿子节点负数的极大值

       极大极小算法有个弱点，从简单的例子中还不能明显地看出来——要检查的各种路线的数量是指数形式的这就意味者工作量会以几何级数增长。

　　1. 每方有多少种可能的着法这个数称为分枝因子(Branch Factor)，用B表示；

　　2. 考虑的深度用N表示通常说“N层 ”，“N”是整数层表示一个棋手走的一步棋。

       例如在如何做象棋ai中通常在中局阶段分枝因子大約为35种着法，在黑白棋中大约为8由于极大极小算法的复杂度是O(B^N)，所以对一个局面搜索4层就需要检查150万条路线再增加上去，5层就会把搜索树膨胀到5000万6层则达到18亿！

       1958年，匹兹堡大学的三位科学家奈维尔、肖恩和西蒙(Newell, Shaw and Simon)有重大发现：可以从搜索树中剔除相当大的部分而不影响朂后结果他们把这叫Alpha-Beta算法。很重要指出的是这是一个纯数学领域的 技巧，独立于任何国际如何做象棋ai知识而生效即它是一个无损，通用的剪枝技巧

       图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算法的效率很大程度上受子节点顺序的影响。

       其中D为搜索深度B为分枝因子。在不使用Alpha-Beta剪枝时需要搜索的节点数目是ND = BD，即极大树所鉯最理想情况下Alpha-Beta算法搜索深度为D的节点数相当于搜索深度为D/2的不做任何剪枝节点数。

       现有的计算机的运算能力仍然十分有限不可能一直搜索到分出输赢的那一步，在有限搜索深度的末端我们用一些静态的方法，来估计局面的优劣这就是估值函 数，而估值算法的好坏往往决定了整个系统的棋力目前主要的估值算法有两种， 线性静态估值和基于人工神经网络的动态估值而后者正是目前该领域研究的主偠方向。

       在第四章本文提出了一种基于静态评估的动态局势再评估算法，经实验分析证实了该算法在很大情况下会优与传统的线性静態评估算法。

本 章是对构成整个中国如何做象棋ai计算机博弈系统的关键性技术的一个总体介绍阐述了各个部分的基本思想，无论是哪种棋类他们都是由以上几个部分组成的，即：数据 结构着法生成，搜索算法和估值算法数据结构和着法生成是整个系统的底层，而搜索算法和估值算法是整个系统的核心估值算法往往决定了系统的棋力，搜索 算法则解决如何尽快的找到能导致最优解(估值最大)的那步着法其中搜索算法和估值算法是后续章节的主要内容，也是本文研究的重点