Null move pruning issue

[maksimKorzh]

Hi guys, I have a following issue.
In this position:

r1k5/1p5p/p1b2p2/P5p1/3R4/R1P5/2P1rBPP/6K1 w - - 2 33
FEN does not get rendered for some reason, hence sorry for string representation

If I run search without null move pruning the pv would be:
a3a2 f6f5 h2h3 h7h5 d4d6

But with null move pruning the pv is:
d4d8 c8d8 f2b6 d8d7 b6f2

Engine sacs a rook thinking that 3 fold repetition is forced.
Here's my null move pruning code:

Code: Select all

let inCheck = isSquareAttacked(kingSquare[side], side ^ 1);
    
    // check extension
    if (inCheck) depth++;
    
    // null move pruning
    if (searchPly && depth >= 3 && inCheck == 0) {
      makeNullMove();
      score = -negamax(-beta, -beta + 1, depth - 1 - 2);
      takeNullMove();
      
      if (timing.stopped == 1) return 0;
      if (score >= beta) return beta;
    }

    let moveList = [];
    generateMoves(moveList);
    
    // sort PV move
    sortPvMove(moveList);
    
    // loop over moves
    for (let count = 0; count < moveList.length; count++) {
      sortMoves(count, moveList);

I feel like I'm doing something wrong but not sure what exactly.
Could you please point out why this is happening and how to prevent this weird behavior?

[brianr]

It could be in your makeNullMove(); code.

Or, you might not have correct repetition move history.
I follow Crafty's approach and keep separate repetition lists by color.

The posted code seems ok.
So, likely one of the above; however, null move can do bizarre things and it might not actually be a problem, although that seems rather unlikely with so many pieces left and no zugzwang.

[maksimKorzh]

It could be in your makeNullMove(); code.

Or, you might not have correct repetition move history.
I follow Crafty's approach and keep separate repetition lists by color.

The posted code seems ok.
So, likely one of the above; however, null move can do bizarre things and it might not actually be a problem, although that seems rather unlikely with so many pieces left and no zugzwang.

MakeNullMove/takeNullMove:

Code: Select all

// make null move
  function makeNullMove() {
    // backup current board state
    moveStack.push({
      move: 0,
      capturedPiece: 0,
      side: side,
      enpassant: enpassant,
      castle: castle,
      fifty: fifty,
      hash: hashKey,
    });
    
    if (enpassant != noEnpassant) hashKey ^= pieceKeys[enpassant];
    enpassant = noEnpassant;
    fifty = 0;
    side ^= 1;
    hashKey ^= sideKey;
  }
  
  // take null move
  function takeNullMove() {
    // restore board state
    side = moveStack[moveStack.length - 1].side;
    enpassant = moveStack[moveStack.length - 1].enpassant;
    castle = moveStack[moveStack.length - 1].castle;
    fifty = moveStack[moveStack.length - 1].fifty;
    hashKey = moveStack[moveStack.length - 1].hashKey;
    moveStack.pop();
  }

For now solved the issue by adding extra condition:

Code: Select all

if (searchPly && depth >= 3 && inCheck == 0 && evaluate() >= beta)

seems like the most straightforward solution

[brianr]

I did not notice passing a flag to your search to not do two null moves in a row...missed it the first time I looked.

Also, it may not help in your engine, but I also only do null moves if

if (alpha == beta - 1)

[maksimKorzh]

I did not notice passing a flag to your search to not do two null moves in a row...missed it the first time I looked.

Also, it may not help in your engine, but I also only do null moves if

if (alpha == beta - 1)

Hold on... do you mean alpha == beta - 1 is the same as evaluate() >= beta ?
Or "also" regards to extra conditions to consider NMP in your engine?

EDIT: by saying evaluate() >= beta I assume that we apply NMP if side to move has good enough score to produce a beta cutoff

[Ferdy]

Hi guys, I have a following issue.
In this position:

r1k5/1p5p/p1b2p2/P5p1/3R4/R1P5/2P1rBPP/6K1 w - - 2 33
FEN does not get rendered for some reason, hence sorry for string representation

If I run search without null move pruning the pv would be:
a3a2 f6f5 h2h3 h7h5 d4d6

But with null move pruning the pv is:
d4d8 c8d8 f2b6 d8d7 b6f2

Engine sacs a rook thinking that 3 fold repetition is forced.
Here's my null move pruning code:

Code: Select all

let inCheck = isSquareAttacked(kingSquare[side], side ^ 1);
    
    // check extension
    if (inCheck) depth++;
    
    // null move pruning
    if (searchPly && depth >= 3 && inCheck == 0) {
      makeNullMove();
      score = -negamax(-beta, -beta + 1, depth - 1 - 2);
      takeNullMove();
      
      if (timing.stopped == 1) return 0;
      if (score >= beta) return beta;
    }

    let moveList = [];
    generateMoves(moveList);
    
    // sort PV move
    sortPvMove(moveList);
    
    // loop over moves
    for (let count = 0; count < moveList.length; count++) {
      sortMoves(count, moveList);

I feel like I'm doing something wrong but not sure what exactly.
Could you please point out why this is happening and how to prevent this weird behavior?

Not sure if this helps, but you may try something like this.

* When time is up, return immediately.
* Do not return 0 if fifty is just 100 without checking first if it is a checkmate as checkmate has a priority over fifty-move draw rule.
* Do not go to qsearch when in check.
* Do not do nullmove successively.

Code: Select all

  function negamax(alpha, beta, depth, donull) {
    pvLength[searchPly] = searchPly;
    
    let score = 0;

    if ((nodes & 2047) == 0){
      checkTime();
      if (timing.stopped == 1) return 0;
    }

    if ((searchPly && isRepetition()) || fifty > 100) return 0;

    let inCheck = isSquareAttacked(kingSquare[side], side ^ 1);
    if (inCheck == 0 && fifty >= 100) return 0;

    // check extension
    if (inCheck) depth++;

    if (depth == 0) { nodes++; return quiescence(alpha, beta); }
    
    // null move pruning
    if (searchPly && depth >= 3 && inCheck == 0 && evaluate() >= beta && donull == 1) {
      makeNullMove();
      score = -negamax(-beta, -beta + 1, depth - 1 - 2, 0);
      takeNullMove();
      
      if (timing.stopped == 1) return 0;
      if (score >= beta) return beta;
    }
    
    ...
    score = -negamax(-beta, -alpha, depth - 1, 1);
    
    ...
    
    score = negamax(-infinity, infinity, currentDepth, 1);
    
    ...

[No4b]

I think allowing multiple nullmoves in a row may cause the issue here

[brianr]

I did not notice passing a flag to your search to not do two null moves in a row...missed it the first time I looked.

Also, it may not help in your engine, but I also only do null moves if

if (alpha == beta - 1)

Hold on... do you mean alpha == beta - 1 is the same as evaluate() >= beta ?
Or "also" regards to extra conditions to consider NMP in your engine?

EDIT: by saying evaluate() >= beta I assume that we apply NMP if side to move has good enough score to produce a beta cutoff

As has been mentioned, multiple null moves in a row are typically bad.

The alpha == beta - 1 is only doing null moves for null window searches.
This works better for Tinker; it may or may not help your engine.

The benefits, if any, of null move details turn out to depend very heavily on each particular engine's search/eval ecosystem.