|
|
编者注：
fenon，原名应为叶剑锋，棋海无涯界面作者，曾获世界奥林匹克大赛第四名。
中国象棋软件的点滴
      从2004年, 走在世界的前列, 编写象棋软件开始, 到2006年, 学习研究并改写全新的引擎, 已经是三年多的时间,。这三年, 是一个技术/思维从粗糙到成熟的过程, 获益良多。           这段时间写了很多文章, 转载在各大网站/论坛上, 可惜已经如风中的铃声, 消失在时间中, 现在摘录的一些, 作为一种回忆, 保存起来。
    在编写象棋软件的期间, 得到象棋世家创始人Poor的帮助, 得到朋友raylau和face的支持, 谢谢他们。在编写象棋软件的期间, 认识了纵马奔流, 象棋奇兵, 棋天大圣, 还有现在的新起之秀象棋旋风, 天机, 象眼, 是他们让我在一次又一次的自我挑战中,不断完善自己.             回想起自己所编写的软件战胜旧一代棋软巨头的时候, 我也明白我的程序, 总有一天也会被淘汰, 消失在人们的眼中, 这是历史发展的必然, 自然会有更好更新的软件, 出现在人们眼前。感谢所有为中国象棋软件做出努力的人们, 愿棋软常青。
      2006.12.4 08:20 作者：fenon
      人工智能系列--nullmove
        Nullmove 实战剖析
            int attackpieces = (side==RED?(Rattackpieces) : (Battackpieces));
              int nulldepth = CtrlNullEx ? 4 : 3;
            if (CtrlNullmove
                    && !NullVerify <BR>                    && !InChk[ply]<BR>                    && !mate_threat <BR>                    && attackpieces        > 0<BR>                    && !avoid_donull<BR>                    && depth>=2<BR>                    && (depth-nulldepth<=0 || zEval(side, ply, 0)>=beta)
                    && do_null) <BR>            { // 控制nullmove的危险程度
                    null_score = -zSearch(-beta, -beta + 1, 1 - side, depth -
            nulldepth, ply + 1, false/*do_null = false*/);
                    if (null_score >= beta)
                    {
                            {
                                    bool verifyok = false;
                                    // null-move verify
                                    if (depth < nulldepth)
                                            verifyok = true;
                                    else
                                    {
                                            NullVerify = true;
                                            if (zSearch(beta-1, beta, side,
            depth-nulldepth+1, ply, false) >= beta)
                                                    verifyok = true;
                                            NullVerify = false;
                                            ///*
                                            if (verifyok) {
                                                    StoreHash();
                                            }
                                            //*/
                                    }
                                    if (verifyok)
                                            return (null_score);
                            }
                    }
                    else if (null_score == -vMate + ply + nulldepth)
                            mate_threat = 1;
            }
      nullmove是一种有损剪枝, 会带来一些不准确的结果, 所以控制nullmove的危险程度是很有必要的
      在何种条件下可以进行nullmove? 我的实现算法中, 采取了以下几种限制
      1. 攻击子>0
      2. depth>=2 最后一层直接剪掉是非常危险的
      3. 不被将军
      4. 上一层已经做了nullmove, 本层就不再做了
      5. 当校验nullmove是否正确时,不再使用nullmove
      6. 当同样的盘面,以前曾经使用过nullmove,并且发现被对方杀死时(参考crafty)
      7. 层数比nulldepth要大, 或者优势很大时 (参考fruit)
      8. avoid_donull发生在如果保存在hash表中有记录,但是却不能返回结果时
      其中7是相当好的一种限制条件, 比通过子力的多少来进行限制有效得多
      因为nullmove的危险性, 需要测试nullmove结果是否正确, 通过统计, 子力多的时候, 基本不会出现verify失败的结果,
      这多少也印证了crafty中, 采用子力多少进行nullmove限制的原因
      nullmove的verify是通过层数多一层的搜索来校验的方法来校验, 所以
      depth小于nulldepth时,可以认为不需要校验
      (考虑这个时候计算的结果跟nullmove搜索结果的比较)
      nullmove搜索的结果可以保存重用(参考crafty)
      这里对象眼nullmove的实现, 提几点建议
                      if (Search.bNullMove
                              && !bNoNull <BR>                              && !mvsLast.bcCheck <BR>                              && Tree.pos.NullMoveOkay()<BR>                              && nDepth>1<BR>                              && (nDepth-NULL_DEPTH-1<=0 ||
      Tree.pos.Evaluate(vlAlpha, vlBeta)>=vlBeta)
                              )
                      {
                              Tree.pos.MakeMove(0);
                              vl = -SearchFull(Tree, -vlBeta, 1 - vlBeta, nDepth
      - NULL_DEPTH - 1, NO_NULL);
                              Tree.pos.UndoMakeMove();
                              if (vl >= vlBeta)
                              {
                                      if (Tree.pos.NullMoveSafe() ||
      nDepth<=NULL_DEPTH || SearchFull(Tree, vlBeta - 1, vlBeta, nDepth -
      NULL_DEPTH, NO_NULL) >= vlBeta)
                                      {
                                              return FAIL_SOFT ? vl : vlBeta;
                                      }
                              }
                              else if (vl == nThisPly + 2 - MATE_VALUE)
                              {
                                      bMateThreat = TRUE;
                              }
                      }
      其中的关键是(nDepth-NULL_DEPTH-1<=0 || Tree.pos.Evaluate(vlAlpha,
      vlBeta)>=vlBeta), 这样可以避免很多危险的情况, 使用了nullmove启发剪枝！
作者：fenon |
|
发表于 2013-10-25 14:01:16
发表于 2013-10-28 20:29:43
,,,,,,,,,,,
