资源描述：
《博弈树搜索算法在中国象棋中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、博弈树搜索算法在中国象棋中的应用计算机系统应用2009年第9期博弈树搜索算法在中国象棋中的应用①ApplicationofGameTreeSearchAlgorithminComputerChineseChess岳金朋冯速(北京师范大学信息科学与技术学院北京100875)摘要:针对中国象棋博弈中较为高效的0【一B剪枝算法进行研究,以提升其效率.依据—p剪枝算法的效率与子节点扩展的排列顺序高度相关的事实及中国象棋自身的特点,从优化着法的排列顺序入手,设计出启发能力较强的着法排列方案,并进一步提出扩大窗口的内部迭代加深算法对上述着法排列方案进行修正,从
2、而使着法顺序得到进一步的优化.实验数据表明,提出的方法可以明显提升一13剪枝的效率.关键词:中国象棋d—B剪枝着法顺序内部迭代加深扩大窗口机器博弈是人工智能研究的重要分支,人类对机器博弈的研究衍生了大量的研究成果.d—B剪枝是机器博弈搜索中最为重要的算法之一.本文在研制中国象棋博弈程序的过程中,设计了一个较为优化的着法生成顺序,对于同一层数可以花费更少的搜索时间,因此棋力更高.在此基础上,提出了一种扩大窗口的内部迭代加深算法,对着法生成顺序做了进一步的优化,从而使d—B剪枝的效率有了更大幅度的提高.在着法生成顺序中,本文还提出了静态评价启发技术.本
3、文所使用的Of.一8剪枝的概念及相关的博弈树搜索算法在文献【1】中有较详尽的介绍.1着法排列顺序的优化一B剪枝对着法顺序非常敏感【2】,所以采用启发式方法对其进行优化是提高算法效率的关键所在.本节参考国际象棋中已有的启发式方法,结合中国象棋的实际情况,提出一个较好的着法排列方案,并通过实验进行验证.在该方案中,我们使用置换表启发,静态评价启发及动态启发等技术.1.1置换表启发在搜索中,经常会在不同的路径上遇到相同的棋局,这样的子树没有必要重复搜索,把最优着法,分值,深度和节点类型等信息保存在一个称为置换表①基金项目:国家自然科学基金(6027301
4、5)收稿时间:2009-01-09140应用技术AppliedTechnique(transpositiontable)t3?4】的数据结构中,再次遇到时直接运用即可.假设对某局面进行d层搜索,窗口是【仅,B】,而发现该局面在置换表中已存在,其评价值为v,类型为t,深度为d'.当d'≥d时,如果t为精确型,便可直接返回1,而代替搜索;如果t为高出边界型且v≥13,便可进行剪枝.否则进行重新搜索以保证所取得数据的准确,此时置换表中保存的最佳着法给了我们一定的启发,它为搜索提供一个较优着法,该着法应排在前面优先搜索,这使总体着法顺序得到一定程度的优化,
5、置换表的一个主要作用是它对着法顺序的启发Is?61.1.2静态评价启发静态评价启发(staticevaluationheuristic)主要用来优化吃子着法的顺序.对吃子着法进行静态评价启发,就是要找出表面上占有较大优势的吃子着法.中国象棋的主要攻击手段就是吃子,首先通过检测吃子来寻找最优着法往往会产生较好的效果.如果我们用V表示攻击子的价值,用W表示被吃子的价值(各个棋子的价值如表1所示),那么某个吃子着法的价值U可表示为:f一(被吃子有保护),.,I(被吃子无保护)2009年第9期计算机系统应用表1棋子的交换价值帅(将)主马炮仕(士)相(象)兵
6、(卒)5433112当吃子着法的值U>0时为表面上能得到获得很大利益的着法,这样的着法往往是好的着法;U=0可能是等价值的换子,这样的着法也值得一试;而U<0的着法往往是吃亏的.因此我们可将吃子着法依据U进行排序,并对U≥0的着法优先进行搜索.1.3动态启发相对来说,对于中国象棋中的某一局面,UI>0的吃子着法是很少的,大多数着法都是U<0的吃子着法和非吃子的着法.对于这些着法仅用1.2节所述的静态评价启发是不够的,还要进行动态启发(dynamicheuristic).树搜索的过程,实际也是信息积累的过程.对这些信息进行挖掘
7、,可以得到我们所需要的启发信息.国际象棋的经验表明,历史启发(historyheuris-tic)【7】和杀手启发(killerheuristic)f8J都是很好的动态启发方法.历史启发的思想是:搜索树中某个节点上的好着法,对于其他节点可能也是好的.所谓好着法是指可以引发剪枝的着法,或者是其兄弟节点中最好的着7】.一经遇到这样的着法,算法就给其历史得分一个相应的增量,使其具有更高的优先搜索权,这个增量通常为d2(d为当前节点需要搜索的深度)或2d.具体地说,就是设立一个90×90的数组,红方和黑方的着法都记录在这个数组中,前一个指标代表起始格,后一
8、个指标代表目标格;或者设立一个14×90的数组,红方着法和黑方着法分别记录,前一个指标代表兵种,后一个指标代表目标格.历史
