作者:nicepeople10
中象棋软搜索引擎揭密(一)fenon
北京大赛终于过去了,在这场盛事前后这段时间,静下心来回顾了走过的象棋研究的路子,心得感触良多.为了纪念这段时间的美好,我决定把这段时间积累的对象棋引擎的心得,总结分享出来
我个人希望通过这篇文章,把一些顶尖棋软的知识普及开来,提高开源象棋软件的水平.
1.搜索引擎和审局之间的关系,如何建立
阅读下面的内容时,首先需要了解几个背景知识
a.人工智能的博弈搜索树和PVS搜索之间的关系
b.PVS搜索是无损搜索
c.PVS的搜索效率和搜索次序的关系
首先明确几点:
a.做一个全PVS的搜索,在限定了层数的情况下,如果基于不正确的知识(比如子力表),并不能保证一定能把杀棋找出来(可能会跑去吃子)
b.为了提高棋力,无损搜索PVS是不足够的,还是需要剪枝的
c.搜索树和审局之间的关系,首先知识必须能够引导搜索到正确盘面(这个地球人应该都知道),第二是避免搜索把正确的分支剪除掉(这个谈论得少一些,我以前曾经有很长一段时间不知道)
我认为,审局和搜索之间的关系的建立,在于
a.知识是带有正确的倾向性的(只能说是倾向性,因为知识很难做到全面准确)
b.搜索是根据知识而采取剪枝方式的(这个下面详细分析)
下面我举一个简单的例子,来说明知识和搜索之间的关系
帅
_____
|||
马_|将_|_兵
|_|_|_|_象
在这个盘面,兵只要靠近王一步,就可以将死了对方,但是基于子力表做depth=1的PVS搜索,只会选择:兵吃象,有利,而且评估子力分数很高,所以吃象
那么有什么办法避免这种情况呢?
a.depth=1的时候不做剪枝
b.给予引擎审局的知识,告诉引擎保持马非底线兵这种组合对将才具有杀伤力
这样就给出了两种选择,哪种更好?
实际上,b这种选择有两种局限
a.局限于现在对审局模型建立的水平,b这种情况需要花费大量的人力功夫来维护完整的知识,而且很难做到准确
b.目前的引擎的搜索棋步排序,大都是基于最近访问->杀棋步->吃子步这样的棋步排序方法,我们可以很容易想象到,使用全面复杂的知识,会引起搜索结果冲突(凑着一个吃子或者杀棋的步子去走,但是最后发现达不到预期的效果),大大降低了搜索的效率
正是因为上面的原因,现在我所了解到的高端引擎,大都是通过控制剪枝的危险程度,来弥补知识的不足,比如,在nullmove中限制depth>=2,或者,在lmr(latemovereduction)--如变种:fruit的historypruning,控制depth>=3,都是利用控制剪枝来弥补知识的缺陷.
我们很清楚知道,depth<=2的时候,都限制了不能剪枝的话,那么刚才的盘面,并不需要任何知识,就可以找出杀棋步,但是,这个是不是我们需要的呢?我想不是的,如果限制了depth<=2不能剪枝的话,我们会发现我们的搜索,产生了大量的节点,啊,天啊,可怕的搜索浪费
当然最理想的方法是,搜索排序的次序是基于知识的,而且盘面评估是基于知识的,如果我们能够达到这样的效果,嗯,我想depth<=1不剪枝的限制也可以去掉了,这样的引擎肯定效率更高吧
现在,让我们想想,哪些分支我们是不想被错误剪掉的?当然是杀棋步,杀棋>吃子,基于子力表的搜索PVS,很可能漏掉的棋步是杀棋步,而这个恰恰是我们不想见到的
对于攻杀激烈的中国象棋,可以说两个引擎的差别在于,谁能更快更准确找到杀棋步.
口语化一点来说给你多搜索两层的能耐,你能保证绝对能通过蚕食我的大子把我变成光棍司令?尤其是随着高层效应的出现(引擎和硬件的发展,搜索的层数越来越大),这种可能更是趋向于零,所以我们应该尽量避免漏掉杀棋步
我知道有很多引擎的做法是,对有潜在攻势的局面做出模糊判断,并且赋予高分,如越容易发生杀棋的棋步,给予越高的分数,例如三子归边的分数>马炮的分数,这样就可避免因为吃马炮而漏掉杀棋,但是这种模糊判断有些致命的缺点
a.模糊知识,会造成大量的搜索浪费(条件越不准确,越容易造成搜索浪费)
b.模糊知识会造成错误的判断,导致乱弃子
c.引擎发展需要更长的发展周期,需要大量的对局来积累知识
一种比较适中的解决方案是,采取depth<=1不剪枝的搜索方法,并且给予depth=1时候,可以形成杀棋的棋型知识的判断
这种方法的原理是,depth=1的搜索,可以达到depth==2的效果,并且可以避免模糊知识判断带来的误搜索的缺陷
这种解决方案的优点在于
a.depth=1可以生成杀棋的知识可以穷举
b.知识准确度高,可以大幅度减少搜索浪费
缺点在于,depth=1可以形成的杀型,覆盖面有限,剩下的知识,还是需要通过一些模糊判断来补充,当然这种补充少很多了,而且完善起来也难度降低很多
上面的介绍可以说是知识模型的缺陷造成的对搜索的依赖,下面我再来说说,知识对搜索产生的影响
我们假设有一个盘面,depth=11的PVS全搜索才能发现杀棋,那么下面的知识,做depth=10搜索时,哪种才能走出正确的棋步呢?
a.对depth=1情况可杀棋的知识评估
b.对depth>=2情况可杀棋的知识评估
c.子力组合(如单车单王胜单王)和子力优势
d.位置分(不是子力表,只是位置的分数,如灵活度等)
实际上我们很容易就可以判断出来,depth=1的知识评估,能走出正确的棋步,情况b也可能走出正确的棋步,但是会有一定的误判,c,d大都情况下,走不出正确的棋步
我们现在对所有的知识打分,这个分数依赖的因素应该是(depth,准确度,搜索浪费),即score=形势*(准确度/(depth*搜索浪费))
因为用评估盘面希望得到的分数等于depth>3的棋步,准确度是相当低甚至会引起大量错误的,所以我们对盘面评估会有一定的限度,同理,评估depth=1变化内的盘面,我们可以做到非常精确,这个时候可以给一个准确的分数
上面提到的a,b,c,d四种知识,对中国象棋软件的知识覆盖面是相当广了,我们可以很简单看出,a可以奖励>马炮的分数,而b因为可能走入误区,常常只是奖励>士相的分数,子力组合不会产生误区,但是需要搜索很深才能得出正解,所以分数也是不会太高,位置分则更小了
但是,给予引擎全面而准确的知识是否恰当呢?即,知识是不是越全面,棋力越强呢?很多朋友都问过这个问题,并且认为恰当的知识会减少搜索量,而且这也是很多朋友追求的方向.我实践的答案是否.搜索其实是追求一种性价比,单位搜索量内,能得到最好的搜索结果,才是好的搜索.简单说说原理,当盘面有两三个知识倾向都可以产生PV路径的时候,只会带来引擎的左右徘徊,尤其在杀棋的盘面,会大大降低搜索的效率,这部分的实践结果,我会在6.建立以kingsafety为核心的审局,以及审局模型的详细分析再进一步详细分析
这里我想纠正一个错误的想法,常常有一些不了解搜索引擎原理的朋友,拿一些盘面,让棋软去判断,看谁能更快更准找到正解,要尽快解出这种盘面,往往需要大量的模糊知识,或者足够的深度,前者无疑是把棋软送上绝路的一种做法.这种评估只是有一定的意义,但绝对不是衡量棋软水平的标准.
2.fruit引擎分析,fruit引擎能达到2600的高度的原因(对比crafty进行阐述)
fruit引擎并不追求速度,实际上,fruit并没有使用流行的bitfile,bitrank技术或者bitboard,所以fruit的nps在国际象棋引擎中并不算高(我想比起crafty应该比不上),如果说两者的差异在于评估的话,嗯,那不在我所了解的范围,我只谈谈两者引擎上面的差别
a.fruit的pv节点的意义以及基于pv节点搜索剪枝的效率
能够在搜索中,把PV节点区分出来,并且根据节点类型进行剪枝,fruit可以说对PVS理解是非常深刻的.
PV节点的定义大家可以查查相关资料,既然PV节点表示正确的搜索结果,那么就肯定不应该剪掉.同样,对于不是PV节点的,就不会找出正确的搜索路径,这就应该剪掉.这个也是fruit剪枝的理论依据。
道理是这样说,但是我们一开始并不知道每一个节点的类型,所以在搜索的时候,会假设某个节点不是PV节点,然后看它是否会fail,如果fail,再做PV节点的搜索.
假如这种假设是成立的,那么就成功完成了对该非PV节点路径的剪枝,否则,需要重新搜索,因为对PV节点假设判断的搜索是做windows=1的搜索,所以耗费的代价是很低的.
下面来看看fruit的实现方法,我认为fruit对PV节点理解的实现方法非常优雅.
intsearch_root()
{
本节点做PV搜索
if(树根节点并且首节点)
下一层节点为PV节点//这个时候还没有找出PV路径,所以必须做PV节点搜索
else
{
下一层节点做假设不是PV节点的搜索
if(fail)
下一层节点做PV节点的搜索
}
}
intsearch_full()
{
根据上一层对该节点的判断,进行节点搜索
if(首节点||假设不是PV节点的搜索)//当假设不是PV节点时,windows=1这个时候不应该假设,应该直接计算了,否则就是重复计算浪费时间
下一节点的节点类型跟本节点类型一致
else
{
下一层节点做假设不是PV节点的搜索
if(fail)
下一层节点做PV节点的搜索
}
}
中象棋软搜索引擎揭密(二)fenon
crafty中,对PV节点的区分方法,是PV节点是否落在[-vMate,+vMate]中,实际上,这种判断方法,对子树的PV节点并不能做出有效的判断,这也直接导致了搜索效率的下降
正是因为PV节点的特殊意义,所以凡是PV节点,fruit都不做剪枝,不从HASH取步,甚至PV节点还需要加强搜索的强度(参考TogaII)
b.fruit的nullmove剖析
我们先来看看fruit的nullmove的实现
if(UseNull&&depth>=NullDepth&&node_type!=NodePV){//不对PV节点进行剪枝,而且depth==1时不剪枝(原因参考上文)
if(!in_check//不是将军盘面
&&!value_is_mate(beta)//当落入一个不知道上限的窗口时,不剪枝,这种情况发生在height==2时
&&do_null(board)//国象规矩限定子>=2
&&(!UseNullEval||depth=beta)){//根据距离叶子或者alpha,beta搜索中,棋形的评估进行控制
我想,对上面的控制条件,大家都是很好理解的,fruit中NullRedcution==3,这个可以理解为fruit审局做得比较完善,depth4时候剪枝的控制条件,这种控制条件往往是根据棋形进行控制,crafty是控制大子的个数,fruit是控制评估的结果,考虑到这个结果因引擎而异,我就不在这里讨论哪种条件才是更好的了
new_depth=depth-NullReduction-1;
move_do_null(board,undo);
value=-full_search(board,-beta,-beta+1,new_depth,height+1,new_pv,NODE_OPP(node_type));
move_undo_null(board,undo);
fruit的nullmove会导致一种和以外不同的搜索情况产生,crafty的做法是,上一层做了NULLMOVE,现在轮到我了,我应该移动棋步,但是fruit的做法,会引起双方的等待,这是否正确?
答案是,很正确.首先考虑算法上面的等价性,连续做NULLMOVE,其实等价于我不知道你是否做了NULLMOVE,不过我也尝试做一个NULLMOVE,看你是否能对我造成威胁,这个并不违背NULLMOVE的思想,而且一个不会产生PV路径的节点,做搜索有意义吗?没有意义.既然如此,那么就剪掉吧.
对nullmove的结果,fruit有两种特别的处理手段
第一,不保存结果,因为fruit的算法的剪枝,会让实际的值和nullmove产生的值差别很大
第二,对某些特殊情况,fruit会做一个nullmoveverify的search,fruit尝试全面利用nullmove,但是某些情况,nullmove成功的概率有限,需要做一定的验证
fruit对nullmove的实现方法,可以说得上是历史性的(开源的引擎来说),这个算法的优异,是fruit搜索效率特高的一个根本原因
c.fruit的qs加强
在上文中,我已经提过,fruit是尝试通过控制depth<=1使用全搜索的方法,尽可能发现杀棋,那么对nullmove来说如果depth<=4,发生了一个剪枝,立刻进入了qs,马上就把杀棋步剪掉了
为了防止这种情况,fruit对刚进入qs的棋步,不单单生成吃子步,还生成将军步,这可以有效防止把杀棋步漏掉的情况.
qs里面,fruit对吃子步产生的将军步,会解将,让对方保持继续进攻的机会,这也是为了防止qs漏掉杀棋步的一种有效措施
虽然qs的论述很少,而且很简单,但是,对qs中,将军的检查,却有着消耗20%性能,提高50%功能的性价比,这个也是crafty所缺少的
d.fruit的historypruning
要了解historypruning,首先建议参考国象中成熟的算法lmr(latemovereduction)的论述
fruit对lmr引入了historyvalue,并且对搜索结果做了verify,有效避免了lmr曾经的failhigh的问题
这里就不对historypruning的限制条件做详细的阐述了,实际上这种防止危险的检查方法和nullmove的限制是类似的,而且会根据不同引擎知识和搜索结合的特点而存在差异
historypruning经实践证明,是一种非常有效的剪枝方法,并且绝对不会对棋力有降低的影响(其实根本原因是不会漏掉杀棋步)
historypruning根据国外的测试,能够提高elo100,旧版的crafty并没有historypruning
e.fruit的hash实现方法
fruit的hash实现方法,经实践,大概比crafty的方法提高了5%~10%的性能
fruit对每个盘面,保存了一个上界和一个下界,如果对一个盘面搜索时,发现该盘面的搜索范围上界比过往的下界都要小,则返回保存的下界,如果发现搜索范围的下界比保存的上界要大,则返回保存的上界,如果发现盘面落入保存的窗口中,则当保存的上界和下界重合而且搜索深度比当前搜索深度更深时,返回保存的结果
这种hash的处理方法,修正了crafty中,只能对单边情况保存的不足,有效提高了效率
需要注意的地方是,在iterativesearch中,每次fruit都会把搜索出来的PV路径都保存到hash中,这是用于取步(不是取值),还有,在处理hash冲突时候,fruit使用了多个cluster的方法...需要细究的细节很多,大家有兴趣可以仔细看看fruit的实现
f.fruit的searchrootmovelist
fruit对每次搜索后对root节点记录分值,并根据分值重新排序,以便下一次使用,当棋步产生振荡的时候(在两个棋步之间徘徊)会有效提高引擎的搜索效率
g.fruit的FAILSOFT
嗯,关于FAILSOFT以及实践的方法,可以参考纵马奔流的****和fruit的代码,我就不再无聊多说一次了..
3.fruit2.1和TogaII1.2.1的差异,elo100的差距原因
首先需要说明的是,我是用diff的方法,比较两者在搜索实现上的差别的,应该是没有遗漏的
两者的差别列举如下
a.延伸的差异,根据特定棋形做了depth+1的搜索,也就是越搜反而越深(当然TogaII有手段防止过深)
b.剪枝的差异,包括打开futility,delta,并且对底层也做了historypruning
c.对棋步稳定的盘面(只产生一个PV路径),用渴望窗口搜索,减少搜索量
d.对危险情况的搜索的加强
两者差异原理分析
简单概括TogaII的改进,那就是利用国际象棋的知识调整了fruit的搜索树,对危险的盘面进行了更深的搜索,否则就剪掉.
首先TogaII最有效的改进，是在叶子附近，利用historyvalue把证明曾经无效的叶子节点丢弃掉，这是一个非常有效的算法，这里面的道理值得我们深思？为什么我们不能够发现一个这样的算法呢？
如果光是观察futility和delta剪枝法,我想肯定会有人对我提出疑问?不是说这些根据子力情况剪掉的分支会漏掉杀棋步吗?为什么还打开剪枝,OK,我来一个简单的回答,假如已经是用了知识判断过这类分支并不危险,那就可以剪掉了.
TogaII能改进fruit的原因基于对国际象棋的深刻理解(也许是大量的测试的证明),它的剪枝和延伸,是相辅相成的,如果有人想尝试这个方向,千万不要只开剪枝或者只加延伸
这个方向,是在搜索树中,加入对棋类知识的判断.调整搜索树更适合某种棋规.
4.fruit算法应用于中象引擎的分析及中象引擎算法改进分析
下面的内容是基于上述阐述的一些具体应用的例子，可对引擎做出一定的修正
a.nullmove改进
nullmove限制条件中,当depth<=4时,进入nullmove.这种情况会忽略了depth=1可能产生的杀棋步,当审局的知识缺乏该方面的内容时,会漏掉杀棋步
这个时候,可以根据自己引擎的审局知识的特点,做depth=1的search_verify
代码如下
if(depth<=4)
do_nullmove;
if(nullscore>=beta)
do_search_verify(depth=1);
这种方法可以避免一些杀棋情况的漏算,这个也可以算是搜索和知识结合的一个典型例子吧
b.historypruning改进
考虑下面的情况
[炮]吃车1,车2吃[炮],车2移动,和车1移动,这两个棋步,会引起同样的historyvalue的减少,虽然限制了historypruning发生在不吃子的情况,但是,中象的交换频率远>国象,这种情况对fruit中historyvalue<9830就剪枝(60%)显然不适合,因为中象发生上面的情况要高多了,而historyvalue<9834(60%)只要该棋步有一次被检索的情况就会发生,这个时候,修正historyvalue<16384*45%,可以有效减少误判
c.futility剪枝及delta剪枝的意义分析
嗯,这个,首先参考TogaII和fruit对比的文章
futility和delta,如果不会漏掉杀棋步,或者,在不会被对方杀死的情况,非常有助于扩大自己的子力优势,这是这两个剪枝法的机制决定的(注意，这两个剪枝法的依据是扩大子力优势，所以适用的范围是有限的，对双方对杀的盘面是会削弱攻击能力的)
我建议使用这两个剪枝法,当然是建立在调整过搜索树以后(避免在容易引发杀棋的盘面使用，常见的手段是判断kingsafety，是否处于被攻击状态中)
中象棋软搜索引擎揭密(三)fenon
d.棋步排序的改进
从PVS搜索的原理出发,搜索效率取决于搜索次序
常见的棋步排序是历史步->吃子步->killer->etc,这是基于最大化子力优势的搜索,当对杀时,这种搜索排序效率是非常低的.
考虑killer棋步,如果能够发生一个killer步的分数是杀棋步,那么调整棋步排序为历史步->killer->吃子步->etc,这样就很好地把杀棋和吃子都结合起来了
5.fruit算法和象眼的差异,如何提高象眼的棋力
通过本篇的介绍,希望能够把开源的象眼程序,改进到一个全新的高度,假如有人希望一起完成象眼的改进,请站内和我联系
下面是我认为可以有效提高象眼棋力的几个地方
a.基于PV节点的nullmovepruning
b.qs加强
c.Historypruning及TogaII剪枝法
d.棋步排序
e.hash的改进
f.IID算法修正
g.searchrootmovelist
6.建立以kingsafety为核心的审局,以及审局模型的详细介绍
a.对盘面区分阶段,不同阶段采取的策略是不同的,开中残差异是很大的
实际上,开局通过开局库和子力位置分+若干简单知识,是很容易走出正确的棋步盘面的,这个研究不深,我更多是依赖开局库解决这个问题
残局时候,调整位置分表,判断子力组合,这个时候因为子力很少,基本上难以进取,更多是应该考虑防守,控制搜索的危险程度和给予适当的分数,很容易做到这点
中局是比较复杂的,下面详细说说我所理解的地方
b.对某个阶段的知识,不要给引擎太多的选择,避免引擎找出多个PV路径,引起棋步的来回选择,如中局,应该集中思考杀棋或者扩大子力的优势
c.上面1.讲述了搜索和知识之间的关系,其中也提及了depth=1时候的杀棋知识评估的重要性,但是,只是局限于depth=1的杀棋知识,我们的盘面判断力还是很有限的,这个时候怎么办?我们能不能对depth>=2的情况进行评估
我提供一个实践的方法,那就是分层次打分.
比如:三子归边的判断,我们通过以下三种层次评分
(a)有沉底炮,+分(depth=3)
(b)有沉底炮和车可做炮架,+分(depth=2)
(c)有沉底炮和车并且马进入了可以助攻的区域,+分(depth=1)
刚才在上面的审局和搜索的关系中，我列举了4种知识，并且强调了知识只应该选择有效的，下面分别说说哪些知识是必须的，不在下面列表内的知识，我都不做判断了
a.准确的杀型
利用位置分值提示车马兵攻击王周围，依赖搜索完成
b.模糊的杀型
(a)当头炮(空头炮,镇中)
(b)底炮(三子归边)
(c)双车杀
c.子力组合，只做会引起问题的子力组合判断，如兑子后双马不佳
d.某些特别容易出问题的知识的补充
7.国际象棋Rybka的胜利以及将来棋软发展的一些展望
一些未来的研究方向,所以个人的意见应该是一些胡言乱语,仅作笑料
上面所说的一切,都是基于知识会有一个确定的分数,但是,这明显是错误的,谁能说三子归边是400分,而不是395分呢?有没有一种方法,可以动态评估这个分数,从而达到知识的最优化呢?
第二,传说中的根据知识排序棋步的方法
在国外流行的认为Rybka超越其他软件的原因是因为更聪明的搜索和知识,从作者言论和Rybka反映的信息做一个猜测(nps超低,搜索准确度超高),一致认为Rybka在搜索和评估中,都采取了全新的方法
其中一个流派3moves现在被认为是Rybka最有可能采取的方法(包含了我的理解补充)
什么是3moves?首先当前盘面移动一步,对可以攻击的子,计算3步内可以攻击的点集,这个点集每个点都有权重.那么多个攻击子做交集的时候,密度最高权重最高的区域,就是当前盘面最容易攻击的位置,这表明了这一个棋步的攻击能力
当这个棋步能攻击到王或者其他子时,这自然就是一个好的棋步,这时候根据点集的情况进行算分,自然是非常准确的.
这种方法超越了子力表和知识分数的局限,而且更好理解了棋规,也难怪被认为是最有可能的
以上转载不知是否你想要的？
