|
|
人工智能系列--中象搜索引擎揭密：
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(late move reduction)--如变种:fruit的history
      pruning, 控制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理解是非常深刻的.
       V节点的定义大家可以查查相关资料, 既然PV节点表示正确的搜索结果, 那么就肯定不应该剪掉. 同样,对于不是PV节点的,
      就不会找出正确的搜索路径, 这就应该剪掉.这个也是fruit剪枝的理论依据。
      道理是这样说, 但是我们一开始并不知道每一个节点的类型, 所以在搜索的时候, 会假设某个节点不是PV节点, 然后看它是否会fail,
      如果fail,再做PV节点的搜索.
      假如这种假设是成立的,
      那么就成功完成了对该非PV节点路径的剪枝,否则,需要重新搜索,因为对PV节点假设判断的搜索是做windows=1的搜索,所以耗费的代价是很低的.
      下面来看看fruit的实现方法,我认为fruit对PV节点理解的实现方法非常优雅.
      int search_root()
      {
        本节点做PV搜索
        if (树根节点并且首节点)
           下一层节点为PV节点 // 这个时候还没有找出PV路径,所以必须做PV节点搜索
        else
        {
           下一层节点做假设不是PV节点的搜索
           if (fail)
              下一层节点做PV节点的搜索
        }
      }
      int search_full()
      {
        根据上一层对该节点的判断, 进行节点搜索
        if (首节点 || 假设不是PV节点的搜索) // 当假设不是PV节点时,
      windows=1这个时候不应该假设,应该直接计算了,否则就是重复计算浪费时间
           下一节点的节点类型跟本节点类型一致
        else
        {
           下一层节点做假设不是PV节点的搜索
           if (fail)
              下一层节点做PV节点的搜索     
        }
      }
      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的方法,比较两者在搜索实现上的差别的, 应该是没有遗漏的
     作者：fenon |
|
发表于 2013-10-25 14:10:54
