Regarding Null Move Pruning

[StackFish5]

Recently, I have been working on the addition of null move pruning within my chess engine. However, many bugs have been present within the chess engine succeeding the inclusion of null move pruning. I managed to solve all but one issue, in which it segfaults very regularly. I have attempted to get to the root of the problem but have yet to pinpoint the error present. I do know that the issue isn’t any depth related as I have run many tests. But other than that, I do not know. Below is some of my code regarding the making and the unmaking of the null moves and some search logic. Help would be greatly appreciated, thank you.

P.S.

Code: Select all

//make and unmake null moves respectively
inline void Legal_Moves::push_null_move(){
	//Skip turn
	side_to_move ^= 1;
	//Nullify the en passant square
	En_Passant_Sq.push_back(64);
}

inline void Legal_Moves::pop_null_move(){
	//Revert turn
	side_to_move ^= 1;
	//Set en passant vector back to original state before null move
	En_Passant_Sq.pop_back();
}

//Principal Variation Search with LMR
inline int pvs(int alpha, int beta, int depth, int ply, bool can_null, HISTORY &history, KILLER &killer, Legal_Moves &board){
	...

	//Null Move Pruning
	if(depth >= 3 && !check && can_null && ply){
		//Make Null Move
		board.push_null_move();
		score = -pvs(-beta, -beta + 1, depth - 3, ply + 1, false, history, killer, board);
		can_null = false;
		//Unmake null move
      		board.pop_null_move();
      		// fail-hard beta cutoff
      		if(score >= beta){
        	// node fails high
        	return beta;
	}
	...
	for(int i = 0; i < move_list.size(); i++){
get_best_move(move_list, i);
	move = move_list[i];

	board.push_move(move);
	nodes++;
			
	bool gives_check = board.in_check();

	if(moves_searched == 0){ 
      		score = -pvs(-beta, -alpha, depth - 1, ply + 1, can_null, history, killer, board);
	} else {
      		if(moves_searched >= full_depth_moves && depth >= reduction_limit && move.capture == E && !move.promoted && !check && !gives_check){
        			score = -pvs(-alpha - 1, -alpha, depth - 2, ply + 1, can_null, history, killer, board);
		} else { 
			score = alpha + 1;  
		}
      		if(score > alpha) {
        			score = -pvs(-alpha - 1, -alpha, depth - 1, ply + 1, can_null, history, killer, board);
        			if(score > alpha && score < beta){
          				score = -pvs(-beta, -alpha, depth - 1, ply + 1, can_null, history, killer, board);
			}
      		}
	}
			
	board.pop_move(move);
	moves_searched++;
	…
}

[Mike Sherwin]

Null move could be as simple as:

Code: Select all

  // null move
  // incheck test not needed if GenCapts() returns -MATE - ply
  eval = GetEval();
  if (eval >= beta && depth >= 3) {
    wtm = 1 - wtm;
    score = -Search(-beta - 1, -beta + 1, depth - 3);
    wtm = 1 - wtm;
    if (score >= beta) return beta;
  }
  

You could replace your null move code with something simple just to see if something is wrong with the null move code. And then go from there.

[odomobo]

So I didn't see anything that looks like the source of your bug, but I do see another bug. It looks like for a particular search, it will only do a null move check once (at the root), and never again anywhere deeper in the search tree. This is because can_null gets set to false at the first NMP attempt, which propagates all the way down the search tree.

I believe you don't want the line that says "can_null = false;"

[StackFish5]

Null move could be as simple as:

Code: Select all

  // null move
  // incheck test not needed if GenCapts() returns -MATE - ply
  eval = GetEval();
  if (eval >= beta && depth >= 3) {
    wtm = 1 - wtm;
    score = -Search(-beta - 1, -beta + 1, depth - 3);
    wtm = 1 - wtm;
    if (score >= beta) return beta;
  }
  

You could replace your null move code with something simple just to see if something is wrong with the null move code. And then go from there.

So you are suggesting to disregard the en passant square during the making of the null move?

[Henk]

Stupid to reduce when in the middle of a tactical combination.

[Ras]

But other than that, I do not know.

The issue might be anywhere in the code, and nullmove might only trigger it. Rather than pasting code excerpts that may not have anything to do with the segfault, I'd suggest looking into how to use GDB: http://www.unknownroad.com/rtfm/gdbtut/gdbsegfault.html

[Mike Sherwin]

Null move could be as simple as:

Code: Select all

  // null move
  // incheck test not needed if GenCapts() returns -MATE - ply
  eval = GetEval();
  if (eval >= beta && depth >= 3) {
    wtm = 1 - wtm;
    score = -Search(-beta - 1, -beta + 1, depth - 3);
    wtm = 1 - wtm;
    if (score >= beta) return beta;
  }
  

You could replace your null move code with something simple just to see if something is wrong with the null move code. And then go from there.

So you are suggesting to disregard the en passant square during the making of the null move?

No I'm not suggesting that. The code I gave is actual code from my engine. My engine does not require the en-passant square to be considered when making a null move. All I'm suggesting is to simplify null move or even remove it completely to see if null move is the problem.

[Ras]

All I'm suggesting is to simplify null move or even remove it completely to see if null move is the problem.

That was already described in the first posting of this thread, emphasis mine: "However, many bugs have been present within the chess engine succeeding the inclusion of null move pruning. I managed to solve all but one issue, in which it segfaults very regularly."

[alessandro]

I see that before applying the search in the null-move you just change the side to move but you keep the current ply in the search tree. This will overwrite the previous move made and saved in the search stack at the same ply.
I don't know the details of your implementation, but I would verify that first.

On the other hand, as a general debugging method, you can try from a specific fen position where you can constantly reproduce the problem and slowly isolate the bug.

[Werner Taelemans]

I managed to solve all but one issue, in which it segfaults very regularly.

P.S.

Code: Select all

inline void Legal_Moves::pop_null_move(){
        //Revert turn
        side_to_move ^= 1;
        //Set en passant vector back to original state before null move
        En_Passant_Sq.pop_back();
}

pop_back() on an empty vector leads to ugly segfaults.
I suggest that you try:

Code: Select all

if(En_Passant_Sq.size()>0){
        En_Passant_Sq.pop_back();
}