人工智能系列--nullmove

 

#1  Nullmove 实战剖析

int attackpieces = (side==RED?(Rattackpieces) : (Battackpieces));

  int nulldepth = CtrlNullEx ? 4 : 3;

if (CtrlNullmove
        && !NullVerify
        && !InChk[ply]
        && !mate_threat
        && attackpieces        > 0
        && !avoid_donull
        && depth>=2
        && (depth-nulldepth<=0 || zEval(side, ply, 0)>=beta)
        && do_null)
{ // 控制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
                        && !mvsLast.bcCheck
                        && Tree.pos.NullMoveOkay()
                        && nDepth>1
                        && (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启发剪枝