Null move pruning

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Null move pruning

Post by cms271828 » Sat Sep 19, 2009 12:42 am

Hi, I haven't got round to implementing this, the last time I looked at it I got confused and left it.

Looking at http://web.archive.org/web/200404270146 ... llmove.htm
which seems to be the clearest example of nmp, I don't understand:
An excellent value of R is 2. So, if for instance you were going to search all of your moves to depth 6, you end up searching all of your opponent's moves to depth 4.
How can you search all your moves to depth 6? A search is both moves searched, and similarly for searching opponents moves.
All I can think it means is beginning with you to play, or beginning with opponent to play.

Looking at the code in blue, I can see that if val doesn't equal or excede beta, we don't return anything, and continue as normal to generate moves and search them, so in these cases the whole search done in blue would have been a waste of time.

Perhaps mathematically (not sure if this is valid).. supposing an effective branching factor of 10, then from that node, a search 6 ply deep will take 100 times longer than a search 4 ply deep, so if the code in blue returns a value more than 1% of the time, the whole search time will decrease.

And the chance of it returning is probably quite a lot higher than 1%, so I guess its worthwhile, but looking at it intuitively seems like it is gonna take up too much time.

Any thoughts? thanks
Colin

Dann Corbit
Posts: 11621
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Null move pruning

Post by Dann Corbit » Sat Sep 19, 2009 1:29 am

cms271828 wrote:Hi, I haven't got round to implementing this, the last time I looked at it I got confused and left it.

Looking at http://web.archive.org/web/200404270146 ... llmove.htm
which seems to be the clearest example of nmp, I don't understand:
An excellent value of R is 2. So, if for instance you were going to search all of your moves to depth 6, you end up searching all of your opponent's moves to depth 4.
How can you search all your moves to depth 6? A search is both moves searched, and similarly for searching opponents moves.
All I can think it means is beginning with you to play, or beginning with opponent to play.

Looking at the code in blue, I can see that if val doesn't equal or excede beta, we don't return anything, and continue as normal to generate moves and search them, so in these cases the whole search done in blue would have been a waste of time.

Perhaps mathematically (not sure if this is valid).. supposing an effective branching factor of 10, then from that node, a search 6 ply deep will take 100 times longer than a search 4 ply deep, so if the code in blue returns a value more than 1% of the time, the whole search time will decrease.

And the chance of it returning is probably quite a lot higher than 1%, so I guess its worthwhile, but looking at it intuitively seems like it is gonna take up too much time.

Any thoughts? thanks
Here is what Bruce is saying (my paraphrasal).
In our search we try a null move. If the null move search proves that a move is so bad that it is worse than doing nothing, then we reduce the search for this move only by Reduction_Factor, which in this case is 2 plies.

There are some caveats to null move pruning. The worst one is zugzwang positions. If your chess position is such that you wish you did not have to move, then you should not use null move pruning.

It is also hazardous when the board is nearly bare. So many chess engines do a check for a lightly populated board.

There are two well known solutions to safegard against bad zugzwang searches. There is verified null move search (by Omid David) where you go ahead and do a quick search to refute the move, and double null move technique (by Vincent Diepveen) which says that you can never do two null moves in a row. I like Vincent's solution as it is simple and clear.

So let's look at it from a human standpoint. Suppose that *you* are playing a game of chess. If you stick your queen in front of an enemy pawn, it's probably a very bad idea. So you won't ponder over that choice nearly as hard as what you consider the best idea available to you.

That is what null move pruning is for. If we decide that we are clearly worse off after we made a move than before it, it's probably not a very good move and so we won't spend as much time and energy thinking about it.

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Null move pruning

Post by cms271828 » Sat Sep 19, 2009 2:46 am

Thanks, I can see why being in check and zugzwang is bad for nmp.

I'm not sure if theres anything I need to do in MakeNullMove() and UndoNullMove(), and also where should I take the first null move, and how often should I use null move?

Thanks
Colin

Dann Corbit
Posts: 11621
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Null move pruning

Post by Dann Corbit » Sat Sep 19, 2009 3:06 am

cms271828 wrote:Thanks, I can see why being in check and zugzwang is bad for nmp.

I'm not sure if theres anything I need to do in MakeNullMove() and UndoNullMove(), and also where should I take the first null move, and how often should I use null move?

Thanks
A null move is a little different than a regular move so many people have a special make and unmake for them.

Make null moves as often as you like, and the more the merrier. Just look at how some others have successfully implemented them.

If you use double null move (Vincent's idea) and never make two in a row, you can use them with absolute impunity.

Null move is the next big breakthrough after Alpha-Beta compared to pure mini-max. You will get a boost in your search depth.

Dann Corbit
Posts: 11621
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Null move pruning

Post by Dann Corbit » Sat Sep 19, 2009 3:15 am

Here is Beowulf's search (not the world's strongest, but easy to understand):

Code: Select all

/* Do the recursive negascout search (with memory).  This works by calling the search
 * function with a zero window bound (beta=alpha+1).  This causes a quick cutoff so we
 * can then do a more accurate search with better defined bounds.  See Prof. Alexander
 * Reinefeld's www page for a paper detailing the algorithm. */
int             Search(Board * B, const int alpha, const int beta, int depth, int ply,
                   const int inchk, int fifty, int NullDepth, MOVE LastMove)
{
    MOVE            movelist[MAX_MOVES],
                    m,
                   *lastmove,
                    hashmove = NO_MOVE,
                    bestmove = NO_MOVE;
    int             score = -INFINITY,
                    best = -INFINITY,
                    evalscore = 0;
    int             NMoves,
                    Moveno,
                    newfifty = fifty + 1,
                    ep_carry,
                    p,
                    pto,
                    LegalMoves = 0,
                    gchk;
    int             newdepth,
                    nullreduction,
                    Base_Extensions = 0,
                    Extensions = 0,
                    excess = 0;
    int             EntryType,
                    EntryScore,
                    SEEScore;
    BOOL            DoNull = TRUE,
                    IsCapTopMove = FALSE;
    FullMove        Full[100];
    Undo            U;
    BOOL            threat = FALSE,
                    Futile = FALSE,
                    IsPV = FALSE,
                    ReduceExtensions = FALSE;
    HashElt        *Entry;
    /* Set up the temporary (changeable) values for alpha and beta at this
     * node */
    int             talpha = alpha,
                    tbeta = beta;
#ifdef DEBUG_VERIFY
    KeyType         CheckKey;
#endif
    /* Debugging information */
#ifdef DEBUG_VERIFY
    CheckKey = B->Key;
    GenerateHashKey(B);
    if (CheckKey != B->Key) {
        fprintf(stderr, "Warning - Key Corrupted in Search()\n");
        PrintBoard(*B);
        while (1);
    }
#endif

    /* Increase the Node Count */
    Nodecount++;

    /* Reset the best move */
    BestMoveRet = NO_MOVE;

    /* Reset 'the move on this ply is a capture' flag */
    IsCap[ply] = FALSE;

    /* ------------====     TEST FOR DRAWN POSITIONS     ====--------------- */

    /* See if this is a repeated/drawn position.  Do not test at top ply */
    if (ply > 0 && IsDrawn(B, ply, fifty, TRUE)) {
        return ((Current_Board.side == B->side) ? (DRAW_SCORE) : -(DRAW_SCORE));
    }
    /* -----------====     PROBE TRANSPOSITION TABLE     ====------------  */

    /* See if this position is in the hash table */
    Entry = HashProbe(B);

    /* ------------====     GET INFORMATION FROM HASH TABLE ====------------- */

    /* See what we can learn from the hash table entry (if any exists). */
    if (USE_HASH && Entry) {
        /* Get the suggested best move from the hash entry (if there is one) */
        hashmove = Entry->move;
        EntryType = GetHashType(Entry->flags);
        EntryScore = (int) Entry->score;
        /* Only accept this hash entry if the level to which it was initially
         * searched was greater than or equal to the current depth. Don't
         * check at ply==0 so that we're sure we can get a return value. */
        if (ply > 0 && ((int) Entry->depth >= depth || (EntryType == HASH_EXACT && IsCM(EntryScore) == 1))) {
            /* This was an exact entry so return it */
            switch (EntryType) {
            case (HASH_EXACT):
                return EntryScore;
                /* This was an upper bound, but still isn't greater than
                 * alpha, so return a fail-low */
            case (HASH_UPPER):
                if &#40;EntryScore <= talpha&#41;
                    return EntryScore;
                /* This was an upper bound, but was greater than alpha, so
                 * adjust beta if necessary */
                if &#40;EntryScore < tbeta&#41;
                    tbeta = EntryScore;
                break;
                /* This was a lower bound, but was still greater than beta,
                 * so return a fail-high */
            case &#40;HASH_LOWER&#41;&#58;
                if &#40;EntryScore >= tbeta&#41;
                    return EntryScore;
                /* This was a lower bound, but was not greater than beta, so
                 * adjust alpha if necessary */
                if &#40;EntryScore > talpha&#41;
                    talpha = EntryScore;
                break;
                /* Check to see if we should avoid null moves */
            case &#40;HASH_NULL&#41;&#58;
                DoNull = FALSE;
                break;
            &#125;
        &#125;
    &#125;
    /* -----------====     TRY A NULL MOVE     ====------------- */

    /* Perform a NULL move if; &#40;1&#41; We're not on the first 2 plies &#40;2&#41; We are
     * OK to NULL move at this position &#40;from the hash table&#41; &#40;3&#41; We haven't
     * done a NULL move already &#40;4&#41; We're not in check &#40;5&#41; There are enough
     * pieces left to avoid high risk of zugzwang &#40;6&#41; We are not rushed &#40;7&#41;
     * We're not on a leaf node */
    if &#40;USE_NULL && ply > 1 && DoNull && NullDepth == 0 && !inchk && &#40;nullreduction = NullOK&#40;B, depth&#41;) && !bRushed && depth > ONEPLY&#41; &#123;
        /* Increase the NULL reduction by one ply to account for the fact
         * that we've passed on this move. */
        /* Set up temporary flags to store the board position */
        ep_carry = B->ep;
        B->ep = -1;

        /* Do the null move reduced-depth search */
        B->side = Opponent&#40;B->side&#41;;
        if &#40;depth - nullreduction < ONEPLY&#41;
            score = -Quiesce&#40;B, -tbeta, -tbeta + 1, ply + 1, 0, 0&#41;;
        else
            score = -Search&#40;B, -tbeta, -tbeta + 1, depth - nullreduction, ply + 1, 0, 0, NullDepth + 1, NO_MOVE&#41;;

        /* Put things back */
        B->side = Opponent&#40;B->side&#41;;

        /* Verification Search.  Here we re-search this node at a shallower
         * depth if the score is >= beta.  The reason we do this is simple&#58;
         * we want to make sure that this really is a strong node, and
         * therefore worth chopping. This time, instead of actually making a
         * NULL move, we play a proper move. Note that we don't bother doing
         * this when close to the frontier nodes &#40;this would take us into the
         * qsearch&#41;.  We only fail high if this second search ALSO fails
         * high. */
        if &#40;score >= tbeta && depth - nullreduction >= ONEPLY&#41;
            score = Search&#40;B, tbeta - 1, tbeta, depth - nullreduction, ply + 1, 0, fifty, NullDepth + 1, LastMove&#41;;

        /* Replace the En-Passant flag */
        B->ep = ep_carry;

        /* If this move returned CM then we must be careful because there is
         * a CM threat dangerously close! Only do this on highest skill
         * level. */
        if &#40;IsCM&#40;score&#41; == -1 && Skill == 10&#41;
            threat = TRUE;

        /* A fail high means that the positional score here is so high that
         * even if the opponent is given a 'free move' then he still can't
         * improve his position enough to increase the value of alpha.  If
         * this is the case then clearly the current position is very strong.
         * In fact it is so strong that the opponent would never let it occur
         * in the first place, so we should cause a cut off.  */
        if &#40;score >= tbeta&#41; &#123;
            HashUpdate&#40;B, score, BestMoveRet, depth + ONEPLY - nullreduction, HASH_LOWER, FALSE, ply&#41;;
            return score;
        &#125;
    &#125;
    /* ----------====     INTERNAL ITERATIVE DEEPENING     ====----------- */

    /* If we're not doing a NULL move and we don't have a hash move and we're
     * at least 3 ply away from the quiescence search, then try to get a good
     * guess for the best move by doing a shallower search from here. */
    if &#40;USE_IID && hashmove == NO_MOVE && NullDepth == 0 && depth >= THREEPLY && Skill > 8 && !bRushed&#41; &#123;
        score = Search&#40;B, talpha, tbeta, depth - TWOPLY, ply, inchk, 0, 0, LastMove&#41;;
        /* Re-search properly if the previous search failed low, so that we
         * know we're getting a good move, not just the move with the highest
         * upper bound &#40;which is essentially random and depends on the search
         * order.) */
        if &#40;score <= talpha&#41;
            score = Search&#40;B, -CMSCORE, talpha + 1, depth - TWOPLY, ply, inchk, 0, 0, LastMove&#41;;
        /* Get the suggested best move that was returned and use it as a
         * hashmove */
        hashmove = BestMoveRet;
    &#125;
    /* ----------====     GENERATE MOVELIST     ====------------  */

    /* Make some moves */
    if (!inchk&#41;
        lastmove = GenerateMoves&#40;B, B->side, movelist&#41;;
    else
        lastmove = GenerateCheckEvasions&#40;B, B->side, movelist, inchk&#41;;

    /* Score the moves in the preliminary movelist.  Don't remove illegal
     * moves just yet, unless we're in check &#40;needed for single-reply
     * extension&#41;. If we're searching the root then order moves according to
     * root scores instead */
    NMoves = FilterMovelist&#40;movelist, lastmove, B, Full, ply, hashmove, inchk&#41;;
    /* No moves - stalemate */
    BestMoveRet = NO_MOVE;
    if &#40;NMoves == 0&#41;
        return (&#40;Current_Board.side == B->side&#41; ? &#40;DRAW_SCORE&#41; &#58; -&#40;DRAW_SCORE&#41;);

    /* -----------====     SEARCH EXTENSIONS     ====------------ */

    /* CM Threat extensions.  We extend here if a NULL move search returned a
     * checkmate threat. */
    if &#40;threat&#41; &#123;
        Base_Extensions += CMTHREAT_EXTEND;
        ThreatExtensions++;
    &#125;
    /* Single Reply Extension.  If there's only one possible move then
     * extend. */
    if &#40;NMoves == 1&#41; &#123;
        Base_Extensions += ONEREPLY_EXTEND;
        OneReplyExtensions++;
    &#125;
    /* Current Approximate Positional Score &#40;for Razoring&#41; if it might be
     * needed */
    if &#40;USE_RAZORING && !inchk && !threat && ply > 1&#41; &#123;
        if &#40;IsDrawnMaterial&#40;B&#41;)
            evalscore = &#40;Current_Board.side == WHITE ? DRAW_SCORE &#58; -DRAW_SCORE&#41;;
        else
            evalscore = LazyEval&#40;B&#41; + IsWonGame&#40;B&#41;;
        if &#40;B->side == BLACK&#41;
            evalscore = -evalscore;
    &#125;
    /* Check to see if we should reduce extensions here as we're getting way
     * too deep. Start doing this after we've extended by a total of
     * MAX_EXTEND ply, or we've searched to twice the default depth,
     * whichever is larger.  Put the best move first. */
    ReduceExtensions = &#40;ply > &#40;GlobalDepth + max&#40;GlobalDepth, MAX_EXTEND&#41;));


    /* -----------====     CYCLE THROUGH MOVES - INNER LOOP ====---------- */

    for &#40;Moveno = 0; Moveno < NMoves; Moveno++) &#123;

        /* Get the highest scoring move from those left on the list.  Put it
         * at the top. */
        SortFrom&#40;Full, Moveno, NMoves&#41;;
        m = Full&#91;Moveno&#93;.move;

        /* Keep track of the top ply move */
        if &#40;ply == 0 && &#40;depth == &#40;GlobalDepth * ONEPLY&#41;)) &#123;
            /* Work out the SEE score for this move */
            SEEScore = SEE&#40;B, MFrom&#40;m&#41;, MTo&#40;m&#41;, IsPromote&#40;m&#41;) * 100;
            /* Set up the top two &#40;the hash move and the largest competitor&#41; */
            if &#40;Moveno == 0&#41;
                TopOrderScore = SEEScore;
            else if &#40;SEEScore > NextBestOrderScore || Moveno == 1&#41;
                NextBestOrderScore = SEEScore;
            /* Set the top ply move that we're working on */
            TopPlyMoveno = Moveno;
        &#125;
        /* Identify the piece that's moving, and the piece on the target
         * square */
        p = PType&#40;B->pieces&#91;MFrom&#40;m&#41;&#93;);
        pto = PType&#40;B->pieces&#91;MTo&#40;m&#41;&#93;);

        /* Do the move */
        U = DoMove&#40;B, m&#41;;

        /* Filter out illegal moves which leave us in check. If we're in
         * check before the move then this has already been done. */
        if (!inchk && InCheck&#40;B, Opponent&#40;B->side&#41;)) &#123;
            UndoMove&#40;B, m, U&#41;;
            continue;
        &#125;
        /* This move is legal, so increase the count */
        LegalMoves++;

        /* Test to see if this move gives check */
        gchk = GivesCheck&#40;B, m&#41;;

        /* Test for immediate CM cutoff */
        if &#40;gchk && InCM&#40;B, gchk&#41;) &#123;
            UndoMove&#40;B, m, U&#41;;
            HashUpdate&#40;B, CMSCORE - ply - 1, m, depth, HASH_EXACT, FALSE, ply&#41;;
            IncreaseCounts&#40;Full&#91;Moveno&#93;, ply, CMSCORE&#41;;
            BestMoveRet = m;
            if &#40;LegalMoves == 1&#41;
                BestFirst++;
            SortNodes++;
            if &#40;Post && ply == 0&#41;
                PrintThinking&#40;CMSCORE - ply - 1, B&#41;;
            return CMSCORE - ply - 1;
        &#125;
        /* Test to see if this move breaks the 50 move draw chain, else
         * increase the count */
        if &#40;pto != empty || IsEP&#40;m&#41;)
            IsCap&#91;ply&#93; = TRUE;
        else
            IsCap&#91;ply&#93; = FALSE;
        if &#40;IsCastle&#40;m&#41; || IsCap&#91;ply&#93; || p == pawn&#41;
            newfifty = 0;
        else
            newfifty = fifty + 1;

        /* -------------====     MORE EXTENSIONS     ====------------------ */

        Extensions = Base_Extensions;

        /* Check extension &#40;if we're giving check this move&#41; */
        if &#40;gchk && Skill > 2&#41; &#123;
            Extensions += CHECK_EXTEND;
            CheckExtensions++;
            /* Revealed Check Extension &#40;Not 100% accurate, but near enough&#41;
             * Test to see if the piece giving check is not the piece moving.
             * &#40;This fails if the piece moving also gives check, and is
             * tested first.) */
            if &#40;gchk != p&#41; &#123;
                Extensions += REVCHECK_EXTEND;
                RevCheckExtensions++;
            &#125;
        &#125;
        /* Recapture Extension.  We do this in the following cases; &#40;1&#41; We
         * are not on the first ply &#40;obviously&#41; &#40;2&#41; The last ply was a
         * capture move &#40;3&#41; This move captures the piece that captured last
         * move &#40;4&#41; The value of this piece equals the value of the target
         * piece */
        if &#40;ply > 0 && IsCap&#91;ply - 1&#93; && MTo&#40;m&#41; == MTo&#40;LastMove&#41; && PieceValue&#91;pto&#93; == PieceValue&#91;p&#93; && Skill > 4&#41; &#123;
            Extensions += RECAP_EXTEND;
            RecapExtensions++;
        &#125;
        /* A Pawn Push Extension is used if we're moving a pawn to within one
         * rank of promotion. */
        if &#40;p == pawn && &#40;MTo&#40;m&#41; <= h7 || MTo&#40;m&#41; >= a2&#41; && Skill > 7&#41; &#123;
            Extensions += PAWNPUSH_EXTEND;
            PawnPushExtensions++;
        &#125;
        /* Fork extension */
        if &#40;p == wknight && Count&#40;KnightMoves&#91;MTo&#40;m&#41;&#93; & &#40;B->BlackQueens | B->BlackRooks | Mask&#91;B->BlackKing&#93;)) > 1&#41;
            Extensions += ONEPLY;
        if &#40;p == bknight && Count&#40;KnightMoves&#91;MTo&#40;m&#41;&#93; & &#40;B->WhiteQueens | B->WhiteRooks | Mask&#91;B->WhiteKing&#93;)) > 1&#41;
            Extensions += ONEPLY;

        /* Seemingly bad top ply moves are reduced when there is an obvious
         * easy move. Do not do this if we are capturing or giving check, or
         * if this is a shallow search. */
        if &#40;ply == 0 && bEasyMove && newdepth >= THREEPLY&#41; &#123;
            if &#40;Moveno == 0&#41;
                IsCapTopMove = IsCap&#91;ply&#93;;
            if &#40;IsCap&#91;ply&#93; && SEEScore + EASY_MOVE_MARGIN < TopOrderScore && m != Killer1&#91;ply&#93; && m != Killer2&#91;ply&#93;)
                Extensions -= ONEPLY;
        &#125;
        /* Reduce Extensions if we're searching too deep already */
        if &#40;ReduceExtensions&#41;
            Extensions /= 2;
        /* Add on the extensions, limiting them to 1.5 plies maximum, plus
         * reduce the depth to the next ply. */
        newdepth = depth + min&#40;Extensions, ONEANDAHALFPLY&#41; - ONEPLY;

        /* ----------------====     PRUNING     ====-------------------- */

        /* Check to see if this node might be futile.  This is used in the
         * subsequent algorithm. This is true if; &#40;1&#41; We are not in check,
         * nor is this a checking move &#40;2&#41; We are not in danger of losing to
         * CM &#40;3&#41; We are not capturing or promoting on this move &#40;4&#41; Alpha is
         * not a CM score, either for or against &#40;5&#41; We are not on the first
         * four ply, so that the search has had a chance to go bad. */
        if &#40;USE_RAZORING && !inchk && !gchk && !threat && !IsCap&#91;ply&#93; &&
            !IsPromote&#40;m&#41; && !IsCM&#40;talpha&#41; && ply > 3&#41;
            Futile = TRUE;
        else
            Futile = FALSE;

        /* Adaptive razoring.  This is similar to futility pruning &#40;see Heinz
         * et al in various papers&#41;, except that it works at several plies,
         * not just frontier and pre-frontier nodes. If the evaluation is
         * significantly below alpha, and this move is futile &#40;see above&#41;
         * then we reduce the depth to which we wish to search this node. The
         * margin we use increases with increasing depth.  Clearly, we need
         * to be much more careful about high-depth nodes as pruning them
         * could have much larger consequences. This algorithm is a bit
         * dodgy, but generally seems to work OK. */
        if &#40;Futile && LegalMoves > AVOID_RAZ_NUM && newdepth >= ONEPLY&#41; &#123;
            excess = talpha - &#40;evalscore + (&#40;newdepth * newdepth * RAZOR_SCALE&#41; / 10&#41; + RAZOR_MARGIN&#41;;
            if &#40;excess > 0&#41; &#123;
                /* If this is well below alpha then prune by a whole ply,
                 * otherwise just prune by a fraction of a ply. */
                if &#40;excess > RAZOR_HARSH&#41;
                    newdepth -= ONEPLY;
                else
                    newdepth -= (&#40;ONEPLY * excess&#41; / RAZOR_HARSH&#41;;
                RazorCuts++;
            &#125;
        &#125;
        /* -----------------====     RECURSE TO THE NEXT PLY
         * ====---------------- */

        /* If at bottom depth then return quiescence score.  Basically, we
         * find a quiet position before we accept the static evaluation. This
         * avoids the so-called 'horizon effect' where bad captures are
         * pushed off the end of the search tree causing total mis-evaluation
         * of the position.  &#40;See notes at top of Quiesce&#40;) function below&#41;. */
        if &#40;newdepth < ONEPLY&#41;
            score = -Quiesce&#40;B, -tbeta, -talpha, ply + 1, newfifty, gchk&#41;;

        /* Recurse to the next ply using negascout search heuristic */
        else &#123;
            /* If this is the first move then search it properly */
#ifdef USE_PV_SEARCH
            if &#40;LegalMoves == 1&#41;
#endif
                score = -Search&#40;B, -tbeta, -talpha, newdepth, ply + 1, gchk, newfifty, 0, m&#41;;

            /* Otherwise this is NOT the first move - use Negascout search */
#ifdef USE_PV_SEARCH
            else &#123;
                /* First try a zero-width search.  This tests if this
                 * position is going to improve alpha, but does not return an
                 * exact score.  It fails much more quickly in the &#40;hopefully
                 * more probable&#41; case that the move does NOT improve alpha. */
                score = -Search&#40;B, -talpha - 1, -talpha, newdepth, ply + 1, gchk, newfifty, 0, m&#41;;
                /* Looks like this move will improve alpha */
                if &#40;score > talpha && score < tbeta && !AbortFlag&#41;
                    /* .. therefore search again with sensible bounds */
                    score = -Search&#40;B, -tbeta, -score, newdepth, ply + 1, gchk, newfifty, 0, m&#41;;
            &#125;
#endif
        &#125;
#ifdef DEBUG_VERIFY
        CheckKey = B->Key;
        GenerateHashKey&#40;B&#41;;
        if &#40;CheckKey != B->Key&#41; &#123;
            fprintf&#40;stderr, "Warning - Key Corrupted in Search&#40;) iteration step, ply=%d, depth=%d\n", ply, depth&#41;;
            PrintBoard&#40;*B&#41;;
            while &#40;1&#41;;
        &#125;
#endif

        /* Undo the move */
        UndoMove&#40;B, m, U&#41;;

        /* ---------------====     HAVE WE IMPROVED OUR BEST SCORE?
         * ====------------- */

        /* Update scores */
        if (!AbortFlag && score > best&#41; &#123;
            best = score;
            bestmove = m;
            /* Have we improved alpha? &#40;i.e. this an interesting move&#41; */
            if &#40;best > talpha&#41; &#123;
                IncreaseCounts&#40;Full&#91;Moveno&#93;, ply, score&#41;;
                /* Fail-high cutoff.  This means that this move is so good
                 * that it will never be played as our opponent will never
                 * allow it &#40;he/she has better alternatives&#41; so don't bother
                 * continuing the search. */
                if &#40;score >= tbeta&#41; &#123;
                    /* Update the hash table & return the move score */
                    BestMoveRet = bestmove;
                    SortNodes++;
                    HashUpdate&#40;B, score, bestmove, depth, HASH_LOWER, threat, ply&#41;;
                    if &#40;LegalMoves == 1&#41;
                        BestFirst++;
                    return best;
                &#125;
                /* Print off the PV if we're posting to XBoard and this is
                 * the top ply and we're not doing the IID loop. */
                if &#40;ply == 0 && &#40;depth == &#40;GlobalDepth * ONEPLY&#41;)) &#123;
                    HashUpdate&#40;B, score, bestmove, depth, HASH_EXACT, threat, ply&#41;;
                    if &#40;Post&#41;
                        PrintThinking&#40;score, B&#41;;
                &#125;
                /* We know we're in the PV Now */
                IsPV = TRUE;
                /* We know that this score > alpha, so improve &#40;the
                 * temporary&#41; alpha */
                talpha = best;
            &#125;
            /* Always store the first top ply entries &#40;to make sure that we
             * have something that we can return&#41;.  Don't store every move
             * because if we get a fail- low in the window search it might
             * well beat the best move so far just by fluke - we might score
             * Move1<100 and Move2<200, giving Move2 a better score, but of
             * course the reality could be that Move1=99, Move2=0. If we're
             * getting only fail-lows in the window search then we need to
             * re-search the root position anyway, using the previous best
             * move &#40;the one searched first&#41; at the top of the list. See also
             * the upper bound hash stores below in the hash table update
             * section. */
            else if &#40;ply == 0 && LegalMoves == 1 && &#40;depth == &#40;GlobalDepth * ONEPLY&#41;)) &#123;
                HashUpdate&#40;B, score, bestmove, depth, HASH_UPPER, threat, ply&#41;;
                if &#40;Post&#41;
                    PrintThinking&#40;score, B&#41;;
            &#125;
        &#125;
        /* Check for time problems and new input periodically */
        if (!AbortFlag && (&#40;Nodecount & INPUT_PERIOD&#41; == 0 || ply < 4&#41; && !bRushed&#41; &#123;
            if &#40;GlobalDepth > Params.Depth && !AnalyseMode&#41;
                AbortFlag = CheckTime&#40;ply, score&#41;;
            if (!AbortFlag&#41; &#123;
                InputFlag = CheckUserInput&#40;);
                if &#40;InputFlag && InputFlag != INPUT_WORK_DONE&#41;
                    AbortFlag = TRUE;
            &#125;
        &#125;
        if &#40;AbortFlag&#41;
            break;
    &#125;

    /* Check for stalemate.  Note that we've already filtered out CMs at the
     * top of this function. */
    if &#40;LegalMoves == 0&#41; &#123;
        best = (&#40;Current_Board.side == B->side&#41; ? &#40;DRAW_SCORE&#41; &#58; -&#40;DRAW_SCORE&#41;);
        bestmove = NO_MOVE;
    &#125;
    /* -------------====     UPDATE THE HASH TABLE     ====--------------  */

    /* We store the hashtable results as an exact value or an upper bound
     * depending on whether we're in the PV or not.  If we have found a move
     * that increased alpha then this move is in the PV and hence is an exact
     * score.  Otherwise, all moves in this level are a result of fail-high
     * cutoffs from the next ply, and hence all we really have is an upper
     * bound on the best score.  We know we can't get any better than this,
     * but we don't really know how bad the score truly is.  All that matters
     * is that the best we could possibly get isn't good enough. Don't store
     * top ply &#40;ply=0&#41; fail-low moves here because a fail low in the window
     * search can cause bad moves to be stored instead of the best move so
     * far.  This is because we get only bounds, and one lower bound being
     * higher than another tells us nothing about the actual scores
     * themselves. &#40;We DO score ply=0 moves if this is the first iteration,
     * however, to make sure that *something* is stored!). */
    if (!AbortFlag&#41; &#123;
        if &#40;IsPV&#41;
            HashUpdate&#40;B, best, bestmove, depth, HASH_EXACT, threat, ply&#41;;
        else if &#40;ply > 0 || GlobalDepth == 2&#41;
            HashUpdate&#40;B, best, bestmove, depth, HASH_UPPER, threat, ply&#41;;
    &#125;
    /* If we've run out of time then print the thinking as far as we've got.
     * Don't bother if we didn't actually finish searching the first move,
     * though.  Also don't bother if the opponent has just resigned. */
    if &#40;AbortFlag && ply == 0 && depth == &#40;GlobalDepth * ONEPLY&#41; && best > -INFINITY && InputFlag != INPUT_RESIGN&#41;
        PrintThinking&#40;best, B&#41;;

    /* Return the best value found */
    BestMoveRet = bestmove;
    return best;
&#125;

And here is the "OK to do null?" check routine:

Code: Select all


/* Test to see whether or not a NULL move is safe in the given position.
 * This is false if;
 * &#40;1&#41; There is less material on the board than the defined minimum, AVOID_NULL_MAT
 * &#40;2&#41; There are fewer pieces than AVOID_NULL_PIECES
 * If a NULL move is safe then we calculate the amount by which we should reduce
 * the search depth. */
int NullOK&#40;Board *B,int depth&#41; &#123;
   int cwp=0,cbp=0,base_reduction = &#40;depth>IGNORE_ZUGZWANG&#41; ? 0 &#58; ONEPLY;
   
   /* If there is a risk of Zugzwang then return 0 &#40;no Null move&#41; */
  if &#40;B->side==WHITE && B->WPts < AVOID_NULL_MAT&#41; return base_reduction;
  if &#40;B->side==BLACK && B->BPts < AVOID_NULL_MAT&#41; return base_reduction;
  cwp = Count&#40;B->WhitePieces&#41;;
  if &#40;B->side==WHITE && cwp < AVOID_NULL_PIECES&#41; return base_reduction;
  cbp = Count&#40;B->BlackPieces&#41;;
  if &#40;B->side==BLACK && cbp < AVOID_NULL_PIECES&#41; return base_reduction;
      
  if &#40;Skill<=8&#41; return Skill;
   
   /*
    The formula below is from Ernst A. Heinz's book "Scalable Search in Computer Chess"
    It comes from pages 35-37 and is described elsewhere in the book.
    This method is called 'Adaptive Null Move Pruning' with R&#40;adapt&#41; = 3&#40;6&#41;~2.
    In English, the NULL move depth reduction is equal to two ply by default.  However,
    if either &#40;a&#41; both sides have fewer than 3 pieces and the current depth is 8 ply or
    more or &#40;b&#41; at least one side has greater than 2 pieces and the current depth is
    6 ply or more then increase the depth reduction to 3 full ply.
   */
//   return TWOPLY + (&#40;depth&#41; > (&#40;6*ONEPLY&#41; + ((&#40;cwp < 3 && cbp < 3&#41; ? TWOPLY &#58; 0&#41;)) ? ONEPLY &#58; 0&#41;;
  
   /* This is my own formula, offering scaleable search depth reduction between one and
    * 2.5 ply depending on the depth to which you are searching */
   return ONEPLY + &#40;depth > &#40;ONEPLY*8&#41; ? &#40;ONEPLY&#41; &#58; &#40;depth / ONEPLY&#41;) + (&#40;depth > ONEPLY&#41; ? &#40;HALFPLY&#41; &#58; &#40;0&#41;);
&#125;

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null move pruning

Post by bob » Sat Sep 19, 2009 12:41 pm

cms271828 wrote:Thanks, I can see why being in check and zugzwang is bad for nmp.

I'm not sure if theres anything I need to do in MakeNullMove() and UndoNullMove(), and also where should I take the first null move, and how often should I use null move?

Thanks
The only thing you need to do is clear the enpassant target, of course. If I play a null-move after you play a move like e7-e5, I no longer have an opportunity to make an EP capture, so the hash signature needs to be corrected for that, assuming you are currently factoring this in to your signature. If course, as part of that the 50 move counter has to be reset, as you are making an "irreversable" move (actually an illegal move). Ditto for your repetition detection as you can't possibly repeat a position that occurred before the null-move.

User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Re: Null move pruning

Post by cms271828 » Sun Sep 20, 2009 12:05 am

Thanks, I think that makes sense. I don't bother with 50 move rule, and I haven't got rep detection to work.

Looking at the code again in blue http://web.archive.org/web/200404270146 ... llmove.htm
I'm concerned about the depth, since say D=1, this wouldn't call alphabeta (or qs in my case) with depth 0, but with depth -2.

So perhaps we need to surround that block with 'IF D >= 3...' so that alphabeta (or qs) gets called by passing in 0 or greater depth.

Any thoughts? Thans
Colin

Sven
Posts: 3882
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Null move pruning

Post by Sven » Sun Sep 20, 2009 7:55 am

cms271828 wrote:Looking at the code again in blue http://web.archive.org/web/200404270146 ... llmove.htm
I'm concerned about the depth, since say D=1, this wouldn't call alphabeta (or qs in my case) with depth 0, but with depth -2.

So perhaps we need to surround that block with 'IF D >= 3...' so that alphabeta (or qs) gets called by passing in 0 or greater depth.
Yes, the code in blue requires some "if (depth >= ...)" guard. If you want to allow your null move search to start directly with qsearch, i.e. with zero plies of full-width search, then the condition should be "if (depth - 1 - R >= 0)" which is equivalent to "if (depth >= R + 1)". Otherwise (which is what I would prefer since I think a null move search that does only qsearch can be dangerous), the condition should be "if (depth - 1 - R >= XX)" or "if (depth >= R + 1 + XX)" where XX denotes the minimum number of plies above the horizon that you allow to start a null move search.

Code: Select all

if &#40;depth >= R + 1 + XX&#41; &#123;
    MakeNullMove&#40;);
    val = -AlphaBeta&#40;depth - 1 - R, -beta, -beta + 1&#41;;
    UnmakeNullMove&#40;);
    if &#40;val >= beta&#41;
        return beta;
&#125;
Sven

User avatar
hgm
Posts: 24999
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Null move pruning

Post by hgm » Sun Sep 20, 2009 9:27 am

I don't think there is any danger jumping directly into QS with a null move, more than with any other move. If there is a threat that cannot be found by the opponent in a QS reply to null move, then it would not be found in QS after a real move either, and as a cosequence also not after a a two ply delaying tactic (as is almost always available) plus a real move. So searching the real moves after a d=1 null move fails high is an almost certain waste of time, as the search is almost guaranteed to come up with a delaying tactic that fails high, even when there would be a threat that is non-detectable in QS.

bob
Posts: 20918
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Null move pruning

Post by bob » Sun Sep 20, 2009 2:39 pm

cms271828 wrote:Thanks, I think that makes sense. I don't bother with 50 move rule, and I haven't got rep detection to work.

Looking at the code again in blue http://web.archive.org/web/200404270146 ... llmove.htm
I'm concerned about the depth, since say D=1, this wouldn't call alphabeta (or qs in my case) with depth 0, but with depth -2.

So perhaps we need to surround that block with 'IF D >= 3...' so that alphabeta (or qs) gets called by passing in 0 or greater depth.

Any thoughts? Thans
You have two choices. You can do this:

(1) if (depth - 1 - R > 0)
call search(depth -1 -R, etc)
else
call quiesce();

(2) let your search get the -2 for depth, but immediately call quiesce() rather than doing "the normal thing."

Post Reply