（计算机应用技术专业论文）混合博弈树算法在中国象棋人机博弈中的应用研究.pdf

摘要 摘要 计算机博弈是人工智能领域中最具有挑战性的科研课题之一。国际象棋的计算机博 弈已经有了很长的历史，在1 9 9 7 年i b m 公司的超级计算机“深蓝 与当时的国际象棋 大师卡斯帕罗夫进行了一场大战，并以“深蓝 计算机战胜世界棋王卡斯帕罗夫( 1 9 9 7 5 ) 而载入史册，因为它表明“计算机智能战胜了人类天才 。 为了能够在这一新兴的人工智能领域取得更快更多的突破性进展，有力发挥机器博 弈的“果蝇 作用，需要很好的明确当前机器博弈所面临的挑战。与国际象棋相比中国 象棋的历史更为悠久，其博弈难度水平决不亚于国际象棋，但是涉足学者太少，而且参 考资料不多。与国际象棋相比中国象棋的盘面规模更大、着法更为特殊、变化也更加复 杂，同时象棋也是一种完全知识博弈，意思是指参与双方在任何时候都完全清楚每一个 棋子是否存在，位于何处，只要看看棋盘，就一清二楚了。一个完备的中国象棋人机博 弈系统一般包括以下组成部分：棋盘表示、搜索引擎、估值核心、开局库、残局库。 本文通过对自行研制的象棋程序的数据表示、走法生成、搜索引擎、估值核心、开 局库模块的描述与分析，阐述了此象棋程序的设计与实现的原理，提出了一种新的混合 博弈树的搜索算法应用到中国象棋的程序中，明显的提高了程序的搜索效率；同时也设 计了一种新的评估函数在中国象棋开局库中的应用，结合了利用共轭梯度求解二次最优 的方法，尽可能的保证系统在开局阶段便处于优势，并使开局库具有一定的自学习能力， 提高了博弈水平。 关键词：人工智能；中国象棋；人机博弈；开局库 大连交通人学t 学硕+ 学位论文 a b s t r a c t c o m p u t e rg a m ei so n eo ft h em o s tc h a l l e n g i n gt o p i c si nt h ef i e l do fa r t i f i c i a li n t e l l i g e n c e c h e s sc o m p u t e rg a m eh a sal o n gh i s t o r y ，i nt h ey e a ro f19 9 7i b mc o r p o r a t i o nd e v e l o p e d s u p e r c o m p u t e r ”d a r kb l u e ”h a dab a t t l ew i t ht h ew o r l dc h e s sc h a m p i o n ，k a s p a r o v f i n a l l y ”d a r kb l u e ”d e f e a t e dk a s p a r o vi nm a y19 9 7 ，w h i c hm e a n st h a t “c o m p u t e ri n t e l l i g e n c ec o u l d d e f e a th u m a n g e n i u s ” i no r d e rt of a s t e nt h ed e v e l o p m e n to ft h en e wr e s e a r c hd o m a i nw i t hb r e a k t h r o u g hr e s u l t s a n dd r o s o p h i l ae f f e c t si na r t i f i c i a li n t e l l i g e n c e ，i ti sn e c e s s a r yt oc l e a rw h a ta r et h ec h a l l e n g i n g i s s u e sf a c e dt oc o m p u t e rg a m er e s e a r c h c h i n e s ec h e s sh a sa l o n gh i s t o r ya n dt h el e v e lo ft h e c h i n e s ec h e s sc o m p u t e rg a m ei sn o te a s i e rt h a nc h e s s n o to n l yt h en u m b e ro fs c h o l a rw h o j o i n si nt h ec o m p u t e rc h i n e s ec h e s sg a m ei sl i t t l eb u ta l s oi n f o r m a t i o nw h i c hi sw o r t ho f r e f e r e n c ei sf e w t h ed i f f i c u l t yo fc h i n e s ec h e s sc o m p u t e rg a m em o s t l yl i e s i nt h eg r e a t e r m o d e lo fc h e s s b o a r d ，t h em o r ed i f f e r e n tm o v eg e n e r a t i o na n dt h em o r ec o m p l e xc h a n g e m e a n w h i l ec h i n e s ec h e s sa l s oi sak i n do fg a m e so fp e r f e c ti n f o r m a t i o nw h i c hm e a n sa ta n y t i m eb o t hs i d e sc o m p l e t e l yk n o wc l e a r l yi fe v e r yc h e s s m a ni se x i s t e do rn o ta n dw h e r et h e y a r e i tw i l lb ec l e a r a s l o n ga sy o ut a k eal o o ka tt h ec h e s s b o a r d t h ec h i n e s ec h e s s m a n - m a c h i n eg a m b l i n gs y s t e mi s g e n e r a l l yi n c l u d e d ：t h eb o a r dr e p r e s e n t a t i o n ，m o v e g e n e r a t i o n ，t h es e a r c he n g i n e ，e v a l u a t i o nf u n c t i o n ，o p e n i n gb o o k sa n dt h ed a t a b a s eo f e n d g a m e s b yd e s c r i b i n ga n da n a l y z i n gt h em o d u l eo fc h e s sp r o g r a mw h i c hd e s i g nb ym y s e l fs u c h a si t sd a t ae x p r e s s i o n ，m o v eg e n e r a t i o n ，s e a r c he n g i n e ，e v a l u a t i o nf u n c t i o na n dd a t a b a s eo f s t a r t i n gg a m e ，t h i sa r t i c l ee x p o u n d st h ec h i n e s ec h e s sp r o g r a m sp r i n c i p l eo fd e s i g na n d r e a l i z a t i o n ，f u r t h e r m o r e ，i tp u t sf o r w a r dan e wh y b r i ds e a r c ha l g o r i t h ma n di m p r o v e s c a l c u l a t i o ne f f i c i e n c yo ft h ep r o g r a mo b v i o u s l ya f t e rb e i n ga p p l i e dt ot h ec h e s sp r o g r a m m e a n w h i l ed e s i g n e dan e we v a l u a t ef u n c t i o na p p l i e di nt h ec h i n e s ec h e s so p e n i n gb o o k sa n d c o m b i n e dw i mc o n j u g a t eg r a d i e n tm e t h o df o rs o l v i n gq u a d r a t i co p t i m a l t h ea p p l i c a t i o n m a k e st h eo p e n i n gb o o kb et h ef u n c t i o no fs e l f - s t u d y i n ga n dp r o m o t e st h es y s t e m sl e v e lo f m a t c h k e yw o r d s ：a r t i f i c i a li n t e l l i g e n c e ；c h i n e s ec h e s s ；m a n - m a c h i n em a t c h ；o p e n i n gb o o k i i 绪论 绪论 1 课题研究背景 象棋的计算机博弈可谓是人工智能学科的“果蝇 ，国际象棋的计算机博弈更是早 已开展得如火如荼，经历了很长的历史时期，并以i b m “深蓝 计算机战胜世界棋王卡 斯帕罗夫( 1 9 9 7 5 ) 而载入史册。 象棋的计算机博弈就是计算机下象棋。可以是计算机与棋手对弈，也可以是计算机 与计算机对弈，这不仅是计算机硬件性能的较量，更是计算机智能软件水平的较量。因 此，就在计算机问世不久，人们就将计算机博弈看作是人工智能领域最具挑战性的课题。 许多学者认为，对于人工智能研究而言，象棋的重要作用相当于遗传学研究的果 蝇。众所周知，果蝇就是水果上的苍蝇，个j l , 4 , ，但生命力极强。它最大的特点是繁殖 快，2 0 多天便能繁殖一代，并容易在短期内出现突变性状，所以果蝇正符合遗传学研究 的需要。摩尔根精心培养这些娇小的生灵。他和他的学生十年如一日长期观察，终于使 摩尔根的“蝇室 硕果累累，使经典遗传学进入顶峰时期。1 9 3 3 年摩尔根获得了诺贝尔 生理学和医学奖i l j 。 人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握了人类 智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要 人类智能的活动中。 而历史悠久的中国象棋的计算机搏弈与国际象棋博弈相比，不仅显得如此稚嫩，而 且在学术界无人问津。计算机与人工智能学科最具挑战性的课题却成为“爱情遗忘的角 落 ，这不能不说是一场历史的误会。近年来随着社会的关注，中国象棋计算机博弈发 展了起来并形成了一定的规模，展开了很多的比赛，同时也出现了很多获得奥林匹克大 奖的团体，使很多的学者和科技青年都投入到了轰轰烈烈的计算机博弈研究中，推动了 人工智能的发展。并且从2 0 0 6 年开始，由人工智能协会每年组织中国象棋计算机博弈 的比赛，不仅促进了国粹的发展也成了科技攻关的主题。 2 本文的主要工作 本文共完成了如下的工作： ( 1 ) 系统地研究了国际象棋以及中国象棋的理论和发展状况。 ( 2 ) 针对象棋博弈搜索中使用的算法进行了广泛的研究。 ( 3 ) 对解决开局库实现和优化的问题，进行了深入细致的研究。 ( 4 ) 在设计象棋程序搜索引擎的时候，应用了一种新的混合博弈树搜索算法，结合 大连交通人学工学硕士学位论文 多种搜索和剪枝算法，提高了搜索的效率并节省了搜索时间；并提出一种新的评估函数 在中国象棋开局库中的应用，利用共轭梯度法求解局面估值，并从中选出最好的局面作 为走法，大大的提高了开局的水平，为中局做好了铺垫；摒弃了只有一套基本位置值的 这种不合理的做法，采用了随着局势不同而有多套位置值的新想法，使中局与残局的子 力水平有了更加合适的分值，提高了棋力；并对并行博弈处理来解决搜索的问题进行了 深入的研究。使得系统能在最短的时间里取得了较大的变化。 ( 5 ) 设计并实现了一个中国象棋计算机博弈系统，并用理论和实际对算法性能进行 了验证。 3 本文框架 第一章阐述了国际象棋和中国象棋的发展和研究现状。 第二章论述了本系统所采用的基本搜索算法和高级搜索算法，并详细地介绍了各种 搜索算法的作用和性能。 第三章针对象棋程序的改进，提出了一种新的混合的博弈树搜索算法，置换表在混 合算法中的应用，博弈比赛过程中软件的时间策略，后台思考技术，以及通过使用量子 遗传算法对评估函数的优化，使用了一种新的区别中残局的棋子位置值，大大的提高了 棋力，使博弈水平有很大幅度提升。 第四章阐述了本博弈程序开局库系统的研制和改进，介绍了哈希技术在中国象棋博 弈软件开局库中的使用，提出了一种新的评估函数在开局库中的应用，提高了博弈的水 平，节省了一定的时间，并验证了这个评估函数的优越性。使开局库为中局的拼杀打下 了良好的基础。 第五章论述了残局库与并行搜索算法在象棋程序中的研究和应用，指出了残局库的 实现形式以及目前使用残局库存在的一些问题。本章的最后介绍了并行博弈处理。 本章小结 本章主要阐述了课题的研究背景和计算机象棋博弈的发展状况，介绍了在中国象棋 计算机博弈中引入的一些算法和本文所做的主要工作。并在本章最后介绍了论文书写的 总体结构框架。 2 第一章中国象棋计算机博弈问题的研究 第一章中国象棋计算机博弈问题的研究 在人类文明发展的初期，人们就开始进行棋类博弈的游戏了。所谓象棋的计算机博 弈就是指计算机下象棋。可以是计算机与棋手对弈，也可以是计算机与计算机对弈，这 不仅是计算机硬件性能的较量，更是计算机软件水平的较量。近几十年来，随着计算机 硬件和软件技术的不断发展，科学家们开始对电脑能否战胜人脑这个话题产生了浓厚的 兴趣，香农( 1 9 5 0 ) 与图灵( 1 9 5 3 ) 提出了对象棋博弈编程的方案，成为机器博弈的创始人， 科学家们同时也提出了以棋类对弈的方式，向人类智能发起挑战。博弈论研究的是人与 人之间利益相互制约下的策略选择的理性行为及相应结局。系统的博弈论的研究是从国 际象棋开始的，冯诺依曼通过对两人零和一类博弈游戏的分析，提出了极大极小值定 理【2 】，这也是博弈论产生的第一个里程碑。 6 0 年代中期，科学家德里夫斯断言，计算机将无法击败一位年仅1 0 岁的棋手。因 为当时机器的计算能力仅能达到每秒2 0 0 步，它的搜索深度最多也就能够达到6 层。到 了1 9 9 7 年“深蓝 小组开发的“超级深蓝 则可达到每秒2 亿步。这时的搜索深度可 以达到1 4 层，局部高达4 0 层。也就是在同年，i b m 公司的超级计算机“深蓝 与当 时的国际象棋世界冠军卡斯帕罗夫进行了一场大肆渲染的比赛。这次被卡斯帕罗夫称作 “终于来临的一天 的比赛以卡氏的失败而告终。i b m 公司将“深蓝 的获胜称作是 人工智能领域的一个里程碑。 许多学者认为，对于人工智能研究而言，象棋的重要作用相当于遗传学研究的果蝇。 就是说人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了 重要影响。人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握 了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任 何需要人类智能的活动中。因此对中国象棋人机博弈问题的研究意义重大。 1 1 国际象棋计算机博弈情况简述 国际象棋机器博弈的发展经历了一个很长的历史时期，回顾国际象棋计算机博弈的 漫漫征程，不禁让人闻到了弥漫的硝烟i l j 。 第一台会下国际象棋的机器实际上是1 7 9 6 年匈牙利工程师b a r o nw o l f g a n gv o n k e m p e l e n 为奥地利皇后作为消遣之用而设计的，这只是一个外形笨拙的机械装置，它 的高超水平来自于一名象棋高手巧妙的藏在这个机械装置中，所以这个会下国际象棋的 机器并不是真正意义上的机器，是由人冒充的。 3 大连交通大学工学硕士学位论文 第一个国际象棋博弈程序是在电脑被真正的发明以前写出来的，它是由有史以来最 伟大的数学家之一的阿伦图灵( a l a nt u r i n g ) 写出的，当时还没有一台机器能够执行这 些指令，于是他就根据所写的算法自己去运算，严格按照运算出来的结构去走棋，当时 每走一步棋需要半个多小时。 19 4 6 年美籍匈牙利数学家约翰冯诺依曼( j o h nv o nn e u m a n n ) 被美国军方指派设 计一台强大的计算机器用来加快工作的进度，到了1 9 5 0 年，呈现在人们面前的是一个 外形奇怪、浑身闪闪发光的庞然大物，一台名叫“埃尼阿克( e n i a c ) 的现代电子计算 机，每秒能执行1 0 0 0 0 条指令。为了试验这台机器，首先就做了一个国际象棋博弈程序， 是一个缩小的6 x 6 的棋盘，没有“相 ，当时搜索到四层深度( 双方各两步) 所需要的时 间是1 2 分钟，如果加上“相 就需要3 个小时的搜索时间了。 5 0 年代中期，“埃尼阿克( e n i a c ) 下了三局棋，第一局是自己对自己，白胜。第 二局的对手是一位让了“王后棋子的强棋手，进行了1 0 个小时的比赛，结果人类大 师胜利。第三局是机器和一位刚学一个星期下棋的年轻姑娘，结果博弈程序2 3 回合取 得胜利，这是在智力的博弈中人类首次负于电脑。 1 9 5 6 年人工智能学科在美国达特茅斯大学的国际会议上诞生，人工智能领域的学者 便开始了对人机博弈的研究。 8 0 年代中期，美国的卡内基梅隆大学开始研究世界级的国际象棋计算机程序 “深思”。 1 9 8 7 年，“深思”首次以每秒钟7 5 万步的思考速度露面，它的水平相当于拥有国际 等级分为2 4 5 0 的棋手。1 9 8 8 年，“深思”击败丹麦特级大师拉尔森。 1 9 8 9 年，“深思”已经有6 台信息处理器，每秒思考速度达2 0 0 万步，但在与世界棋 王卡斯帕罗夫进行的“人机大战”中，以o 比2 败北。 1 9 9 5 年，i b m “深蓝”更新程序，新的集成电路将其思考速度提高到每秒3 0 0 万步。 1 9 9 6 年，“深蓝”在向卡斯帕罗夫的挑战赛中，以2 比4 败北。 1 9 9 7 年，“深蓝小组经过8 年的研究开发出“更深的蓝”，它具有更加高级的“大 脑”，通过安装在r s 6 0 0 0 s 大型计算机上的2 5 6 个专用处理芯片，每秒2 亿步的计算 速度，并且存储了百年来世界顶尖棋手的1 0 亿套棋谱，并由4 名国际大师为其出谋划 策，最后“超级深蓝”以3 5 比2 5 击败了卡斯帕罗夫。卡斯帕罗夫要求重赛，但没有得 到回应。 1 9 9 9 年，“弗里茨”升级为“更弗里茨”。 2 0 0 1 年，“更弗里茨”更新了程序，击败了卡斯帕罗夫和阿南德，以及除了克拉姆尼 克之外的所有排名世界前十位的棋手。 4 第一章中国象棋计算机博弈问题的研究 2 0 0 2 年1 0 月，“更弗里茨”与克拉姆尼克在巴林进行“人机大战”，思考速度为每秒 6 0 0 万步。结果4 ：4 打成平手。 2 0 0 3 年1 2 月以色列两位著名的电脑专家阿米尔班和布申斯基研制的“更年少者” 与卡斯帕罗夫举行人机对抗，双方3 比3 战平。 2 0 0 5 年7 月国际象棋大师、英国象棋冠军迈克尔亚当斯在与超级计算机h y d r a 的 大战中以0 5 ：5 5 输给了对方。h y d r o 在这次比赛期间仅仅利用了其6 4 台p c 中的3 2 台。 h y d r a 的每台p c 都配置有一个3 0 6 g h z 的至强芯片。h y d r a 每秒钟能够计算2 亿步棋， 能够预测4 0 步棋p i 。 随着硬件和软件的发展，国际象棋的博弈水平越来越高，目前比较有名的国际象棋 软件有：z a p p a ( 第1 3 届奥赛冠军) 、j u n i o ( 第1 4 届奥赛冠军) 、c r a f t y ( 开源软件) 、f r i t z 、 s h r e d d e r 等等。 1 2 中国象棋人机博弈问题的局面综述 与国际象棋相比，面对历史更为悠久的中国象棋，其计算机博弈显得如此稚嫩。国 际象棋计算机博弈开展的要比中国象棋早很多，技术也比较成熟，参考文献也很多，而 且还有很多公开的源代码，所以发展的很快。进入8 0 年代，在世界各地也有一些学者 开展了对中国象棋计算机博弈研究，但是距离中国象棋世界冠军的差距却很远，仅仅接 近于大师水平，而且关注的学者很少，资料匮乏，形成了沉寂的计算机博弈氛围。这不 能不说是一场历史的误会，也是我们当前我们所面临的艰难局面。 专家们经过研究认为，中国象棋与国际象棋并没有什么本质上的区别，有的只是形 式上的不同，但由于中西方的历史、地理、文化背景的不同，使得两者在规则、着法上 仍然具有很大的差劓4 1 。所以应该通过对中国象棋和国际象棋的比较分析，找出中国象 棋与国际象棋的共同点和存在的差别，吸收国际象棋先进的经验和技术，比如比特棋盘， 许多国际象棋的成熟的做法我们都可以结合中国象棋的特点加以完善，为中国象棋博弈 的发展做出贡献。 近几年，在内地也涌现出一批对中国象棋人机博弈问题感兴趣的高校、单位及个人， 而且进入2 1 世纪以后，中国象棋计算机博弈的研究受到越来越多的学者的关注，并且 在很多大赛中中国象棋博弈程序都获得了多个奖项如在与张强、b 风波、柳大华等特级 象棋大师的对弈中，均取得了很好的成绩，设计象棋博弈程序的研究学者也开始逐渐增 多，推动了中国象棋人机博弈的发展。显而易见，让计算机战胜中国象棋冠军的伟大创 举决不是一两个学校或者是科研机构单独能够完成的，必须动员千千万万的计算机爱好 5 大连交通大学丁学硕十学位论文 者和一大批专家学者参加，经过较长时间的艰苦奋战才能取得这一划时代的科技成果。 在2 0 0 6 年参加“浪潮杯”全国首届计算机象棋博弈锦标赛的参赛队伍如表1 1 所示。 表1 12 0 0 6 参赛的中国象棋计算机博弈程序 t a b l e1 1t h ec h i n e s ec h e s sc o m p u t e rm a t c hp r o g r a mi n2 0 0 6c o m p e t e n c e 程序作者 地区 宝岛一号许舜钦台湾 谢谢大师p a s c a l法国 象眼竞技 黄晨北京 s h i g a ( 象棋世家) 郑明政、颜士净台湾 将神传说 雷春鸣深圳 c o n t e m p l a t i o n 千虑吴光哲、陈志昌、徐赞升、许舜钦台湾 c y c l o n e ( 象棋旋风) 陈朝阳北京 棋天大圣王骄东北入学 象棋奇兵赵明阳大陆 当然每年也会有中国象棋计算机博弈的国际奥林匹克大赛，这其中有2 0 0 3 年的世 界冠军“纵马奔流”，2 0 0 4 年的世界冠军“谢谢象棋大师”，2 0 0 5 年的世界冠军“象 棋奇兵 ，2 0 0 6 年和2 0 0 7 年的世界冠军“棋天大圣 ，还有一些有名的博弈软件如： “象棋明星 、理直气壮、“梦入神机、“象棋a b c ”等等。特别是在2 0 0 6 年，由东 北大学、清华大学等高校承办了在北京举行的“浪潮杯”全国首届中国象棋人机博弈大 赛，这些都体现了中国象棋的人机博弈的研究的受关注程度。尽管如此，中国象棋人机 博弈的研究还比国际象棋晚了几十年，并且在搜索算法等方面的研究与国际象棋相距甚 远。 中国象棋同其他棋类遍历搜索的复杂度对比见表1 2 ，表中的数字为复杂度的自然 对数值1 6 j 。 6 第一章中国象棋计算机博弈问题的研究 表1 2 几种棋类的空间复杂度及树的复杂度对比 t a b l e1 2t h ec o n t r a s to fs p a c ea n dt r e e sc o m p l e x i t yo fs e v e r a lc h e s s 棋类棋盘大小空间复杂度树的复杂度 井字棋 3 335 黑白棋8 82 85 0 国际象棋8 x 85 0 1 2 3 中国象棋1 0 95 2 1 5 0 日本将棋 9 97 l2 2 6 韩国象棋 1 0 95 21 3 8 围棋 1 9 1 91 7 24 0 0 从表1 2 中可以看出，中国象棋的状态空间复杂度和博弈复杂度都比井字棋、黑白 棋、韩国象棋和国际象棋要高，显然这是对中国学者提出的严峻挑战。 1 3 中国象棋程序的研究 面对如此富于挑战性的局面，大连交通大学软件学院计算机应用研究所于2 0 0 6 年 开始了中国象棋计算机博弈课题的研究。在认真借鉴国际象棋开发成果的基础上，不断 创新，突破了一系列的关键技术，设计开发了具有相当棋力的博弈软件系统。并于同年 的6 月份组成了代表队，在2 0 0 6 年7 月的全国首届计算机象棋博弈锦标赛中取得了新 秀奖的好成绩，并希望在2 0 0 7 年的比赛中有所突破，并在中国象棋机器博弈的领域里 开创新的局面。 在新的博弈程序中同样是由四个部分有机结合而成的：棋盘结构，局面评估，搜索 技术，其他的一些策略。其中棋盘结构中包括棋盘表示，棋子的移动，着法生成，对一 些特殊局面的判断；局面评估中一般包括固定子力值、棋子位置值、棋子灵活度值、威 胁与保护、牵制、棋子配合作战、兵的状态、将的安全，各个棋子之间关系的评估和优 化局面的评估等方面，而如何取值就大有学问【5 j ；搜索技术有很多种，但是在本文的程 序中主要应用的是完全搜索技术，静态搜索，启发式规则，裁剪策略，置换表和并行处 理，经过一系列的改进，将这些搜索结合在一起，来提高搜索的效率和象棋程序的棋力； 还有一些其他的策略应用到其中，比如：开局库、残局库后台思考、时间策略、引擎的 协议等等，让这些策略与整个系统配合起来。 7 大连交通大学_ t 学硕士学位论文 本文象棋博弈程序的主要特点包括快速的数据结构生成设计、具有一定的知识自学 习能力、新的高效率的搜索，并且在开局库中引入了一种新的评估函数，放弃了原来只 查询当前局面的开局库执行方式，使得权重和自学习更容易设计。这些机制保证了博弈 系统在开局时节省了大量的时间：提高了中局的搜索时间；在应用大量领域知识的同时 能保持高速的搜索速度与深度，做到知识与速度的均衡。 本章小结 本章主要阐述了国际象棋和中国象棋人机博弈问题的国内外研究现状以及该研究 课题的意义，通过对国际象棋软件的研究提升中国象棋软件的水平，使中国象棋水平进 一步的提高。并简要的阐述了本人开发的象棋程序的模块构成以及目前的研究情况。 8 第二章中国象棋程序博弈树算法的研究 第二章中国象棋程序博弈树算法的研究 搜索 7 1 算法是象棋程序的核心算法，同时也是人工智能领域普遍存在的问题。实际 上一个好的程序可以只依靠棋盘局面和很好的硬件来确定哪一方处于领先以及领先多 少，并且制定作战计划让这个优势变为胜果。但是需要考虑的局面类型太多了，再加上 那么多的规则和特例，就是再好的程序也不能满足这种要求，况且硬件仅仅是物质基础， 再好的硬件也无法实现“象棋不败算法【引。于是搜索策略与搜索引擎就显得尤为重要。 如何在成指数递增的状态空间中寻求最优解，是人工智能研究的一个重要的方向。 几乎所有的棋类问题，都可以用博弈树来描述。博弈树是把计算机和用户所有可能 走法和局面罗列出来的一颗树。因为完全建立博弈树是不可能的，所以如何在计算机处 理能力允许的条件下，尽可能地搜索更深的层数，这也就是计算机博弈中搜索引擎研究 的重点。只要计算机搜索的足够深，就会看到杀着，使自己处于最优的局面。因此，搜 索得越深，计算机就会施展越复杂的对弈计划。 当然并不是说博弈树需要遍历它的每一个节点来取得当前评估函数下最优的节点， 经过选择和剪枝，博弈树的规模可以大大的缩小，也就是各种搜索算法的共同目标。搜 索算法做的越好，搜索的深度也就越深，搜索的速度也就越快，这是衡量博弈程序的水 平高低的一个重要方面。 2 1 搜索算法的分类 象棋程序的搜索算法都是基于“最小一最大”策略的，因此衍生出以a l p h a - b e t a 为基 础的完全搜索算法以及带裁剪的搜索算法。如今，“带置换表的启发式a l p h a b e t a 搜索” 成了象棋程序的主流，这种思想强调对着法排序的重要性，排序着法是由“启 发”( h e u r i s t i c ) 算法来完成的，它同“置换表”( t r a n s p o s i t i o nt a b l e ) 一起，使搜索效率有大 幅度的提高。 搜索算法大致可以分为以下四类： ( 1 ) 完全搜索算法，即a l p h a b e t a 搜索及其变种，诸如期望窗口、p v s 、m t d ( f ) 等； ( 2 ) 启发算法，对着法顺序进行优化，尽可能地提高a l p h a - b e t a 搜索的效率，中国 象棋中的启发算法有置换表启发、吃子启发、杀手着法启发和历史表启发等； ( 3 ) 裁剪算法【91 0 l ，运用棋类知识略去对某些着法的搜索，以提高搜索深度，中国象 棋中最常用的裁剪算法是空着裁剪，当然还有其他方法。 9 大连交通大学t 学硕+ 学位论文 ( 4 ) 置换表，其初衷是利用置换现象来减少搜索( 即置换裁剪，属于裁剪算法的范 畴) ，然而在象棋的中局阶段，置换现象并不那么普遍，因此它的主要功效在于启发( 即 置换表启发，属于启发算法的范畴) 。 以上几种搜索算法都是由基本搜索和高级搜索所组成的，基本搜索和高级搜索的结 合形成了当前高水平的中国象棋程序，它尽可能剪掉博弈树中没有搜索价值的节点，在 相同的时间内搜索到更深的层数，从而提高象棋程序的博弈水平。 下面简要的介绍一下本文开发的象棋程序搜索引擎所用到的搜索算法： 2 2 基本搜索算法 ( 1 ) 极大极小值算法 在搜索过程中，一般是使用一个评估函数，对每个格局( 即博弈树中的节点) 进行“估 值”，假设评估函返回值越大，表示对电脑走棋越有利，那么，电脑在走下一步棋时，只要 搜索出估价函数值最大的局面即可。当然对手走棋会选函数值低的局面，这样非终端结 点的函数值就由其下层结点的这种最大最小交替递归调用得到，称为极大极小算法搜索 算法。 极大极小值搜索属于完全搜索，在最大最小树搜索的过程中相当一部分结点的搜索 并不会影响最终搜索树的值，因此采用这种搜索方法的搜索引擎的搜索效率非常低。“蛮 力搜索【l6 】”肯定是不可取的，而应进行有选择的搜索。主动放弃那些没有意义的分支( 剪 枝) ，不会遗漏存在最优解可能的节点，并在最有希望的方向上局部加深，这便是最基 本的搜索策略【1 1 1 。目前国际象棋的搜索引擎不下百余种，而且仍然是博弈学者们研究的 焦点。 ( 2 ) 负极大值算法 普通的极大极小值算法看起来有一点笨拙，因为我们总要检查哪一方要取极大值而 哪一方要取极小值，以执行不同的操作，出于这样的原因k n u t h 和m o o r e 在1 9 7 5 年提 出了负极大值的方法【1 2 1 ，消除了两方的差别，使博弈的双方都取极大值。 负极大值的算法伪代码如下： 1 0 第二章中国象棋程序博弈树算法的研究 实际上负极大值算法和极大极小值算法在原理上是完全等效的。但是负极大值更容 易被使用，是一种很好的表达方式，今天的博弈程序大多采用的都是负极大值形式的搜 索算法，本文也不例外。 极大极小值算法和负极大值算法是是所有搜索算法的基础，而所有剪枝算法的基础 却是a l p h a b e t a 搜索。 ( 3 ) a l p h a - b e t a 搜索剪枝算法 在极大极小和负极大值的搜索过程中存在这一定的数据冗余，这就需要通过剪枝算 法对大量的不影响结果的冗余节点抛弃，所有剪枝算法的基础都是a l p h a b e t a 搜索【1 3 j 。 口一剪枝的示意图如下： ( a ) a l p h a 剪枝 ( b ) b e 协剪枝 图2 1a l p h a 剪枝和b e t a 剪枝 f i g 2 1a l p h aa n db e t ap r u n i n ga l g o r i t h m 上图中圆圈代表的是取极小值，正方形代表的是取极大值。 岱一剪枝的原则归纳为以下两个部分： a l p h a 剪枝：a l p h a 剪枝是基于取极大值的父节点而言的。 大连交通大学t 学硕+ 学位论文 如图2 1 ( a ) 所示，因为采用深度优先搜索，所以b 点的值首先得到，此时必有a = b ， 如果在c 的子节点中d _ b ，则说明c = d = b ，则e 、f 都应该避免搜索。即b e t a 是对于对手来说最坏的值。 由上面的介绍可以看出，a l p h a - b e t a 搜索对节点的搜索顺序非常敏感，为了衡量基 于a l p h a b e t a 搜索算法的各种优化算法的优劣，引入两个相关的概念：极小树和极大树。 极小树( m i n i m a lg a m et r e e ) ： 极小树是a l p h a - b e t a 搜索在理论上的最优情况，它假定展开每一个节点时，第一个 访问的节点总是最佳的。极小树在数学角度上看是很有意义的，它表示搜索树的最小规 模。 极大树( f u l lm i n i m a xt r e e ) ： 极大树是a l p h a - b e t a 搜索理论上的最差情况，它假定在展开每一个节点时，最佳的 节点总是最后被发现。 在使用a l p h a b e t a 搜索的时候，一般采用a l p h a 作为期望得到的搜索值的下界，b e t a 作为其上界。这样，就可以根据上界和下界剪掉那些不能影响树的结果的走法，这时区 间( a l p h a , b e t a ) 就可以认为是一个窗e l ，我们假设搜索值的期望值在这个窗口之内l l 训。 如果某个着法的结果小于或等于a l p h a ，那么它就是很差的着法，因此可以抛弃。 因为局面对走棋的一方来说是以a l p h a 为评价的。同时如果某个着法的结果大于或等于 b e t a ，那么整个节点就废除了，因为对手不希望走到这个局面，而它有别的着法可以避 免到达这个局面。因此如果我们找到的评价大于或等于b e t a ，就证明了这个结点是不会 发生的，因此剩下的合理着法没有必要再搜索。这也同时意味着对搜索同一棵树来说， a l p h a - b e t a 搜索所花费的时间远远少于极大极小算法所花费的时间。 口一剪枝算法的伪代码如下： 1 2 第二章中国象棋程序博弈树算法的研究 ( 4 ) 其他基本搜索算法 在基本的搜索算法中，一切算法的原理基础都是极大极小值算法、负极大值算法和 口一剪枝算法，在本象棋博弈软件中还应用到的基本搜索算法如：p v s 搜索、静寂搜 索和n u l lm o v e 剪枝算法【”】。 p v s 搜索实际是提高“口一”算法效率的一种方法，在a l p h a - b e t a 搜索中，任何 结点都属于以下三种类型： a l p h a 结点； b e t a 结点； p v 结点。有一个或多个着法会返回大于或等于a l p h a 的值( 即p v 着法) ，但是没有 着法会返回大于或等于b e t a 的值。 p v s 搜索假设：如果在搜索一个节点时找到一个p v 着法，那么就得到p v 结点。 也就是说假设着法排序已经足够好了，不必在其余的着法中找更好的p v 着法或者高出 边界的着法( 这就会使结点变成b e t a 结点) 。当找到一个着法其值在a l p h a 和b e t a 之间， 那么对其余的着法，搜索的目标就是证明它们都是坏的着法。跟要搜索出更好的着法相 比，这种搜索也许要快一些。 如果这个算法发现判断是错的，即其中一个后续着法比第一个p v 着法好，那么它 会被再一次搜索，这次使用正常的a l p h a - b e t a 搜索方法。如果这种情况发生了，这样就 浪费时间了，但是不会浪费很多的时间。 静寂搜索( q u i e s c e n c es e a r c h ) 算法的思想是在叶子节点振荡剧烈( 有吃子现象出 现) 时，不调用评估函数，而是继续向下搜索，直到局面平静下来为止。这个函数也对 大连交通大学下学硕十学位论文 局面作评价，只是避免了在明显有对策的情况下走出缓着。简而言之，静态搜索就是应 对可能的动态局面的搜索。 该算法的伪代码如下： 这个搜索算法有几个可能的结果：可能评价函数会返回足够高的数值，使得函数通 过b e t a 截断马上返回；也可能因为某个吃子而产生b e t a 截断；可能静态评价比较坏， 而任何吃子着法也不会更好；或者可能任何吃子的走法都不好，但静态评价只比a l p h a 高一点。 注意这里静态搜索中没有传递“d e p t h ”这个参数。正因为如此，如果找到好的吃子， 或者有一系列连续的强制性吃子的着法，那么搜索可能会非常深。 n u l l m o v e 剪枝算法是由1 9 9 3 年c h r i l l yd o n n i n g e r 1 7 j 在i c c a 杂志上首先提出的， 它是前置剪枝搜索中最著名的算法。它可以在不过多地影响搜索准确性的前提下，大大 缩小搜索的层数。它运用可能忽视重要路线的冒险策略， 1 4 第二章中国象棋程序博弈树算法的研究 n u l lm o v e 算法的基本思想是，假设对手连走两步，如果本方在浅层的搜索中仍旧 具有良好表现( 产生b e t a 剪枝) ，那么就不需要进行完全深度的搜索了。 该算法的伪代码如下： 对于其中r 的值来说，r 的值一般取2 ，这样做比较安全。如果想让搜索变得更快， 有些引擎也令r 的值为3 ，但是危险性也很大。现在比较流行的是r 做自适应变化。 n u l l m o v e 剪枝的一个问题是：在一条分枝上可以多次使用n u l lm o v e 搜索，但是不 能连续使用，中间必须间隔一层正常的搜索。也可以在一个实在着法之前，允许连续两 个n u l lm o v e 裁剪 n u l l m o v e 剪枝的另一个问题在于它会导致“搜索的不稳定性”。n u l l m o v e 搜索的 成功与否取决于b e t a 的值。这个结点下次访问时，b e t a 可能不同，因此搜索会有不同 的值，这是很不合理的。但是在实战中，比起遇到偶然的对策错误，以及搜索不稳定性 的增加来说，搜索速度的加快重要得多，总的来说会减少2 0 到7 5 的搜索时间。 2 3 高级搜索算法 在博弈系统的搜索引擎中，还应用到了一些相对高级的搜索算法进行优化和改进， 用来提高搜索水平和节省搜索的时间，以达到搜索的最优化。 ( 1 ) 历史启发 在搜索的过程中，一些以前经过搜索认为最佳的走法，在相差不大的局面下，仍然 有很大可能成为最优的走法。而且，某个走法被证明是最佳的次数越多，成为当前局面 最佳的可能性也就越大。所以我们可以通过一些复杂的判断来找出这些相似的局面，率 先搜索，从而提高剪枝效率。 大连交通人学： 学硕十学位论文 j s c h a e f f e r 第一次明确阐述了历史启发的概念【l 引。历史启发实际上就是记录搜索过 的好的走法，包括两种情况： 由其产生的节点引发了剪枝； 由其产生的节点未引发剪枝，但是其兄弟走法中的最佳者； 但是需要注意的是上述的定义并未将好的走法仅定义为最佳者，一个引发剪枝的节 点可以使该节点的后继免于搜索。因此首先搜索该节点将加快搜索速度。 历史启发的定义如下： h i s t o r y v a l u eh i s t o r y t a b l e 【9 0 11 9 0 ； 第一维坐标表示走法的起始位置，第二维坐标表示走法的终止位置，存储的数据类 型为h i s t o r y v a l u e ，表示走法的打分，该数据也是历史启发对走法排序的依据。 使用了历史启发的a l p h a b e t a 搜索在遍历的节点数目上和时间的花费上均远远的小 于单纯的a l p h a - b e t a 搜索，而且这一差距随着深度的增加而增加。 ( 2 ) 杀手启发 在搜索过程中，有许多的走法一经搜索就发生了剪枝。这些常常是同一走法。杀手 启发的方法是为每一层记录引发剪枝最多的走法( 杀手) 。当下一次搜索到同样的深度 时，如果杀手是该局面的一个合法的走步的话，就可以把杀手走法找出来先搜索。 假设m o v e 表示象棋走法，那么杀手走法可以定义如下： c h e s s m o v e k i l l e r d e p t h ； 其中d e p t h 表示层数，该数组元素类型为c h e s s m o v e ，表示走法。 显然，杀手启发是一种特殊的历史启发，它不依赖于人类的知识，具有普遍性【l9 1 ， 或许我们把它叫做历史启发的简化版。使用杀手启发来代替历史启发调整节点顺序，是 一种可行的手段。 ( 3 ) 迭代深化 迭代深化最初是作为控制时间的机制而提出的【2 0 1 ，它能够根据搜索所需要的时问选 择搜索深度。对于搜索引擎来说，局面的复杂程度对搜索深度的影响很大。同样的搜索 深度下，开局和中局耗费的时间比较长，残局来说比较短。如果一直保持固定的搜索深 度，对残局来说是种浪费，但是深度过大，可能使开局和中局搜索时间过长。迭代深化 很好地解决了这个问题。 迭代深化的做法是先搜索第一层，如果没到时间，再搜索第二层，以此类推，直到 到达规定时间。迭代深化并不只是简单地搜索，还对置换表、历史启发等写入了启发信 息，这次迭代对下次迭代的搜索顺序做了大量的铺垫工作，所以迭代深化的效率要比不 用迭代好得多。 1 6 第二章中国象棋程序博齐树算法的研究 伪代码表达如下： 几乎所有高水平的博弈程序都采用迭代深化作为调整节点顺序、改进搜索效率的重 要手段，而且