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 <= NullReduction+1 || eval(board) >= beta)) { // 根据距离叶子或者alpha,beta搜索中,棋形的评估进行控制

我想, 对上面的控制条件,大家都是很好理解的, fruit中NullRedcution==3, 这个可以理解为fruit审局做得比较完善,depth<=4进入审局搜索盘面评估的结果, 逼近搜索的结果, 而eval则是对depth>4时候剪枝的控制条件,这种控制条件往往是根据棋形进行控制, 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会做一个nullmove verify的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的history pruning

要了解history pruning, 首先建议参考国象中成熟的算法lmr (late move reduction)的论述

fruit对lmr引入了history value,并且对搜索结果做了verify,有效避免了lmr曾经的fail high的问题

这里就不对history pruning的限制条件做详细的阐述了,实际上这种防止危险的检查方法和nullmove的限制是类似的,而且会根据不同引擎知识和搜索结合的特点而存在差异

history pruning经实践证明, 是一种非常有效的剪枝方法, 并且绝对不会对棋力有降低的影响(其实根本原因是不会漏掉杀棋步)

history pruning根据国外的测试,能够提高elo 100,旧版的crafty并没有history pruning

e. fruit的hash实现方法

fruit的hash实现方法,经实践,大概比crafty的方法提高了5%~10%的性能

fruit对每个盘面,保存了一个上界和一个下界,如果对一个盘面搜索时,发现该盘面的搜索范围上界比过往的下界都要小, 则返回保存的下界, 如果发现搜索范围的下界比保存的上界要大, 则返回保存的上界, 如果发现盘面落入保存的窗口中, 则当保存的上界和下界重合而且搜索深度比当前搜索深度更深时, 返回保存的结果

这种hash的处理方法,修正了crafty中,只能对单边情况保存的不足, 有效提高了效率

需要注意的地方是, 在iterative search中, 每次fruit都会把搜索出来的PV路径都保存到hash中,这是用于取步(不是取值), 还有,在处理hash冲突时候, fruit使用了多个cluster的方法...需要细究的细节很多, 大家有兴趣可以仔细看看fruit的实现

f. fruit的search root move list

fruit对每次搜索后对root节点记录分值,并根据分值重新排序,以便下一次使用,当棋步产生振荡的时候(在两个棋步之间徘徊)会有效提高引擎的搜索效率

g. fruit的FAIL SOFT

嗯, 关于FAIL SOFT以及实践的方法, 可以参考纵马奔流的论文和fruit的代码, 我就不再无聊多说一次了..

3. fruit 2.1和TogaII1.2.1的差异,elo 100的差距原因

首先需要说明的是,我是用diff的方法,比较两者在搜索实现上的差别的, 应该是没有遗漏的

两者的差别列举如下

a. 延伸的差异, 根据特定棋形做了depth+1的搜索, 也就是越搜反而越深(当然TogaII有手段防止过深)

b. 剪枝的差异, 包括打开futility, delta, 并且对底层也做了history pruning

c. 对棋步稳定的盘面(只产生一个PV路径), 用渴望窗口搜索, 减少搜索量

d. 对危险情况的搜索的加强

两者差异原理分析

简单概括TogaII的改进,那就是利用国际象棋的知识调整了fruit的搜索树,对危险的盘面进行了更深的搜索,否则就剪掉.

首先，TogaII最有效的改进，是在叶子附近，利用history value把证明曾经无效的叶子节点丢弃掉，这是一个非常有效的算法，这里面的道理值得我们深思？为什么我们不能够发现一个这样的算法呢？

如果光是观察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. history pruning改进

考虑下面的情况

[炮]吃车1, 车2吃[炮], 车2移动, 和车1移动, 这两个棋步, 会引起同样的history value的减少, 虽然限制了history pruning发生在不吃子的情况, 但是, 中象的交换频率远>国象, 这种情况对fruit中historyvalue<9830就剪枝(60%)显然不适合, 因为中象发生上面的情况要高多了, 而historyvalue<9834(60%)只要该棋步有一次被检索的情况就会发生, 这个时候, 修正historyvalue<16384*45%, 可以有效减少误判

c. futility剪枝及delta剪枝的意义分析

嗯, 这个, 首先参考TogaII和fruit对比的文章

futility和delta, 如果不会漏掉杀棋步, 或者, 在不会被对方杀死的情况, 非常有助于扩大自己的子力优势, 这是这两个剪枝法的机制决定的(注意，这两个剪枝法的依据是扩大子力优势，所以适用的范围是有限的，对双方对杀的盘面是会削弱攻击能力的)

我建议使用这两个剪枝法, 当然是建立在调整过搜索树以后(避免在容易引发杀棋的盘面使用，常见的手段是判断kingsafety，是否处于被攻击状态中)