Value of Null Move...

[Steve Maughan]

I added a simple null move routine to Maverick. If I remember correctly, when I added this to Monarch it game about +1 ply and close to 100 ELO. With Maverick the ELO gain is only about 16 ELO (after 600 games). I haven't added hash tables yet - would they enhance the impact of null move (I doubt it).

Here's the code:

Code: Select all

	if (can_do_null_move(board, pv, ply, alpha, beta)){

		//-- Make the changes on the board
		make_null_move(board, undo);

		//-- Store the move in the PV data
		pv->current_move = NULL;

		//-- Evaluate the new board position
		evaluate(board, next_pv->eval);

		//-- Find the new score
		e = -alphabeta(board, ply + 1, depth - NULL_REDUCTION - 1, -beta, -beta + 1);

		//-- undo the null move
		unmake_null_move(board, undo);

		//-- is it good enough for a cut-off?
		if (e >= beta)
			return e;
	}

Am I missing something? The "can_do_null_move" function returns true if not in check, not a PV.

Steve

[asanjuan]

I added a simple null move routine to Maverick. If I remember correctly, when I added this to Monarch it game about +1 ply and close to 100 ELO. With Maverick the ELO gain is only about 16 ELO (after 600 games). I haven't added hash tables yet - would they enhance the impact of null move (I doubt it).

Here's the code:

Code: Select all

	if (can_do_null_move(board, pv, ply, alpha, beta)){

		//-- Make the changes on the board
		make_null_move(board, undo);

		//-- Store the move in the PV data
		pv->current_move = NULL;

		//-- Evaluate the new board position
		evaluate(board, next_pv->eval);

		//-- Find the new score
		e = -alphabeta(board, ply + 1, depth - NULL_REDUCTION - 1, -beta, -beta + 1);

		//-- undo the null move
		unmake_null_move(board, undo);

		//-- is it good enough for a cut-off?
		if (e >= beta)
			return e;
	}

Am I missing something? The "can_do_null_move" function returns true if not in check, not a PV.

Steve

static_eval > beta?
depth >= NULL_REDUCTION +1 ?

[asanjuan]

I added a simple null move routine to Maverick. If I remember correctly, when I added this to Monarch it game about +1 ply and close to 100 ELO. With Maverick the ELO gain is only about 16 ELO (after 600 games). I haven't added hash tables yet - would they enhance the impact of null move (I doubt it).

Here's the code:

Code: Select all

	if (can_do_null_move(board, pv, ply, alpha, beta)){

		//-- Make the changes on the board
		make_null_move(board, undo);

		//-- Store the move in the PV data
		pv->current_move = NULL;

[b]		//-- Evaluate the new board position
		evaluate(board, next_pv->eval);[/b]

		//-- Find the new score
		e = -alphabeta(board, ply + 1, depth - NULL_REDUCTION - 1, -beta, -beta + 1);

		//-- undo the null move
		unmake_null_move(board, undo);

		//-- is it good enough for a cut-off?
		if (e >= beta)
			return e;
	}

Am I missing something? The "can_do_null_move" function returns true if not in check, not a PV.

Steve

static_eval > beta?
depth >= NULL_REDUCTION +1 ?

I don't understand why you evaluate the board after calling make_null_move(..).
In Rhetoric I need to call eval() to check if I can enter into the null-move search.
My code is something like:

Code: Select all

	int R=3;
	// null move pruning
	if (!is_check  
		&& can_nullmove // info from TT and last move was not null-move too
		&& !isMate(beta)
		&& OutputDepth >= 4
		&& board_eval > beta		
		&& board_has_pieces()		
		){
			int eval_reduced;			
			int null_prof = max(1,depth - R -1);
			
			move_do_null ();
			eval_reduced= - search_scout( null_prof, -(beta-1), node_type);
			move_undo ();
			if (eval_reduced >= beta){
				return beta;
			}
			MoveType threat = pv_get_best();
			if (threat != NULL_MOVE) threat_sq = To(threat); 
			
	} //end null move

[cetormenter]

Check to make sure you are not calling two null moves in a row?

[Steve Maughan]

Hi Alberto,

(...)I don't understand why you evaluate the board after calling make_null_move(..).

In Maverick the board is *always* evaluated before alphabeta is called. When I eventually add LMR I think it will be of value when deciding if there should be a depth reduction.

Your implementation of null move is more restrictive. I'll give it a try.

Thanks,

Steve

[Henk]

1) If null move gives a value >= beta
should you return beta or return value.
Makes a difference.

2) Why test if king is in check. If it is, king is captured and null move just fails low. So why bother.

3) I don't test if last move was not a null move before entering null move pruning. I do not notice any difference if I add that condition.

[bob]

I added a simple null move routine to Maverick. If I remember correctly, when I added this to Monarch it game about +1 ply and close to 100 ELO. With Maverick the ELO gain is only about 16 ELO (after 600 games). I haven't added hash tables yet - would they enhance the impact of null move (I doubt it).

Here's the code:

Code: Select all

	if (can_do_null_move(board, pv, ply, alpha, beta)){

		//-- Make the changes on the board
		make_null_move(board, undo);

		//-- Store the move in the PV data
		pv->current_move = NULL;

		//-- Evaluate the new board position
		evaluate(board, next_pv->eval);

		//-- Find the new score
		e = -alphabeta(board, ply + 1, depth - NULL_REDUCTION - 1, -beta, -beta + 1);

		//-- undo the null move
		unmake_null_move(board, undo);

		//-- is it good enough for a cut-off?
		if (e >= beta)
			return e;
	}

Am I missing something? The "can_do_null_move" function returns true if not in check, not a PV.

Steve

I did a quantitative evaluation of these things a few years back. Things interact quite a bit. For example, removing null-move from crafty, by itself, costs me about 40 elo. Removing LMR by itself costs about 40 elo. Removing both costs about 120 elo. If you work the other way, adding either null move or LMR is worth 80, but once you have added one, adding the other only gains another 40 or so.

If you think about it, it makes sense, since BOTH reduce the size of the tree by reducing the average search depth.

If you are only getting +18 in a fairly new program, that suggests some sort of bug or else less than optimal implementation...

[asanjuan]

1) If null move gives a value >= beta
should you return beta or return value.
Makes a difference.

2) Why test if king is in check. If it is, king is captured and null move just fails low. So why bother.

3) I don't test if last move was not a null move before entering null move pruning. I do not notice any difference if I add that condition.

1) if you return beta or a value>=beta, on both cases the move at the parent node will fail low. So there's no difference.

2) if you don't test if the king is in check, your opponent will take the king and this is illegal. Also, you can't be sure that you are in a good position before return beta.

3)if you don't test if the previous move in the move stak was a null move, without any other restriction, you could be doing two null moves, and is the same that search over the same position, but with a 2*R reduction. You can be return beta, but losing a lot of information.
I am sure that there are more reasons.

[Henk]

1) If null move gives a value >= beta
should you return beta or return value.
Makes a difference.

2) Why test if king is in check. If it is, king is captured and null move just fails low. So why bother.

3) I don't test if last move was not a null move before entering null move pruning. I do not notice any difference if I add that condition.

1) if you return beta or a value>=beta, on both cases the move at the parent node will fail low. So there's no difference.

2) if you don't test if the king is in check, your opponent will take the king and this is illegal. Also, you can't be sure that you are in a good position before return beta.

3)if you don't test if the previous move in the move stak was a null move, without any other restriction, you could be doing two null moves, and is the same that search over the same position, but with a 2*R reduction. You can be return beta, but losing a lot of information.
I am sure that there are more reasons.

1) if all moves at the parent fail low, the parent node will have the value of the best move of all these moves failing low

2) capturing king is legal in my program. Don't know what you mean with "
Also, you can't be sure that you are in a good position before return beta"

3) I made a mistake. My chess program doesn't update last move when doing a null move.

[Steve Maughan]

Hi Bob,

(...)If you are only getting +18 in a fairly new program, that suggests some sort of bug or else less than optimal implementation...

This is my fear!

Thanks for the input - useful!

Steve