Null Move Pruning gives worse results

[ciorap0]

Hello!

I am currently testing null move pruning in my engine and it seems a bit odd to me that it gives me worse results (around -17elo in a 1k game match against the version without null move pruning) when I use it.

It is very weird, especially considering that everyone says it's probably the most important pruning technique.

I should also mention that I tried tweaking the reduction depth and the material threshold, but it performs even worse than this.

Here's a the code of my alphaBeta function:

Code: Select all

int alphaBeta(int alpha, int beta, short depth, short ply, bool doNull) {
    assert(depth >= 0);

    int pvIndex = ply * (2 * N + 1 - ply) / 2;
    int pvNextIndex = pvIndex + N - ply;

    memset(pvArray + pvIndex, NO_MOVE, sizeof(int) * (pvNextIndex - pvIndex));

    if(!(nodesSearched & 4095) && !infiniteTime) {
        long long currTime = chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
        if(currTime >= stopTime) timeOver = true;
    }
    if(timeOver) return 0;
    nodesSearched++;

    int hashFlag = HASH_F_ALPHA;

    bool isInCheck = board.isInCheck();

    if(isInCheck) depth++;

    // --- MATE DISTANCE PRUNING --- 
    int matedScore = - MATE_EVAL + ply;
    if(alpha < matedScore) {
        alpha = matedScore;
        if(beta <= matedScore) return matedScore;
    }

    int mateScore = MATE_EVAL - ply;
    if(beta > mateScore) {
        beta = mateScore;
        if(alpha >= mateScore) return mateScore;
    }

    if(alpha >= beta) return alpha;

    if(board.isDraw()) return 0;

    bool isPV = (beta - alpha > 1);

    // retrieving the hashed move and evaluation if there is any
    int hashScore = probeHash(depth, alpha, beta);
    if(hashScore != VAL_UNKNOWN) {
        // we return hashed info only if it is an exact hit in pv nodes
        if(!isPV || (hashScore > alpha && hashScore < beta)) {
            return hashScore;
        }
    }

    int moves[256];
    int num = board.generateLegalMoves(moves);
    if(num == 0) {
        if(isInCheck) return -mateScore; // checkmate
        return 0; // stalemate
    }


    if(depth <= 0) {
        int q = quiesce(alpha, beta);
        if(timeOver) return 0;
        return q;
    }
    int currBestMove = NO_MOVE;

    // --- NULL MOVE PRUNING --- 
    const int ENDGAME_MATERIAL = 16; // this is equivalent to all pieces on the table except the queens
    if(doNull && (!isPV) && (isInCheck == false) && ply && (depth >= 3) && (gamePhase() >= ENDGAME_MATERIAL) && (evaluate() >= beta)) {
        board.makeMove(NO_MOVE);

        short R = 2;
        int score = -alphaBeta(-beta, -beta + 1, depth - R - 1, ply + 1, false);

        board.unmakeMove(NO_MOVE);

        if(timeOver) return 0;
        if(score >= beta) return beta;
    }

    int movesSearched = 0;

    sortMoves(moves, num, ply);
    for(int idx = 0; idx < num; idx++) {
        if(alpha >= beta) return alpha;

        board.makeMove(moves[idx]);
            
        // --- PRINCIPAL VARIATION SEARCH --- 
        int score;
        if(!movesSearched) {
            score = -alphaBeta(-beta, -alpha, depth-1, ply+1, true);
        } else {
            // --- LATE MOVE REDUCTION --- 
            if(movesSearched >= 2 && !isCapture(moves[idx]) && !isPromotion(moves[idx]) && !isInCheck && depth >= 3 && !board.isInCheck()) {
                int reductionDepth = int(sqrt(double(depth-1)) + sqrt(double(movesSearched-1))); 
                if(isPV) reductionDepth = (reductionDepth * 2) / 3;
                reductionDepth = (reductionDepth < depth-1 ? reductionDepth : depth-1);

                score = -alphaBeta(-alpha-1, -alpha, depth - reductionDepth - 1, ply+1, true);
            } else {
                score = alpha + 1; // hack to ensure that full-depth search is done
            }

            if(score > alpha) {
                score = -alphaBeta(-alpha-1, -alpha, depth-1, ply+1, true);
                if(score > alpha && score < beta) {
                    score = -alphaBeta(-beta, -alpha, depth-1, ply+1, true);
                }
            }
        }

        board.unmakeMove(moves[idx]);
        movesSearched++;

        if(timeOver) return 0;
        
        if(score > alpha) {
            currBestMove = moves[idx];

            pvArray[pvIndex] = moves[idx];
            copyPv(pvArray + pvIndex + 1, pvArray + pvNextIndex, N - ply - 1);

            assert(pvArray[pvIndex] != NO_MOVE);
            assert(pvIndex < pvNextIndex);
            assert(pvNextIndex < (N * N + N) / 2);

            if(score >= beta) {
                recordHash(depth, beta, HASH_F_BETA, currBestMove);

                if(!isCapture(moves[idx]) && !isPromotion(moves[idx])) {
                    storeKiller(ply, moves[idx]);
                    updateHistory(moves[idx], depth);
                }

                return beta;
            }
            hashFlag = HASH_F_EXACT;
            alpha = score;
        }
    }
    if(timeOver) return 0;

    recordHash(depth, alpha, hashFlag, currBestMove);
    return alpha;
}

I would appreciate some help from a more experienced chess programmer. Thanks!

[Steve Maughan]

I can't see anything obviously wrong but here are some pointers:

• Does the "board.makeMove(NO_MOVE)" routine flip side to move?

• Does the "board.makeMove(NO_MOVE)" routine xor WHITE_TO_MOVE_HASH to change the side to move in the hash signature?

• I'd recommend implementing null-move before Late-Move-Reductions

I hope this helps. A basic implementation of null move, like the one you have here, should add ~100 ELO.

— Steve

[JVMerlino]

Steve's thoughts are the place to start. But I also don't recall ever seeing the condition (evaluate() >= beta) before doing a null move.

[Ras]

But I also don't recall ever seeing the condition (evaluate() >= beta) before doing a null move.

I do that, and e.g. Stockfish, Demolito, and Ethereal as well. It also makes sense because you're looking for a beta cut-off - and if the static eval is already below beta, and then you even give the opponent a free move, it's unlikely to suddenly jump over beta. Except maybe in zugzwang prone situations where you shouldn't do nullmove searches in the first place.

[ciorap0]

• Does the "board.makeMove(NO_MOVE)" routine flip side to move?

• Does the "board.makeMove(NO_MOVE)" routine xor WHITE_TO_MOVE_HASH to change the side to move in the hash signature?

Yes and yes. I should also probably add that the engine (correctly?) searches less nodes for each depth when null move pruning is enabled, but the best move is different sometimes.

I'd recommend implementing null-move before Late-Move-Reductions

I will try disabling LMR and post the results here.

[ciorap0]

• I'd recommend implementing null-move before Late-Move-Reductions

I tested the disabling LMR and this is what I got:

Code: Select all

--- NMP and no LMR vs LMR and no NMP ---
Score of CiorapBot 0.2 +NMP -LMR vs CiorapBot 0.2 -NMP +LMR: 196 - 538 - 266  [0.329] 1000
...      CiorapBot 0.2 +NMP -LMR playing White: 59 - 285 - 156  [0.274] 500
...      CiorapBot 0.2 +NMP -LMR playing Black: 137 - 253 - 110  [0.384] 500
...      White vs Black: 312 - 422 - 266  [0.445] 1000
Elo difference: -123.8 +/- 19.2, LOS: 0.0 %, DrawRatio: 26.6 %

--- NMP and no LMR vs no NMP and no LMR --- 
Score of CiorapBot 0.2 +NMP -LMR vs CiorapBot 0.2 -NMP -LMR: 424 - 185 - 391  [0.620] 1000
...      CiorapBot 0.2 +NMP -LMR playing White: 264 - 71 - 165  [0.693] 500
...      CiorapBot 0.2 +NMP -LMR playing Black: 160 - 114 - 226  [0.546] 500
...      White vs Black: 378 - 231 - 391  [0.574] 1000
Elo difference: 84.7 +/- 17.0, LOS: 100.0 %, DrawRatio: 39.1 %

-- more aggressive NMP and no LMR vs LMR and no NMP ---
--- (ENDGAME_MATERIAL = 4; R = 3 + depth / 6;) ---
Score of CiorapBot 0.2 +NMPa -LMR vs CiorapBot 0.2 -NMP +LMR: 232 - 475 - 293  [0.379] 1000
...      CiorapBot 0.2 +NMPa -LMR playing White: 93 - 234 - 173  [0.359] 500
...      CiorapBot 0.2 +NMPa -LMR playing Black: 139 - 241 - 120  [0.398] 500
...      White vs Black: 334 - 373 - 293  [0.480] 1000
Elo difference: -86.2 +/- 18.4, LOS: 0.0 %, DrawRatio: 29.3 %

The games had time control 100/1+0.03.

Null move pruning seems to work if Late move reduction is disabled, but they don't work that well together. Engine performs much better using only LMR than only NMP.

I also checked the node count in startpos and it seems that LMR reduces the node count by much more than NMP.

Code: Select all

-- +LMR -NMP
info score cp 13 depth 8 nodes 93323 time 227 nps 411114 pv e2e4 d7d5 e4d5 e7e6 b1c3 g8f6 f1b5 c7c6 

-- +NMPa -LMR
info score cp 21 depth 8 nodes 1252116 time 2754 nps 454653 pv e2e4 d7d5 e4d5 g8f6 d2d4 e7e6 f1b5 c8d7

-- -NMP -LMR
info score cp 21 depth 8 nodes 2647814 time 5724 nps 462581 pv e2e4 d7d5 e4d5 g8f6 d2d4 e7e6 f1b5 c8d7 

Does this make sense?

[ciorap0]

I also ran a search from startpos with the version with both NMP and LMR, and it seems to search significantly less nodes than with only LMR, but only at higher depths (depth 10+, where it only usually gets after multiple seconds).

Maybe null move pruning only works well at slower time controls? I will test it on longer games and come back with the results.

[ciorap0]

UPDATE: After testing the engine in a 30+0.5 time control (null-move pruning and LMR vs only LMR) for 100 games, I got this

Code: Select all

Score of CiorapBot 0.2 +NMP +LMR vs CiorapBot 0.2 -NMP +LMR: 29 - 14 - 57  [0.575] 100
...      CiorapBot 0.2 +NMP +LMR playing White: 16 - 7 - 27  [0.590] 50
...      CiorapBot 0.2 +NMP +LMR playing Black: 13 - 7 - 30  [0.560] 50
...      White vs Black: 23 - 20 - 57  [0.515] 100
Elo difference: 52.5 +/- 44.7, LOS: 98.9 %, DrawRatio: 57.0 %

It seems like my theory could be true, but it still needs more testing.

[ciorap0]

Code: Select all

Score of CiorapBot 0.2 +NMP +LMR vs CiorapBot 0.2 -NMP +LMR: 117 - 37 - 159  [0.628] 313
...      CiorapBot 0.2 +NMP +LMR playing White: 79 - 12 - 66  [0.713] 157
...      CiorapBot 0.2 +NMP +LMR playing Black: 38 - 25 - 93  [0.542] 156
...      White vs Black: 104 - 50 - 159  [0.586] 313
Elo difference: 90.8 +/- 26.9, LOS: 100.0 %, DrawRatio: 50.8 %

I think this confirms it, null-move pruning works, but only at slower time controls.

[Steve Maughan]

I think this confirms it, null-move pruning works, but only at slower time controls.

I'm surprised by this since null move normally gives 50 to 100 ELO gain for most engines. Can someone with a mature engine validate these results?

— Steve