在后继的搜索过程中新万博体育官方网站

当前位置:新万博体育官方网站 > 新万博体育官方网站 > 在后继的搜索过程中新万博体育官方网站
作者: 新万博体育官方网站|来源: http://www.woyaokaoyan.com|栏目:新万博体育官方网站

文章关键词:新万博体育官方网站,博弈树搜索

  博弈树搜索算法的分析与实现Research Game-treeSearch Algorithm WeiChunbo Wang Hairui Wen Qiaonong (昆明理工大 学信息工程与自动化学院, 昆明 650051) (Faculty Automation,KunmingUniversity Technology,Kunming 650051) 果分析。B*算法是 剪枝算法的一些缺陷。关键字: 人工智能; 博弈树搜索; 剪枝算法;B*算法 中图分类号:TP181 文献标识码:A 文章编号:1671-4792-(2007)5 -0037-03 Abstract: alpha-betapruning algorithm mostimportant maturegame-tree search algorithm. we give its improved strategy implementaltechnology, furthermore we present experiment result relativenew method which differentfrom alpha-beta pruning algorithm, alpha-beta.Keywords: Artificial Intelligence; Game-tree Search; Alpha-beta Pruning Algorithm; 引言在智能过程中,搜索是必不可少的,是人工智能中的 个基本问题——Nilsson。这是因为人工智能研究的主要是 那些没有成熟方法可依的问题领域,需要一步步搜索求解。 游戏中如何找到对自己有利的局面就属于这类问题。在游戏 (人机博弈)程序中博弈树搜索算法是其核心的部分,它与 估值及规则(走法)构成一个完整的系统。 剪枝算法窗口原则(Window Principle) (初始的β值),在搜索进行中再 就有可能提高剪枝效率,这就是窗口原则。使用窗口原则的算法有: Falphabeta 算法,即 Fail- soft-alphabeta 算法; 渴望搜索(Aspiration Search); 小窗口搜索(MinimalWindow Search/PVS) 置换表(Transpotion Table) 置换表基本思想: 在搜索进行中,用一张表把搜索过的 节点结果(包括搜索深度,估值类型: 准确还是上下边界) 记录下来,在后继的搜索过程中,查看表中记录。如果搜索 的节点已经有记录(子树的深度大于或者等于当前的新节点 要求的搜索深度),它的信息就可以直接运用了,这样我们 可以避免重复搜索很多子树。置换表是一种内存增强技术, 以空间换时间。 历史启发(History Heuristic) 历史启发是为 了迎合 剪枝搜索对节点排列顺序敏感的特点来提高剪枝效率的,即根据历史走法对当前搜索的 点集进行排序,新万博体育官方网站从而优先搜索好的走法。迭代深化(Iterative Deepening) 迭代深化是一 个不断求精的过程,对博弈树进行多次遍 历,并不断加深其深度,用于控制搜索的时间。 在实用中迭 代深化和前面提到的算法结合使用具有很好 的效果,如 PVS 算法,上几层迭代得到的最佳走法可以帮助 下一层提高剪枝效率; 迭代过程中把前面局面的历史得分存 入置换表,最佳走法存入历史启发表可以提高剪枝效率。 1.5 实验数据分析 各种增强策略都能提高 剪枝的效率,其中空窗口15 技广场2007.5 探测(PVS) 从第五层开始平均需估计的节点数减少为一半, 而效率提高一倍。单纯的迭代深化由于在迭代需要耗费时 间,从效率上看提高不大。置换表在前三层没什么表现,这 是因为置换表操作也要耗费时间,且当其命中率低时效果不 佳,但层数较多命中率高时优势越来越明显。历史启发是这 几种增强策略中最好的,在第五层效率就能提高十倍以上, 越往后效果更好,这也证实了 剪枝对顺序的极度敏感。MTD(f)算法在实验中的前几层稍优于 PVS 算法,但它层数大 于六时很不稳定且本身带置换表,因此在把各种增强策略融 合时不如 PVS 算法。融合各种增强策略的 PVS 算法在第六层 就比基本的 算法2.1 算法是由Hans 1979年提出来的一 算法,毫无疑问B*算法是到目前为止最具有人类风格的棋 算法的思想与要点:每个节点用一个乐观估值和一个悲 观估值来表示评价值。两个估计值都动态可变,且估值出自 同一方的立场,只是估计的棋局按层次交错更替。对对方棋 局的乐观估计即是对本方棋局的悲观估计; 对对方棋局的悲 观估计即是对本方棋局的乐观估计。因此,从下层节点向上 层节点反馈信息时,悲观估计和乐观估计是交叉传递的。B* 树在展开过程中,只要子节点的估值有利于父节点估值的精 化,即改动父节点的估计值,即使乐观估值和一个悲观估值 相互靠近(当当前节点深度大于零时需回溯),如果这种改动 波及到父节点的估值,则根节点需考虑使用何种策略。B* 法设立两种策略,证明最优(PROVEB EST) 和排除其余 (DISPROVEREST) 。算法从这点出发,用这两个界来证明哪个 节点是最好的。当根节点的一个孩子的悲观值不比所有其它 节点的乐观值差的时候,B* 算法就结束了。算法的搜索控制 就是尽可能快的得到终止条件。 算法的优点是找到一步好棋速度快,不限定搜索深度,不会“产生水平效应”(这是固定深度 一个缺点),缺点是它对局面的乐观值和悲观值的估计依赖 性太强,实现困难。 2.2 算法伪代码typedef struct statue qijucon; qiju为当前棋局内容(数组) int opt; 棋局乐观估计值int pes; 棋局悲观估计值unsigned par; 父节点所在的地址unsigned eld;// 长子节点所在的地址 unsigned young;幼子节点所在的地址 STATUE;sta cur-qiju,-ININITY, ININITY, qijuBXin(STATUE sta) vector

  v[i].opt&& v[i].opt

  v[best]. opt) next 修改次极小乐观值节点位置if(v[pest]. pes pes)pest intopt v[best].opt;int pes 满足条件,则修改当前节点的估计值,并在深度大于零时进行回溯 (opt

  v[cur].pes opt;v[cur].opt pes;if(depth v[cur].par;depth--; goto lab; 有一枝的悲观值不小于其它枝的乐观值,则搜索结束。; if(takeprovebest strategy) cur best;else cur best;depth++; 2.3实验说明 实验中用的策略为 Berliner 原则: 用一组候选分枝与 最佳分枝做比较,如果各候选分枝实行信息反馈的深度是 ti,最佳分枝实行信息反馈的深度是 t,比较ti2 者小于后者,则采用DISPROVEREST 策略,否则采用 PROVEBEST 策略,即优先搜索那些至今搜索深度比较浅的分 算法对估值的依赖性很强,实验所用的估值效果实现算法速度很快(时间小于一秒),但走法只有搜索深 度为三层 结束语以上讨论了博弈树搜索算法的两类算法,其中 枝算法比较成熟,是当前最常用的算法,在融合各种策略后具有很高的剪枝效率。如果能进一步改进数据结构和进行代 码优化以及使用开局、残局库可以使程序具有很高的效率智 算法由于其复杂性,一般使用较少,国内研究的热情不高,有待进一步研究,包括如何对棋局进行估值,使用何 种策略以及与在中国象棋、围棋等游戏中实现。 参考文献 [1]陆汝钤.人工智能[M].北京:科学出版社,1995. 王小春.游戏编程(人机博弈)[M].重庆:重庆大学出版社,2002. [3][美]Nils Nilsson.人工智能[M].北京:机械工 业出版社,2000. [4]Knuth, D.E. Moore,R.W. (1975). Analy-sis Alpha-BetaPruning[J]. Artificial Intelligence, Vol. 4:293-326.[5]Berliner, H.J. (1979). B*-treesearch: best-firstproof procedure[J]. Artificial Intelligence, Vol. 12, 1:23-40.作者简介 危春波(1981 —),男,湖南新邵县人,现为昆明理工 大学 2005 级硕士研究生,主要研究方向: 游戏与人工智能。 17

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!