<P><A href="http://hi.baidu.com/whhha/blog/item/f27eb0d386fd9fdea8ec9a1f.html" target=_blank>http://hi.baidu.com/whhha/blog/item/f27eb0d386fd9fdea8ec9a1f.html</A></P>
<P> </P>
<P>象棋引擎的主攻方向有速度型和知识型</P>
<P>假设两个引擎的起点一样（主搜索算法和审局一样），这个时候，如何进一步发展引擎？</P>
<P>1、采用剪枝算法或者精简审局<BR>2、加大知识</P>
<P>我把第一种方法归为速度型，第二种归为知识型</P>
<P>两个起点一样的引擎，引擎A是速度型发展，引擎B是知识型发展，经过一段时间后，他们会有这样的差别</P>
<P>引擎A比引擎B多搜索一层，引擎B的每一步棋步质量比引擎A高</P>
<P>假设低层时多搜索一层的价值为1，同时，随着层数的增加，价值开始递减（例如，高层14层对15层，多一层的价值为0.2）</P>
<P>在这个时候，引擎B每一步的搜索质量分数多增加了0.1</P>
<P>这时候，知识型和速度型对上了，他们的胜负结果如下：<BR>1. 速度型的引擎A在层数较低（如8层）时，每一次搜索比引擎B多0.2分，毫无疑问，这个时候速度型引擎A在多次棋步积累后会战胜引擎B<BR>2. <BR>知识型的引擎B在层数较高时（如10层），每一次搜索比引擎A多0.2分（层数效应衰减导致10层时多搜索一层只有0.8分，而每一层引擎B的积累分数为0.1分），同样引擎B胜出毫无疑问</P>
<P>上面的是一个抽象的模型，但是基本能通过这个模型，解释为什么一些引擎慢棋厉害，一些引擎快棋厉害</P>
<P>所以，我得出以下一些结论：<BR>1、引擎纯速度的提高，随着硬件的发展，空间是有限的<BR>2、剪枝算法，如果太多，快棋效果较好，慢棋是得不偿失<BR>3、搜索算法上面的突破永远是最有效的提高方法<BR>4、知识越多，快棋越差，慢棋越好</P>
<P>这让我多少明白到，为什么我的引擎，超快棋（3+2）怎么也下不赢对手，而快棋（10+3）能抗衡对手，到了慢棋能战胜对手的原因</P>
<P>近曰和旋风、骑兵进行了UCCI对局测试，10+3的结果还是令人满意的，虽然不敢说超越对手，但是差距<BR>是很小的，这些天继续测试，修改提高一下</P>
<P>虽然因为旧引擎本身的问题，无法提高纯速度，但是结症已经找到，相信下一版本就能取得突飞猛进，<BR>目前先把一些问题修正一下，并且编写相关的操作界面和工具，没有界面是没法用的</P>
<P>假如条件允许，会编写下一版的引擎，全面提高nps和支持并行搜索，只是以目前的状况来看，暂时无法动手</P>
<P><BR>2007.2.15 13:21 作者：fenon 收藏 | 评论：0<BR>中国象棋软件的点滴<BR>分类:默认栏目从2004年, 走在世界的前列, 编写象棋软件开始, 到2006年, 学习研究并改写全新的引擎, 已经是三年多的时间, 这三年, <BR>是一个技术/思维从粗糙到成熟的过程, 获益良多.<BR><BR>这段时间写了很多文章, 转载在各大网站/论坛上, 可惜已经如风中的铃声, 消失在时间中, 现在摘录的一些, 作为一种回忆, 保存起来.<BR><BR>在编写象棋软件的期间, 得到象棋世家创始人Poor的帮助, 得到朋友raylau和face的支持, 谢谢他们.<BR><BR>在编写象棋软件的期间, 认识了纵马奔流, 象棋奇兵, 棋天大圣, 还有现在的新起之秀象棋旋风, 天机, 象眼, 是他们让我在一次又一次的自我挑战中, <BR>不断完善自己.<BR><BR>回想起自己所编写的软件战胜旧一代棋软巨头的时候, 我也明白我的程序, 总有一天也会被淘汰, 消失在人们的眼中, 这是历史发展的必然, 自然会有更好更新的软件, <BR>出现在人们眼前.<BR><BR>感谢所有为中国象棋软件做出努力的人们, 愿棋软常青.<BR>2006.12.4 08:20 作者：fenon 收藏 | 评论：0<BR>人工智能系列--nullmove<BR>分类:默认栏目#1   Nullmove 实战剖析</P>
<P>       int attackpieces = (side==RED?(Rattackpieces) : (Battackpieces));</P>
<P>         int nulldepth = CtrlNullEx ? 4 : 3;</P>
<P>       if (CtrlNullmove <BR>               && !NullVerify <BR>               && !InChk[ply]<BR>               && !mate_threat <BR>               && attackpieces         &gt; 0<BR>               && !avoid_donull<BR>               && depth&gt;=2<BR>               && (depth-nulldepth&lt;=0 || zEval(side, ply, 0)&gt;=beta)<BR>               && do_null) <BR>       { // 控制nullmove的危险程度</P>
<P>               null_score = -zSearch(-beta, -beta + 1, 1 - side, depth - <BR>       nulldepth, ply + 1, false/*do_null = false*/);</P>
<P>               if (null_score &gt;= beta)<BR>               {<BR>                       {<BR>                               bool verifyok = false;</P>
<P>                               // null-move verify<BR>                               if (depth &lt; nulldepth) <BR>                                       verifyok = true;<BR>                               else<BR>                               {<BR>                                       NullVerify = true;</P>
<P>                                       if (zSearch(beta-1, beta, side, <BR>       depth-nulldepth+1, ply, false) &gt;= beta)<BR>                                               verifyok = true;</P>
<P>                                       NullVerify = false;</P>
<P>                                       ///* <BR>                                       if (verifyok) {<BR>                                               StoreHash();<BR>                                       }<BR>                                       //*/<BR>                               }</P>
<P>                               if (verifyok)<BR>                                       return (null_score);<BR>                       }<BR>               }</P>
<P>               else if (null_score == -vMate + ply + nulldepth)<BR>                       mate_threat = 1;<BR>       }</P>
<P>nullmove是一种有损剪枝, 会带来一些不准确的结果, 所以控制nullmove的危险程度是很有必要的</P>
<P>在何种条件下可以进行nullmove? 我的实现算法中, 采取了以下几种限制<BR>1. 攻击子&gt;0 <BR>2. depth&gt;=2 最后一层直接剪掉是非常危险的<BR>3. 不被将军<BR>4. 上一层已经做了nullmove, 本层就不再做了<BR>5. 当校验nullmove是否正确时,不再使用nullmove<BR>6. 当同样的盘面,以前曾经使用过nullmove,并且发现被对方杀死时(参考crafty)<BR>7. 层数比nulldepth要大, 或者优势很大时 (参考fruit)<BR>8. avoid_donull发生在如果保存在hash表中有记录,但是却不能返回结果时</P>
<P>其中7是相当好的一种限制条件, 比通过子力的多少来进行限制有效得多</P>
<P>因为nullmove的危险性, 需要测试nullmove结果是否正确, 通过统计, 子力多的时候, 基本不会出现verify失败的结果, <BR>这多少也印证了crafty中, 采用子力多少进行nullmove限制的原因</P>
<P>nullmove的verify是通过层数多一层的搜索来校验的方法来校验, 所以<BR>depth小于nulldepth时,可以认为不需要校验<BR>(考虑这个时候计算的结果跟nullmove搜索结果的比较)</P>
<P>nullmove搜索的结果可以保存重用(参考crafty)</P>
<P>这里对象眼nullmove的实现, 提几点建议</P>
<P>                 if (Search.bNullMove <BR>                         && !bNoNull <BR>                         && !mvsLast.bcCheck <BR>                         && Tree.pos.NullMoveOkay()<BR>                         && nDepth&gt;1<BR>                         && (nDepth-NULL_DEPTH-1&lt;=0 || Tree.pos.Evaluate(vlAlpha, <BR>vlBeta)&gt;=vlBeta)<BR>                         )<BR>                 {<BR>                         Tree.pos.MakeMove(0);<BR>                         vl = -SearchFull(Tree, -vlBeta, 1 - vlBeta, nDepth - <BR>NULL_DEPTH - 1, NO_NULL);<BR>                         Tree.pos.UndoMakeMove();<BR>                         if (vl &gt;= vlBeta)<BR>                         {<BR>                                 if (Tree.pos.NullMoveSafe() || <BR>nDepth&lt;=NULL_DEPTH || SearchFull(Tree, vlBeta - 1, vlBeta, nDepth - NULL_DEPTH, <BR>NO_NULL) &gt;= vlBeta)<BR>                                 {<BR>                                         return FAIL_SOFT ? vl : vlBeta;<BR>                                 }<BR>                         }<BR>                         else if (vl == nThisPly + 2 - MATE_VALUE)<BR>                         {<BR>                                 bMateThreat = TRUE;<BR>                         }<BR>                 }</P>
<P>其中的关键是(nDepth-NULL_DEPTH-1&lt;=0 || Tree.pos.Evaluate(vlAlpha, vlBeta)&gt;=vlBeta), <BR>这样可以避免很多危险的情况, 使用了nullmove启发剪枝</P>
<P>2006.12.4 08:16 作者：fenon 收藏 | 评论：0<BR>人工智能系列--如何测试<BR>分类:默认栏目#1   如何测试你的引擎</P>
<P>引擎的测试枯燥无味，而且需要花费大量的时间，在这里提供一些方法，希望能够帮助大家减少无谓的工作量，多一点享受生活的机会。</P>
<P>首先，引擎的测试，需要有参照物，一个成熟的坐标，是成功的关键，我推荐象眼，开源的帮助是巨大的，你可以对他做出自己喜欢的定向修改，提取自己喜欢的数据。</P>
<P>1. 引擎的实现次序应该是: 框架（保证速度）-&gt;引擎-&gt;审局。<BR>一般来说，如果nps差别没有几倍，是引擎的棋力还是相当接近的，我测试nps提高30%~50%，在对战中，胜率的比例变化不大，所以，首先保证你的引擎，nps和别人接近吧，注意，这里的nps指纯子力表nps</P>
<P>2. <BR>开始引擎的测试了，首先，把审局去掉，然后，减少加速的方法，嗯，尽量把可变因素降低吧，跟着，开始测试2分钟限时，5分钟限时，10分钟限时的胜负比率，你会发现，原来时间对胜负比率的影响是有限的，OK，选一个最短时间做为测试样本吧。</P>
<P>2.1 <BR>对中断的测试，引擎出步，限制时间，会引起中断，但是中断往往会耗费大量的无效时间，控制不要中断，中断的计算是无效的，根据当前情况，决定是否需要下一层计算吧，这样才能提高测试的准确度</P>
<P>2.2 注意搜索的节点数，这个是考察测试有效度的重要指标，都只采用子力表，搜索10层，别人只用了你的1/3节点数，你不应该怀疑自己的搜索效率么？</P>
<P>2.3 测试fhf，即第一棋步返回率，OK，这个指标应该可以高达90%以上，当然70~80%的fhf对棋力影响也不会太大，但是，你的搜索效率是不高的，对么？</P>
<P>2.4 注意quiet节点和fullsearch节点的比例，这两者的比例可以进一步提高搜索的准确度，不要让无聊的剪枝，影响了这两者的比例</P>
<P>2.5 把盘面和搜索路径打印出来，并且可以恢复，这样才可以连续测试，并且比较自己引擎和别人引擎的分析差别</P>
<P>2.6 利用对战工具，看看自己的对战失败原因吧！是一直被别人压着打，还是突然跳水？哦，如果跳水，那就是剪枝出问题了，别人搜索到了一个你没能搜索到的棋步</P>
<P>2.7 .... </P>
<P>3 当引擎成熟以后，再尝试添加审局吧！</P>
<P>2006.12.4 08:15 作者：fenon 收藏 | 评论：0<BR>人工智能系列--一些技巧心得<BR>分类:默认栏目#1   棋软实现的一些技巧心得</P>
<P>一直以来都很想把自己积累的心得发表出来，和大家一起共享，希望能够促进棋软的发展，感谢elephantbase提供这样的一个传播空间</P>
<P>组成棋软的几大核心:<BR>1. 开局库<BR>2. 计算<BR>3. 审局</P>
<P>开局库对棋软的帮助非常大，很多引擎之间对战，成绩接近，但是一配合开局库，差异就拉大了，根据个人经验，开局库的质量，会影响对局的30%左右的成绩。考虑到引擎的特点不同，需要调整开局库，引导盘面进入适合自己计算的盘面，一般来说，引擎的大都有如下倾向：1.善守；2.善攻，毫无疑问，对于善守的引擎，盘面拉入双方接近的粘滞情况，对于善攻，盘面拉入双方互有机会的盘面，都是很有帮助的</P>
<P>计算是引擎的重要组成部分，也是大家考虑最多的，本人在理论的研究上比较肤浅，就只谈谈实现的技巧吧</P>
<P>1. <BR>如何加速引擎：假如统计过引擎内访问的节点，我们很容易就知道，访问次数最多的节点是静态quiet节点，其次是fullsearch节点，那么让我们来看看，组成quiet节点和fullsearch节点最重要的函数是什么？在我的引擎里面，访问次数最多的是Incheck(), <BR>genmove(), gencap(), domove(), <BR>undomove()，如果评估函数eval()占的比例很大，评估函数的比例也是很重要的。学过计算机的一些基础理论应该知道，赋值操作&gt;判断语句&gt;函数调用，所以，在上面的几个函数，需要避免函数调用（如：不要用包含构建函数的数据类型，尽量内联等），减少判断，这样就可以加速引擎了。</P>
<P>1.1 <BR>domove()和undomove()里面的操作基本上是赋值操作，但是考虑到context，很多人习惯在domove()和undomove()里面保存每一个棋步的上下文变化，某些上下文并不是必要的，请把这些不需要的上下文去掉。</P>
<P>1.2 eval(), incheck(), genmove(), <BR>gencap()里面包含了大量的棋子关系判断和棋步生成判断，加速这些函数最佳的方法是，把去掉棋子关系判断以及利用棋步预生成技术。if <BR>(!colour_is_same()) addeat(); 这样的做法，可以通过idx = colour1^colour2, <BR>生成一个标志，把对应的数据放到对应的数据空间即可. 即上面的代码可以变成 move_eat[idx];这样就可以方便区分开棋步，同时也去掉了判断</P>
<P>1.3 用尽量少的数据，表达更多的内容。现在bitfile, bitrank技术相当的流行(当然这离不开eleeye的开源的帮助), <BR>bitfile和bitrank技术，有效减少了车炮棋步的判断次数，对nps的提高有50%的帮助，这是一个很典型的用尽量少的数据表达更多内容的例子。表达棋盘的基本元素colour, <BR>piece, square(坐标), move都建议尽量用bit位，这种帮助是很明显的。</P>
<P>1.4 bitboard对eval()的帮助。bitboard本身就包含了bitfile, <BR>bitrank的信息，所以bitboard可以很方便实现车炮的预计算（bitboard可以通过维持一个按行排列，一个按列排列的组合来实现bitfile, <BR>bitrank），bitboard在表达棋子之间的模糊关系时，有强大优势。考虑到目前的机器大都是4字节对齐，32bit，建议用4个32位来表达一个bitboard，这样可以很好处理棋步</P>
<P>2. <BR>保持引擎的计算的稳定，少用剪枝。现在机器已经发展到一定的高度，引擎的计算层数，已经相当的深，所以，避免因为剪枝而错失关键棋步，已经成为引擎的一个重要组成元素。在我实现的引擎中，有损剪枝法，只用nullmove，这样可以大幅度提高引擎对抗的能力。棋软也有一个木桶理论，最差的棋步，决定棋软的水平，</P>
<P>2.1 <BR>机器速度提高的帮助，在目前来看，机器速度的提高，才是引擎最快的提高方法，虽然有点无奈，但这是一个事实，引擎辛苦调出来5%的节点节省，随便用个好点的机器，就已经可以弥补了，不要轻视机器的差别，举个例子，在有损的情况下nullmove节省了50%的节点，但是机器提高20%~30%的速度，就完全可以达到同样的效果</P>
<P>2.2 避免出错。hashtable或者history, <BR>killermove的棋步，一些实现方法都会导致棋步不可用，这必须对棋步的合法性做出判断，这些一旦出错，直接导致致命错误，类似的还有内存访问的问题</P>
<P>2.3 提高准确度。在quiet节点的评估，可以在王被将军或者不被将军两种情况下，进行评估，我采用了一直走到王不被将军和无吃子的盘面进行评估。</P>
<P>2.4 <BR>nullmove，这是重点中的重点，我建议参考fruit2.1(国象引擎)中，对nullmove的实现方法，毫无疑问，fruit的实现方法非常优秀，而且很值得玩味。nullmove需要verify，这是保证nullmove质量的一个关键手段。</P>
<P>2.5 棋步排序，我采取的棋步排序是根据当前盘面是否被将军来排序，如果被将军，次序为hashmove-&gt;eat <BR>attacker-&gt;kingmove-&gt;left, 否则，采用hashmove-&gt;matekiller-&gt;win <BR>capture(小吃大)-&gt;goodcapture(吃没有保护的子)-&gt;killermove-&gt;capture-&gt;history-&gt;left，对棋步排序一个很有意义的指标是fhf，即第一节点返回率（参考crafty），棋步排序对计算质量的提高是非常明显的。</P>
<P>2.6 alpha-beta和pv节点，不同的节点，采取不同的搜索方法和剪枝方法，请参考fruit的实现方法，非常优雅。请保证自己能够理解这个概念。</P>
<P>2.7 <BR>延伸，将军延伸是必要的，其他的延伸有一定的帮助，但是效果未必很好，在crafty中，matethreat延伸只有3/4将军延伸的价值，recapture的价值也被降低，这部分需要大量的测试工作。</P>
<P>2.8 其他的一些可以加速的算法，如internal iterative deepening等，对加速未必会非常明显，所以我只使用了iid.</P>
<P>3 审局<BR>审局是对盘面的评估，这就需要保证审局的知识是准确的，虽然审局可以不全面，但是，使用了错误的知识，必然会导致问题</P>
<P>在我的审局模型中，我对审局划分为包括棋型/倾向性引导/王威胁三种评估</P>
<P>3.1 <BR>审局的作用，当引擎稳定后，对杀棋棋步进行测试，我们会发现，能否搜索出杀棋，跟引擎是息息相关，跟审局则是关系不大，但是，盘面危险度的认识，却跟引擎息息相关，所以，我们得出一个结论，审局，只是评估危险度，不要让审局承担提前发现杀棋的工作，多在引擎本身找找原因</P>
<P>3.2 <BR>王威胁&gt;倾向性引导&gt;棋型。我把棋型定义为子的摆放位置，倾向性引导定义为子力组合和运子方向，王威胁是对9宫的进攻情况。三者分数如上所述。很多棋型的合理性，在使用了子力表后，在计算中是可以体现出来的，但是，单车和单车士象全这种子力组合，却是无法通过子力表得知的。</P>
<P>3.3 王威胁模型，考虑下图：<BR>    |    |    |<BR>---+--+--+---<BR>---|---+--|---<BR>---+--+--+---<BR>    |    |    |<BR>假如王所在的9宫，是在棋盘的中心，而且兵的方向可以4周移动，那么，车马炮兵对9宫的威胁，是4个方向等价的</P>
<P>但是在实际棋盘中，因为规则限制的原因，9宫在4个方向受到的威胁是不同的，这就表示，棋子的移动方向，对王的威胁有影响</P>
<P>我们知道，车炮受到的影响是较少的，而马兵则很大，分析表明，马到了两边，可以踩到的9宫点明显减少，同理，兵也是，而车炮能踩到的9宫点，则不会变化太多</P>
<P>所以，我们可以得出一个推论，子对9宫的攻击点越多，那么，对王的威胁越大。</P>
<P>我们再来看看防守子，当象挡住了车照王，车对9宫的攻击点只有一个！所以，在我的模型里面，防守子的意义，在于减少对9宫的攻击点！</P>
<P>即，对9宫的威胁，通过攻击点的个数和程度来表示。例如，(炮)-&gt;(车)-&gt;[士]-&gt;[王]，这样对9宫的攻击点有两个，因为车炮都双重攻击，所以被攻击的两个点的威胁度很高，(炮)-&gt;(马)-&gt;[士]-&gt;[王]可以有4个攻击点，但是威胁度都比较低，子力组合可以跟攻击点的威力有一定挂钩。</P>
<P>由此，抽象出一个模型，王被威胁的程度=f(进攻的子力组合,进攻的点)，对王的威胁评估，只需寻找出上述两个参数，即可查表得知目前被威胁的程度</P>
<P>这种评估是想相当准确的。</P>
<P>3.4 <BR>子力组合和运子，当无法对王造成威胁时，子力组合和运子就非常重要了，运子在特定盘面，都有一定的倾向度，所以，搜索前通过调整子力表，即可对运子造成影响，当然，需要准确评估还是eval()可靠，如兵卒的分数调整。子力组合的情况，子少时，就是残局了，中局时，车马马是不如车马炮的，这些都需要有一定提示。</P>
<P>3.5 <BR>评估的准确，空头炮在子力充沛时，分数很高，但是子力减少，则威力降低。很多人的空头炮就采用了上述方法进行评估，如果按我的模型来算，则是因为子力减少，导致王威胁出现的机会降低，所以，空头炮如果子力很多但是无法舒展，还强行保持空头炮，会很危险。这就涉及审局准确度的问题。即，多高概率的事件可以采用模糊评估？</P>
<P>上面是我对棋软的一些认识，希望能对大家有帮助。因为本人的理论水平不高，用词不准确，对此抱以万分歉意。</P>
<P>北京大赛终于过去了, 在这场盛事前后这段时间, 静下心来回顾了走过的象棋研究的路子,心得感触良多.为了纪念这段时间的美好, <BR>我决定把这段时间积累的对象棋引擎的心得, 总结分享出来</P>
<P>我个人希望通过这篇文章,把一些顶尖棋软的知识普及开来,提高开源象棋软件的水平.</P>
<P>1. 搜索引擎和审局之间的关系, 如何建立</P>
<P>阅读下面的内容时, 首先需要了解几个背景知识<BR>a. 人工智能的博弈搜索树和PVS搜索之间的关系<BR>b. PVS搜索是无损搜索<BR>c. PVS的搜索效率和搜索次序的关系</P>
<P>首先明确几点:</P>
<P>a. 做一个全PVS的搜索, 在限定了层数的情况下, 如果基于不正确的知识(比如子力表),并不能保证一定能把杀棋找出来(可能会跑去吃子)<BR>b. 为了提高棋力, 无损搜索PVS是不足够的, 还是需要剪枝的<BR>c. 搜索树和审局之间的关系, 首先知识必须能够引导搜索到正确盘面(这个地球人应该都知道), <BR>第二是避免搜索把正确的分支剪除掉(这个谈论得少一些,我以前曾经有很长一段时间不知道)</P>
<P>我认为, 审局和搜索之间的关系的建立, 在于<BR>a. 知识是带有正确的倾向性的(只能说是倾向性,因为知识很难做到全面准确)<BR>b. 搜索是根据知识而采取剪枝方式的(这个下面详细分析)</P>

下面我举一个简单的例子, 来说明知识和搜索之间的关系
    帅
   
     _____
     |   |    |
马_| 将_|_兵
     | _| _|_象

在这个盘面, 兵只要靠近王一步, 就可以将死了对方, 但是基于子力表做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理解是非常深刻的.

PV节点的定义大家可以查查相关资料, 既然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的方法,比较两者在搜索实现上的差别的, 应该是没有遗漏的

两者的差别列举如下
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步内可以攻击的点集,这个点集每个点都有权重.那么,多个攻击子做交集的时候,
密度最高权重最高的区域, 就是当前盘面最容易攻击的位置, 这表明了这一个棋步的攻击能力

当这个棋步能攻击到王或者其他子时, 这自然就是一个好的棋步,这时候根据点集的情况进行算分,自然是非常准确的.

这种方法超越了子力表和知识分数的局限, 而且更好理解了棋规, 也难怪被认为是最有可能的.


在过去研究象棋引擎/人工智能的过程中, 有一份恬然/投入的精彩

开技术例会有以下好处:
1. 总结最近项目的技术情况, 提高技术水平
2. 学习最新的技术热点
3. 促进团队交流 (交流和培训同步进行)
4. 每周5下班前两小时举行, 有效提高工作效率

开技术例会的一些注意:
1. 避免大范围在项目中期引入新技术, 特别是框架层次, 模块级别可以适当引入
2. 需要长期的组织, 依赖某些人的热情和爱好
3. 注意长期的笔记积累, 分析哪些技术已经讲过, 哪些技术没有
4. 每次例会前, 项目经理/技术经理需要明确是否包含以下内容
    a. 项目进度
    b. 讨论的技术内容
    c. 下一次例会内容
5. 下一次技术会议内容, 欢迎每一个开发成员都积极发言
6. 有时候, 例会可以在外面的餐厅开一下的

2006.11.23 08:45 作者：fenon 收藏 | 评论：0
   关于速度型和知识型引擎的思考
   代号为qstar的新引擎诞生了
   中国象棋软件的点滴
   人工智能系列--nullmove
   人工智能系列--如何测试
   人工智能系列--一些技巧心得
   人工智能系列--中象搜索引擎揭密
   介绍一下我曾经编写过的象棋软件程序
   该曰志已被锁定
   从一个管理者的角度看定时技术聚会