我想, 对上面的控制条件,大家都是很好理解的, 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，是否处于被攻击状态中)
d. 棋步排序的改进
从PVS搜索的原理出发, 搜索效率取决于搜索次序
常见的棋步排序是历史步->吃子步->killer->etc, 这是基于最大化子力优势的搜索, 当对杀时, 这种搜索排序效率是非常低的.
考虑killer棋步,如果能够发生一个killer步的分数是杀棋步,那么调整棋步排序为历史步->killer->吃子步->etc,这样就很好地把杀棋和吃子都结合起来了
5. fruit算法和象眼的差异, 如何提高象眼的棋力
通过本篇的介绍, 希望能够把开源的象眼程序, 改进到一个全新的高度, 假如有人希望一起完成象眼的改进, 请站内和我联系
下面是我认为可以有效提高象眼棋力的几个地方
a. 基于PV节点的nullmove pruning
b. qs加强
c. History pruning及TogaII剪枝法
d. 棋步排序
e. hash的改进
f. IID算法修正
g.search root move list
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步内可以攻击的点集,这个点集每个点都有权重.那么,多个攻击子做交集的时候, 密度最高权重最高的区域, 就是当前盘面最容易攻击的位置, 这表明了这一个棋步的攻击能力
当这个棋步能攻击到王或者其他子时, 这自然就是一个好的棋步,这时候根据点集的情况进行算分,自然是非常准确的.
这种方法超越了子力表和知识分数的局限, 而且更好理解了棋规, 也难怪被认为是最有可能的.
水鱼 ：如果能够， 尽量提供转帖来源
[ 本帖最后由 水鱼 于 29-8-2006 12:41 PM 编辑 ] |
本周最热论坛帖子
发表于 29-8-2006 11:58 AM
变色卡
千斤顶
楼主
2355 
32
