（计算机应用技术专业论文）一种新的博弈树搜索算法及其应用研究.pdf

一种新的博弈树搜索算法及其应用研究 中文提要 中文提要 机器博弈是人工智能研究领域的一大热点，博弈树搜索则是机器博弈的引擎。本 文在博弈树搜索算法和博弈树优化技术等方面做了深入研究，将理论和实践紧密结 合，取得了以下的主要创新成果： ， ( 1 ) 提出并成功验证了一种新的博弈树搜索算法：基于广度优先的接力式空窗探测搜 索算法。实验证实该方法在实际应用中的平均搜索效率，高于目前公认搜索效率最高、 也是最流行的p v s 和m t d ( f ) 搜索方法；在迭代深化搜索中，该方法也具有相对优势； 并且该算法的最小搜索极限小于极小树。因此，该方法具有广阔的应用前景。 ( 2 ) 给出了一种新的博弈树优化技术一“子树复用 技术。该技术在几乎不需要额外 时间开销的情况下，就能使深层博弈树搜索的效率提高1 0 以上，并随着搜索深度的 加大，效率提高得愈多。“子树复用 技术在限定用时或必胜局面的对弈中还具有额 外的实用价值，因而“子树复用 技术无疑具有极好的应用价值。 ( 3 ) 给出了极小搜索树叶结点数定理的新的证明方法，指出了以前的有关证明：的缺陷。 针对很多人对极小树的不准确理解，以及对窗口搜索效率的有关误解，给出了正确的 结论o ( 4 ) 开发了高水平的五子棋人机对弈系统，该系统在估值函数设计上，探索了不同颗 粒度估值函数的应用效果，证实粗颗粒度估值函数在深度搜索中可以具有更好的综合 效果；部分局面下的估值函数延伸评估技巧，同样可以替代搜索，来减少地平线效应； 这些为同行提供了很好的借鉴。证实借助棋类知识的走法生成函数，在五子棋对弈系 统中具有很好的效果。在博弈树优化方面，挖掘出极小极大值搜索算法的优势，应用 收到了良好的效果。 关键词：博弈树：p v s 搜索；m t d ( f ) 搜索；极小树；空窗探测；迭代深化；五子棋 作者：张明亮 导师：李凡长 al l e wg a m e - t r e es e a r c ha l g o r i t h ma n di t sa p p l i c a t i o nr e s e a r c h a b s t r a c t c o m p u t e rg a m ei sav e r yp o p u l a rf i e l di na i , g a m e - t r e es e a r c hi st h ek e yc o r eo f c o m p u t e rg a m e t h i sp a p e rg i v e sp r o f o u n dr e s e a r c hi sg a m e - t r e es e a r c hm g o f i t h ma n d 。野l 矗l e 疵e “：o p t i m i z a t i o n t e c h n i q u e , t h e a u t h o r c o m b i n e s t h e o r ya n d + p r a c t i c e p r e s e n t st h e f o l l o w i n g r e s u l t s ： 、 ( 1 ) i tp u t sf o r w a r dan e wg a m e - t r e es e a r c hm g o f i t h m sw h i c hb a s e do nb r e a d t h - f i r s t c o n t i n u o u s l yn u l l - w i n d o wt e s tm e t h o d e x p e r i m e n t sh a v ep r o v e dt h a tt h ee f f i c i e n c yo ft h i s a l g o r i t h mo u t - p e r f o r m st h ep o p u l a ra l g o r i t h m ss u c ha sp v sa n dm t d ( ow h i c ha r c c o n s i d e r e da sh a v i n gm o s th i g he f f i c i e n c i e s t h en e wm e t h o da l s oh a ss o m ea d v a n t a g e si n i t e r a t i v e - d e e p e n i n gs e a r c h ，a n dt h es e a r c hl i m i to ft h i sa l g o r i t h mi s _ s m a l l e rt h a nm i n i m a l g a m e - t r e e t h u sa w i d ea p p f i c a t i o nc a nb ep r o m i s e db yt h i sa l g o r i t h m ( 2 ) i tg i v e san e wt e c h n i q u eo fo p t i m i z i n gg a m et r e e ：s u b - g a m e - t r e ei u s e t h i st e c h n i q u e c a n i m p r o v ed e e ps e a r c he f f i c i e n c yb y1 0p e r c e n ta n dm o r ew i t hd e e p e rd e p t hb u tn oe x t r a e x p e n d i t u r e 。t h es u b g a m e - t r e er e u s et e c h n i q u eh a sa d d e de f f e c ti nl i m i tt i m eg a m eo r m u s tv i c t o r yp h a s e o f c o u r s e ，i th a sab e t t e ra p p l i c a t i o nv a l u e ( 3 ) i tg i v e san e wp r o o fo ft h et h e o r ya b o u tt h en u m b e rb o t t o m - n o d e so fm i n i i 脚 g a m e - t r e e ，a n dp o i n t so u tt h ed e f i c i e n c yo fo l dm e t h o d i ta l s oc l a r i f i e st h e m i s u n d e r s t a n d i n gc o n c e p t so fm i n i m a lt r e ea n dw i n d o ws e a r c h i n ge f f i c i e n c ya n dg i v e st h e c o r r e c tc o n c l u s i o n ( 4 ) i nt h i sp a p e ra h i 曲l e v e lh u m a n - m a c h i n ep l a y i n gg o b a n gs y s t e mi sd e v e l o p e d ，a n dt h e a u t h o rp r o v e st h a tb yu s i n ge v a l u a t i o nf u n c t i o no f r o u g hv a l u et h eb e t t e rw h o l ee f f e c ti n d e p t hs e a r c h i n gc a na c q u i r e ，a n dt h ee x t e n d i n ge v a l u a t i n gt e c h n i q u eo ft h ee v a l u a t i o n f u n c t i o na l s oc a l lr e d u c et h eh o r i z o ne f f e c t t h ea u t h o ra l s ot e s t i f i e st h a tw i t ht h eh e l po f p l a y i n gg o b a n gk n o w l e d g e ，t h em o v e - g e n e r a t i o nf u n c t i o nc a l lp r o d u c eg o o dr e s u l t si n h u m a n - c o m p u t e rp l a yg o b a n gs y s t e m t h ea u t h o ra l s oe x t e n d su s eo fi n i n i m a xs e a r c h a l g o r i t h mi nt h eo p t i m i z i n gg a m e - t r e ea r e aa n da c h i e v e sg o o dr e s u l t w i t ha l lt h e s ei d e a s a n d e x p e r i m e n t s ，t h ep a p e rp r o v i d e sag o o dr e f e r e n c et of e l l o wr e s e a r c h e r s k e yw o r d s ：g a m e - t r e e ；p v s ；m t d ( o ；m i n i m a lt r e e ；n u l l - w i n d o wt e s t ；i t e m t i v e - d e e p e n i n g ； g o b a n g w r i t t e n b yz h a n gm i n g l i n g s u p e r v i s e db yl if a n z h a n g 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：荭塑! 主扫 学位论文使用授权声明 期：砌7 j 修 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究量主名：丝幽耄日 导师签 期：秒7 儿廖 一种新的博弈树搜索算法及其应用研究第一章博弈树搜索算法的历史与现状 第一章博弈树搜索算法的历史与现状 1 1 机器博弈的简史与重要意义 机器博弈是人工智能研究中最活跃的领域，研究各种博弈及其机器实现的规律。 双入、“零和”、完备知识博弈则一直是机器博弈的主要研究领域，多以计算机下棋为 例研究其规律。事实上，早在人工智能成为一门独立的学科之前，人们就已经进行了 机器博弈的理论研究和实践。上世纪2 0 年代，j o h nv o nn e u m a n n ( 冯诺依曼) 和e m i l e b o r e l 分别提出了双人零和博弈的极小极大值定理【据文献1 ，2 ，3 ，4 】，1 9 4 4 年，在j o h n v o nn e u m a n n 和o s k a rm o r g e n s t e r n 合著的( t h e o r yo fg a m e sa n de c o n o m i cb e h a v i o r ) ) 中，给出了极小极大值定理完整的论述【据文献l ，2 】，为机器博弈创立了相应的数学 理论。1 9 世纪4 0 年代，a l a nt u r i n g 在电子计算机出现之前，就编写了计算机下棋的 程序来迎接计算机的诞生，他甚至饶有趣味地自己来模拟程序的搜索过程与人进行对 弈。电子计算机出现后的1 9 世纪4 0 年代末，由于计算机下棋的趣味性和挑战性，吸 引了众多人投入到计算机下棋的研究中，如j o h nv o nn e u m a n n 用一个简单的下棋程 序来检验m a n i a c 计算机的指令系统。c l a u d es h a n n o n 尝试将选择和排除策略引入 到他的计算机下棋程序中，可以说是剪枝搜索的雏形。他在1 9 5 0 年发表的 “p r o g r a m m i n gac o m p u t e rf o rp l a y i n gc h e s s 和“ac h e s s - p l a y i n gm a c h i n e ”对早期 的机器博弈有重要影响。h e r b e r ts i m o n ，a l a nn e w e l l 和s h a w 在1 9 5 8 年确认了浅层 a l p h a - b e t a 搜索算法【1 】，对后来的计算机弈棋产生了深远的影响。以及b e r n s t e i n 等人 的早期计算机国际象棋程序等。而人工智能( a r t i f i c i a li n t e l l i g e n c e ) 概念的提出则是到 1 9 5 6 年夏季，在达特茅斯学院举行的“人工智能”夏季研究会，期间有“人工智能 之父 之称的j o h nm c c a r t h y 首次正式提出，m c c a r t h y 并在后来发明了适用于人工智 能的n s p 计算机语言。 计算机弈棋为人类提供了一个很好人工智能的试验场所，a l e x a n d e rk r o n r o d 将国 际象棋的计算机弈棋研究比喻为人工智能的果蝇。由于计算机下棋的基础理论研究和 应用实践有着完美的结合，有众多的计算机专业人员从事研究和开发，通过人们几十 年的努力，率先取得了突破性的成果。在1 9 9 7 年，由多位专家和国际大师合作，历 经8 年设计出的m m “深蓝 计算机国际象棋人机对弈系统( 其硬件是专门设计的， 第一章博弈树搜索算法的历史与现状 一种新的博弈树搜索算法及其应用研究 采用了并行技术) ，击败了当时公认的国际象棋第一人卡斯帕罗夫，更是轰动了全世 界，彻底打破了计算机下棋不可能战胜人类的说法。到目前为止，多数棋类游戏的计 算机弈棋水平已经超越了人类，如国际象棋、中国象棋、跳棋、黑白棋、奥赛罗棋等 等。只剩下少数的几种棋类游戏还处于人类占上风的态势，如五子棋、围棋等。_ 般 认为，- 围棋可能是人类坚守阵地最长的棋类游戏，短时间内，计算机的围棋水平还难 以威胁到专业棋手。 机器博弈的研究早已不是待在实验室的科学家们的自娱自乐行为，几十年的研究 衍生了大量的研究成果，这些研究成果对更广泛的领域产生了非常重要的影响，如经 济管理、航空调度、天气预报、资源勘探、生物进化、工程管理、文化娱乐、军事博 弈、金融调控、+ 商业竞争等领域。 1 2 机器博弈系统的基本组成 双人、“零和 、完备知识的计算机下棋系统可以划分为四大组成部分：知识表 示、走法生成、估值函数和博弈树搜索。 知识表示部分包括棋局的表示与实现，开局库和残局库等知识库，以及整个对弈 系统的数据结构等，是对弈系统的基础。高效率的存储与表示技术是其主要的研究方 向，如国际象棋的“比特棋盘 ( b i tb o a r d s ) 表示技术，由于国际象棋为8 x8 ，其存储 和处理的基本单位按“位( b i t ) 进行，处理效率就能成倍地提高。 走法生成函数根据对弈规则等找出合法的招法，走法生成函数还可以结合相应的 棋类知识来进一步筛选出更合理的走法，并对走法序列进行优化排序，来提高博弈树 搜索效率。不同种类游戏的对弈系统，走法生成函数的设计实现差异很大。 估值函数用来对局面进行评估，给出个恰当的数值来反映局面的优劣，多数情 况下评估值使用整数值，一般情况下估值函数不是直接用来对当前局面进行评估，而 是根据博弈树的展开，在假设的双方若干步走法之后形成的局面，调用估值函数进行 局面评估。由于众多棋类游戏的博弈树异常庞大，不可能完全展开，只能展开到一定 深度，然后使用估值函数进行评判，评估的速度和精确性对博弈树的搜索效率有直接 的影响。由于速度和准确性是在一定程度上相互矛盾的，对系统的影响也非常大，因 此估值函数的设计实现是高水平对弈系统的一个重点。 博弈树搜索则是对弈系统的中枢。将对弈双方可能的走法进行展开，所构成的树 一种新的博弈树搜索算法及其应用研究第一章博弃树搜索算法的历史与现状 型结构，简称为博弈树，博弈树还有一个隐含的内容，就是整个树的求解依据极小极 大值定理进行，关于这方面内容在下面介绍j 通过对整个博弈树的搜索( 遍历) ，来找 出当前局面下对弈一方的最佳走法，称为博弈树搜索。博弈树搜索到叶结点( 所展开 的博弈树的最末层结点) ，需使用估值函数来得到局面估值，博弈树搜索的过程就是 计绰机“思考 过程，搜索的结果反映了对弈系统的智能，即对弈系统的棋力水平。 对于人类，思考得越深远，判断就越准确，计算机的博弈树搜索也是同样道理，博弈 树搜索层数越多，搜索的结果越准确可靠。计算机弈棋的水平主要决定于这里的博弈 树搜索深度，理论上，没有时间限制的搜索可以找到博弈的最佳解，实际的博弈则要 在合理的时间内确定招法。因此，博弈树搜索深度必然受具体的软硬件环境和时间制 约。对于搜索深度与棋力的关系，以国际象棋为例，西方学者比较一致的看法是，1 4 层深度( 双方各走7 步) 博弈树搜索的棋力大致相当于2 8 0 0 等级分，这是极少数顶尖 专业棋手才能达到的等级分。专业棋手的计算深度一般也不过十几层( 即推算十几步 以后的结局，来决定当前的走法) ，但与计算机不同，计算机可以几无遗漏地准确判 断出十几步以后的局面，人的计算则有极强的选择性，且会多有漏算。由于搜索深度 是制约计算机棋力的一个瓶颈，搜索算法的研究，就成为半个世纪以来计算机下棋的 主要研究领域。 。x “ - 1 3 极小极大值算法 ：j 早在电子计算机出现以前，很多数学家就对博弈进行了理论研究，并首先建立了 双人、“零和 、完备知识博弈的数学求解方法一极小极大值算法定理( m i n i m a x a l g o r i t h m t h e o r y ) 。极小极大值算法的雏形据文献【3 】介绍，可以追溯到1 7 1 3 年，j a m e w a l d e g r a v e 在研究纸牌游戏时提出过类似思想。在2 0 世纪2 0 年代，e m i l eb o r e l 首先 重新发现了极小极大值算法【据文献1 ，3 ，4 】。极小极大值算法定理的证明则由j o h nv o n n e u m a n n 在1 9 2 8 给出。之后到1 9 4 4 年，在j o h ny o nn e u m a r m 和o s k a rm o r g e n s t e r n 合 著的t h e o r yo fg a m e sa n de c o n o m i cb e h a v i o r ) 中最终给出了完整的论述，标志着博 弈论的正式创立。此外，h e r m a n nw e y l 在1 9 5 0 年给出了极小极大值定理更为简洁的 证明【3 ，4 】。 双人零和完备知识博弈的“双人 指参与博弈的只有对抗性的双方，并不是只限 于两个人，一方内部利益完全一致，相当于一个人，双方交错进行。“零和”指参与 第一章博弈树搜索算法的历史与现状一种新的博弈树搜索算法及其应用研究 博弈的双方，一方的获益严格地等于另一方的损失，、双方的收益之和为零。完备知识 博弈是指对弈双方在任何时候都完全清楚对方的情况，对规则的理解完全相同，对结 果的评价亦相同。由于双人零和完备知识博弈在数学上是可以完全求解的，且众多的 博弈游戏符合以上特征，因此成为机器博弈中的“宠儿一，一直是机器博弈的重点研 ：究领域。闺1 1 ，就是一个针对双人零和完备知识博弈的博弈树，提取其数学要素抽象 表示博弈的一方进行决策时，用极小极大值算法进行决策的过程。 图1 1 极小极大值算法和a l p h a - b e t a 剪枝原理示意图 图1 1 为每个结点仅有2 个子结点的、深度为4 的博弈树，其中的叶结点如果不 是自然终结结点，可由估值函数给出评估值( 现假设是准确的) ，用来形象地表示己方 在( 双方交替选择到达) 该叶结点时的收益，也可以看作是对方的损失。用极小极大值 算法从叶结点向上，“口 表示的结点取其子结点中的极大值，也称为m a x 结点；“0 表示的结点取其子结点中的极小值，也称为m i n 结点；由叶结点层层递推可得到根 结点的值为1 0 ，来自于其左子结点。这个求解过程表明当前决策方应该选择一层左 子结点的招法，能保证获得最不坏的收益1 0 ，在双方都是理智决策的前提下，这也 就是博弈树的最终解。对于到达叶结点层的路径，常用杜威的十进制表示法【据文献 1 】，如图1 一l 中所得到的求解路径可表示为1 1 1 2 ，表示第一层己方选择第一个结点， 第二层对方将理智地选择第一个结点，第三层己方继续选择第一个结点，第四层对方 将理智地选择第2 个结点。如果对方在此过程中进行了非理智的选择，己方的收益将 保证1 0 。博弈树的求解路径也称为最不坏收益路径，其含义也正在于此。 极小极大值定理表明，对于在有限回合内结束的双人零和完备知识博弈游戏，用 数学方法是可以完美求解的。 一种新的博弈树搜索算法及其应用研究 第一章博弈树搜索算法的历史与现状 ：1 9 7 5 年，d o n a l de k n u t h ( 高德纳) 和r o n a l dw m o o r e 在文献【l 】中，给出了极小 极大值算法的另外一种描述形式一一负极大值算法。即：不论是m a x 结点，还是m 矾 结点；均取其子结点的负的极大值。极小极大值算法和负极大值算法在数学上是完全 等价的，只是后者的描述更美观、和谐、统一，因而很多文献乐于使用负极大值描述， 但从应用和易于理解的角度看，极小极大值算法更好一些。 主，利用极小极大值算法，结合停留在有限深度上的博弈树，用估值函数给出叶结点 的估值，就找到了让计算机进行博弈树搜索、决策的一个方法，这就是计算机下棋的 基本原理。j o h nv o i in e u m a n n 在其早期论述中，终端结点的取值只有1 、0 和- 1 ，代 表胜、和、负【2 】。而实际的计算机博弈树构造中，就如图1 一l 所是，利用极小极大值 定理，完成搜索，但结点的值可以是灵活的，一般给出一个整数值，代表一定的收益， 再用“+ ( 实际可用计算机能表示的极大值来表示) 代表获得全部收益，“一”代表 没有任何收益，这就为非完整博弈树的求解( 搜索) 扫清了障碍。 1 4 a l p h a - b e t a 搜索 2 0 世纪5 0 年代，计算机下棋的研究就异常活跃。在5 0 年代后期的计算机下棋研 究申，按照极小极大值算法进行博弈树搜索时，人们又逐步发现存在剪枝算法。据文 献 1 1 3 0 3 页介绍，剪枝的思想可追溯到1 9 5 6 年在达特茅斯学院举行的“人工智能 夏季研究会，会议期间j o h l lm c c a r t h y 在对b e r n s t e i n 的计算机国际象棋程序的评论中 首次提出。“a l p h a - b e t a ”搜索剪枝的名称也来自于m c c a r t h y 后来的论述，简称为q 一1 3 剪枝或a 1 3 搜索。q 一1 3 剪枝又分为浅层q b 剪枝和深层q 一1 3 剪枝，还可以再具 体分成q 剪枝和b 剪枝。h a s i m o n , a n e w e u 和j c s h a w 在1 9 5 8 年正式确认了浅 层a l p h a - b e t a 搜索算法。最早详述“深层a l p h a - b e t a 剪枝 方法的公开文献为1 9 6 3 年 苏联b r u d n o 的文献【5 】。 剪枝的原理虽然并不艰深，但清晰的直接描述难以做到，因而，几乎所有文献都 借助图示的方式加以叙述，本文亦用此方式描述。q 一1 3 剪枝的原理这里继续借助图 1 1 进行说明，设从底层向上的逆推按从左至右的方向进行。浅层a l p h a - b e t a 剪枝， 如图1 1 中s 结点的左子结点的值已求出为l o ，则s 1 0 为已知，在搜索了p 结点 的左子结点5 之后，已知p - - 5 ，此时p 结点已不可能对s 结点有贡献，可放弃对p 结 点剩余子结点的搜索。这种不影响正确求解的前提下，截去某些分枝的做法，称为剪 第一章博弈树搜索算法的历史与现状一种新的博弈树搜索算法及其应用研究 枝。、剪枝是在搜索进行过程中，通过合理的判断来完成的。上例可称为浅层a 剪枝。 浅层b 剪枝可见t 结点的剪枝示意。深层a l p h a - b e t a 剪枝的原理亦相仿，只是稍微难 理解一些，如已得出根结点r 的左子结点值为1 0 ，则r 1 0 为己知；再搜索到q 结 点的左子结点3 后，已知q = 3 ，而q 结点对r 结点能有贡献的前提是q 结点的值必 须 1 0 ，因此，再搜索q 结点的其余子结点已无必要。这可称为深层a 剪枝。对于 ，深层t p 剪枝( 最快将在第5 层出现) ，情况类似，不再赘述。深层a l p h a - b e t a 剪枝还可 以出现在更深层。7 用a l p h a - b e t a 剪枝算法的从左至右求解过程参见图1 - 1 所示，用双斜线标注的被 剪分支为浅层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 剪枝可以共同作用于某些结点，如图1 - 1 的叶 结点4 的位置等。a l p h a - b e t a 剪枝算法与极小极大值算法相比，在保证能求出根结点 值及其来自哪个子结点的同时，节省了大量的无须遍历的结点；尤其是所需遍历的叶 结点数大为减少，在机器博弈中能显著降低时间开销。 文献【1 ，第2 9 8 3 0 0 页】给出了负极大值和极小极大值描述j 包括深层剪枝的 a l p h a - b e t a 搜索算法，文献【6 、7 附录】给出了为窗口搜索而改进的算法，即，具有 “f a i l s o f t 功能的a l p h a - b e t a 搜索算法，这个改进虽简单，对剪枝也没有影响，却为 窗口探测带来了便利。此处给出使用极小极大值描述、具f a l l - s o f t 功能的c 伪码 a l p h a - b e t a 搜索算法，据文献【1 ，6 ，7 ，8 】稍做整理。 算法1 1 极小极大值的a l p h a - b e t a 搜索算法 n t a h a ( d a 。b 、d 为当前结点蓟时结点的层数a 为t 限值8 为上限值。 l i n tm | 一： i f ( d rt o 、r e t u r nv a t ( t e a y _ 剃e 、；n 调用估值函数，返回时结点的 吉值。 细( i = l ；i 1w ：t + + 1 遍历所有子结点。 l m f f im a x m b e t a ( d - 1 。a 。b 、：q 保持兄弟结点的极大值。 矿细 aj a = m ； f ( a - - - - b 、r e t u r nm ； ，发生0 药枝提前返回o l 。 r e t u r n m ： 一种新的博弈树搜索算法及其应用研究 第一章博弈树搜索算法的历史与现状 j ， 。 i r a b e t a ( d ，n 卢j l i n tm = 一： i f ( a = = djr p f l 4 r l t 删眦加纠； f o r ( i = j ；i ，w ；f + + j l r a f f im i n ( m a h a ( d q q b 、 、；鼢保持兄弟结点的极小值。 i ( m 18 = m ； 嘻b = a 、r e t u r n f i t , 抒发生d 剪枝，提裁返回。 j r e t u r n m ； 算法1 - 1 的调用形式一般为a l p h a ( d ，一，+ ) 。实际应用的搜索算法可能更关心 的是，根结点的值来自于哪个一层子结点，需对上述算法稍加改进来记录和传递该信 息，还需要一个走法生成器来生成子结点等。 1 5 极小博弈树 有了a l p h a - b e t a 剪枝算法，搜索的效率无疑大大提高，尤其在深层博弈树和稠密 博弈树( b u s h yg a m et r e e ，指每个结点的子结点数较多) 的搜索中。那么，包含深层剪 枝的a l p h a - b e t a 搜索的最小搜索极限是多少，就自然成为人们关注的一个焦点。该极 限据文献【1 】的说法，早在1 9 6 1 年，由l e v i n 简单提及，但最早提及该结论的公开文 献见1 9 6 3 年苏联的b r u d n o 的文献 5 】，该文献也是最早详述“深层a l p h a - b e t a 剪枝 方法的，文中提到了发生最多剪枝的情形，该极限所对应的遍历过的博弈子树称为极 小( 博弈) 树或极小搜索树( m i n j m a lg a m e t r e m m i n i m a lu r e m i n i m a ls e a r c h 眈e ) ，也总结 出极小树叶结点数的结论，但未能给出证明。包含深层剪枝的a l p h a - b e m 搜索的最小 搜索极限极小( 博弈) 树叶结点数的结论为： n w d = w j + w d ，2 1 1 ( 1 - 1 ) 其中w 为每个结点的子结点数，d 为博弈树深度，式( 1 1 ) 中用l x j 表示x 的最 大整数，用f x l 表示x 的最小整数。这个结论的前提是：假设每个结点的子结点数 目均相同，并且叶结点均出现在同一层( 最末层) ，这样的博弈树成为“均衡博弈树 第一章博弈树搜索算法的历史与现状 一种新的博弈树搜索算法及其应用研究 ( u n i f o r mg a m e 锻动 【文献1 】。 极小树叶结点数定理的证明最早见于1 9 6 9 年，由j a m e sr s l a g l e 和j o h nk d i x o n 在文献 9 】中给出了用数学归纳法的一个证明。1 9 7 5 年，d o n a l de k n u t h 和r o n a l dw m o o r e 在文献【l 】中，则给出了一个归纳论述式的证明，同时指出了文献【9 】的证明的 一个不足之处。笔者在分析文献【1 】的证明时，发现其仍然存在缺陷，并找到了一种 直接推导式的简洁证明方法，将在第5 章给出。， 图1 - 2 包含深层a l p h a - b e t a 剪枝的最佳情形示意图 图1 2 是以子结点数w = 3 ，深度d = 5 的均衡博弈树为例，画出了相应的极小搜索 树，在可能发生剪枝的地方均发生了剪枝，剪去的分枝未画出。由于以上a l p h a - b e t a 搜索算法是在遍历的同时进行博弈树的生成，在生成相应的博弈树时尽量对子结点进 行排序优化，是提高剪枝效率的最主要手段。 极小树定理指明了a b 剪枝算法及其各种改进算法的一个理论上的最小搜索极 限【1 】，该定理表明，在博弈树近乎最优时，a l p h a - b e t a 搜索大约可以达到极小极大值 搜索的两倍的深度。对基于“与或”树构想的各类算法该极限也同样适用，因此，成 为各种博弈树搜索算法进行效率评价的标尺 见文献2 0 - 2 5 ，2 7 3 0 ，4 3 _ 4 6 】。 由于搜索的时间开销主要来自于叶结点的估值，因此，搜索效率多用遍历的叶结 点数n b p ( n u m b e ro fb o t t o mp o s i t i o n s ) 来衡量。a l p h a - b e t a 搜索在有限深度时的平均剪 枝效率，曾引起了人们的研究兴趣，不过至今仍无法给出严格的数学上的平均剪枝效 率结论【见文献1 ，1 0 ，1 1 ，1 2 ，1 3 ，1 4 ，1 5 。当搜索深度趋于o o 时的剪枝效率，可用分支因子 r a 币= l i r a ( n w ，d ) d 来衡量，文献【l o 】的结论是当搜索深度趋于o o 时，r 。吊= 毛( 1 毛w ) ，其中毛w 为方程x w + x 一1 = 0 的正根，r a b 的近似值为( o 9 2 5 ) w 玑7 47 ，有限深度 时的如8 虽然没有确切结论，也只是稍大于以上的极限。这表明对于结点值是离散的、 一种新的博奔树搜索算法及其应用研究第一章博奔树搜索算法的历史与现状 随机分布的博弈树，a l p h a - b e t a 搜索的剪枝是相当可观的。相当于对随搜索深度增加 以指数级爆炸增长的博弈树叶结点数( w d ) ，平均只搜索了少于w 玑8 d 数目的n b p 。实 际应用中生成博弈树时，由于已经对子结点进行了排序优化，一般情况下的剪枝效率 高于以上的平均剪枝效率。 1 6 窗口搜索 如果算法1 一l 的初始调用形式为a l p h a ( d ，v l ，v 2 ) ，其中v 1 和v 2 为有限值且 v l v 2 ，则称为窗口搜索。其返回值v 可分三种情形，v - - - v l ，( 喜) v - - v 2 ，v 1 n 、r e t u r np f “= v a l u e ；纷剪枝同时保存结点p 的下界。 i f ( v a l u e m a 搿c o r e ) m a x s c o r e 。v l 妣； l r e t u r n p f “= m a 盥c o r t ；露返回探灏飘的上界同时保存结点p 的上界。 j ， 姒m t _ b e t a ( p , d j l i n tm i n s c o r e = + ： i f ( d = 2 0o rt e r m i n a l ( pj j r e t l l l t l e v a l u a t i o n ( pj ； i f ( p 。za 、r e t u r np | 。：，在博弈图或独立探灏时有用。 谚( p 彳 a ) r e t u r np f 。； w = l o a d _ s u c c e s s o r s 嗡；找出p 结点的子结点p i 。p 。w 为子结点个数o f o r ( i = l ：i = w ：t + + 、 即遍历所有子结点o l v a l u e = m ta l p h a ( p i d - 11 ： 1 0 一种新的博弈树搜索算法及其应用研究 第一章博弈树搜索算法的历史与现状 i f ( v a l u e | a 、r e t u r np f 。= v a l u e ：i i j 寥t j l 同时保存结点p 的上界 r e t u r n p f “；m i n s c o r e ；纷返回探溺勤的下界同时保存结点p 的下界。 ， 本文中的空窗探测不加说明时，均是指增加了记忆功能和f a i l s o f t 功能的空窗探 测。 1 7 置换表技术 许多博弈树搜索算法不是靠一次搜索完成的，如渴望搜索。当再次搜索同个博 弈树时，如果能把以前搜索的信息加以利用，无疑将提高搜索效率，保存以前搜索信 息主要使用置换表( r 丌，t r a n s p o s i t i o nt a b l e s ) 1 8 ，2 1 ，2 2 。置换表一般容量很大，以尽 量保存庞大的博弈树各结点信息，并且应实现快速访问，因此多用哈希表技术来具体 实现。与一般哈希表不同的是，这里的哈希表一般不使用再散列技术，在哈希冲突很 少时，不去进行再散列，能有效加快处理速度，如果出现写冲突，直接覆盖，只要在 读访问时不使用错误数据即可。 置换表中的一个数据项应包含详细信息说明对应博弈树的何种结点，该结点的搜 索评估值，以及评估值对应的搜索深度等。其中评估值一般还可以分成两部分，分别 保存该结点的上限值和下限值，比如渴望搜索和空窗探测等，多数时候是得到一个结 点的上限值或下限值就剪枝返回，这种值同样有利用价值。如果得到了某结点的准确 评估值，可以将上限值和下限值保存成一样来表示。置换表在使用时一般要及时更新。 置换表技术在当今机器博弈领域已经是广为使用的技术，对搜索速度有明显的提高。 机器博弈中的博弈树往往是非常庞大的，a l p h a - b e t a 搜索由于一般情况下是边生 成结点边搜索，并不需要保存整个博弈树，内存开销并不大。如果置换表用来保存博 弈树已经搜索过的全部结点信息，内存开销将是巨大的。从剪枝效率的角度考虑，由 于博弈树顶层的剪枝对剪枝效率具有决定性的影响，因此，即使置换表只保存较顶层 的博弈树结点信息，仍然能够明显地提高剪枝效率。 对于置换表的使用，还有一种情况需要特别指出，博弈树最末层结点在很多情况 下保存到置换表中，并没有作用，这一点容易被很多人所忽视，导致置换表使用上的 第一章博弈树搜索算法的历史与现状一种新的博弈树搜索算法及其应用研究 浪费，也降低了搜索速度。这里的具体道理将在本章第8 节后结合说明。 置换表不仅仅是提高重复搜索的效率，还能有效地解决博弈图的搜索，这部分见 本章第1 3 节的叙述。 1 8 p v s n e g a s c o u t 搜索 上世纪8 0 年代出现的p v s ( p r i n c i p a lv a r i a t i o ns e a r c h ，主要变例搜索) 算法【文献 6 ，1 l ，1 2 】，也称为n e g a s c o u t 搜索算法，a r e i n e f e l d 声称是他于1 9 8 2 年发明了该算法。 p v s 算法在机器博弈领域使用广泛，是最常用的搜索算法之一。p v s 算法从最初的 非递归方式演变至递归方式，并且在最末两层由文献【1 9 】做了改进。p v s 算法使用了 空窗探测，其搜索原理可简单地描述为：递归地以左结点为假想的最佳结点进行宽窗 口搜索，然后空窗探测其兄弟结点，如较已知的结点为佳，则用相应的宽窗口准确搜 索出该结点的值并设为最佳，如此进行下去。 由于空窗探测的时间开销一般低于窗口搜索，如果探测的成功率高于一个阀值， 则p v s 搜索将比a l p h a - b e t a 搜索节省时间。从另一角度来说，p v s 相当于在深度优先 的a l p h a - b e t a 搜索中，适当引入了最佳优先的策略，是两者的结合。 文献 1 3 】简洁地分析了p v s 算法的效率，结论是在内部结点是强有序( s t r o n g l y o r a e r e a 2 0 ) 时，p v s 搜索优于a l p h a - b e t a 搜索。这是一个相对保守的结论。初步实验 证实，结点优化排序后，p v s 搜索较a l p h a - b e t a 快3 0 以上。实际应用的博弈树搜索， 几乎都进行了内部结点顺序的大力优化，因此，p v s 搜索效率明显好于a l p h a - b e t a 搜 索。 在p v s 搜索对第一层最后一个结点的空窗探测f a l l - h i g h 时，已表明该结点即是要 找的最佳结点，可以省去对该结点的重新搜索，这称之为l - a l p h a 6 、7 附录】，能轻 微提高搜索效率，尽管此时还未找出根结点的准确值，但从应用的角度来说，已经知 道了一层的最佳子结点( 最后一个) ，已达到了搜索目标。 由于p v s 搜索中存在空窗探测后的重新搜索，采用增加记忆功能( 一般用置换表 技术实现) ，可以跳过某些无须再搜索的结点，加快p v s 搜索速度，同时可以加快博 弈图【2 1 搜索速度，称为记忆增强的p v s 搜索。比较充分地使用记忆增强技术后，笔 者的实验表明，p v s 搜索的速度还能提高2 0 以上( 这里包括了博弈图的贡献) 。 以下是记忆增强的p v s 搜索的c 伪码算法，据文献【6 ，1 1 ，1 2 和文献【1 9 】的改进方 一种新的博弈树搜索算法及其应用研究第一章博弈树搜索算法的历史与现状 法整理。其中增加的置换表技术一般通过哈希表实现。 算法1 3 增强记忆的p v s 搜索算法 i m p