Value of Null Move...

[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.

3) Yes I found a or maybe the bug (not updating last move when doing a null move, not testing last move <> null before applying null move pruning). I repaired the bug. Looks like this changes a lot. Can even think of testing LMR again for things have changed now.

[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.

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.

Ok, let's try it again.

1) If all moves of the parent fail low, the parent won't return ANY move, at least if your search is similar to this basic search:

Code: Select all

int  alphabeta(int depth, int alpha, int beta){

	if (depth==0 ) {
		return quies_search (QUIES_DEPTH, alpha, beta);			
	}
	
	int max=alpha;
	MoveType best_move = NULL_MOVE;
	MoveType move;

	int value =0;
	int legalmoves =0;
	bool is_check = board_is_check ();

	sort_init_position(... );
	while &#40;max < beta && &#40;move = next_move&#40;..))!=NULL_MOVE&#41;&#123;

		move_do&#40;move&#41;;
		if ( board_illegal_king&#40;))&#123;
			move_undo&#40;);
			continue;
		&#125;
		legalmoves++;
		value = - alphabeta&#40;depth-1, -beta, -max&#41;;
		move_undo&#40;);

		if &#40;value > max )&#123;			
			max = value;
			best_move = move;
		&#125;
	&#125;

	
	//finally, checkmate or slatemate
	if &#40;legalmoves == 0 )&#123;
		if &#40;is_check&#41;&#123;						
			return -MATE0; //check mate
		&#125;else&#123;
			return 0; //slatemate
		&#125;
	&#125;
	return max;

&#125;

This was a concept hard for me to understand, but is true that at some nodes, you can't find a move that improves alpha. These nodes are called All-nodes. You can find more discussions about all-nodes and cut-nodes here in this forum.


2) the basis of the null move pruning is that you want to verify that a position considered to be good, is so good that, letting your opponent do a second move, his double-move doesn't hurts you, so there's no need to search at full depth. This verification is done by doing a null move and searching with reduced depth.
It is logical that in order to save search effort, you can ask your eval if your position is somehow good before doing a costly search.
Also, if you are in check the position is still very dynamic, so you can't be sure that your position is good enough to return beta. If you are checked, you can be mated, and then, Why to bother about returning beta?? Try to escape from any mate, so do a normal search and don't worry about any null-move.

I think that this answers everything.

[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.

Ok, let's try it again.

1) If all moves of the parent fail low, the parent won't return ANY move, at least if your search is similar to this basic search:

Code: Select all

int  alphabeta(int depth, int alpha, int beta){

	if (depth==0 ) {
		return quies_search (QUIES_DEPTH, alpha, beta);			
	}
	
	int max=alpha;
	MoveType best_move = NULL_MOVE;
	MoveType move;

	int value =0;
	int legalmoves =0;
	bool is_check = board_is_check ();

	sort_init_position(... );
	while &#40;max < beta && &#40;move = next_move&#40;..))!=NULL_MOVE&#41;&#123;

		move_do&#40;move&#41;;
		if ( board_illegal_king&#40;))&#123;
			move_undo&#40;);
			continue;
		&#125;
		legalmoves++;
		value = - alphabeta&#40;depth-1, -beta, -max&#41;;
		move_undo&#40;);

		if &#40;value > max )&#123;			
			max = value;
			best_move = move;
		&#125;
	&#125;

	
	//finally, checkmate or slatemate
	if &#40;legalmoves == 0 )&#123;
		if &#40;is_check&#41;&#123;						
			return -MATE0; //check mate
		&#125;else&#123;
			return 0; //slatemate
		&#125;
	&#125;
	return max;

&#125;

This was a concept hard for me to understand, but is true that at some nodes, you can't find a move that improves alpha. These nodes are called All-nodes. You can find more discussions about all-nodes and cut-nodes here in this forum.


2) the basis of the null move pruning is that you want to verify that a position considered to be good, is so good that, letting your opponent do a second move, his double-move doesn't hurts you, so there's no need to search at full depth. This verification is done by doing a null move and searching with reduced depth.
It is logical that in order to save search effort, you can ask your eval if your position is somehow good before doing a costly search.
Also, if you are in check the position is still very dynamic, so you can't be sure that your position is good enough to return beta. If you are checked, you can be mated, and then, Why to bother about returning beta?? Try to escape from any mate, so do a normal search and don't worry about any null-move.

I think that this answers everything.

1) My search is different I initialize max = -GAME_OVER and not max = alfa.

There is also something as fail soft and fail hard. I don't remember clearly. I have to look it up. I forget too easily.

[sedicla]

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

Hi Steve,

You may also consider not calling eval for all moves. I had that in my engine and it was very expensive. In the context for futility pruning I changed to call only when needed, I mean, when I got to the first candidate move for pruning (quiet, not killer, etc.).