Null Move Fail

[CDaley11]

I just implemented the null move technique into my program, and it made my program start sucking at chess! Even though it was getting to plys of 10+ it failed to recognize simple captures or to protect its own pieces, even the queen. I am using a standard NegaMax algorithm with no other optimizations (except alpha beta). Here's the code I'm using for the null move:

Code: Select all

if ( !isCheck() && nullMoveAllowed ) {
     toggleTurn();
     int temp = -searchToDepth( depth + 3, -alpha, -beta, Null_Move_Not_Allowed ); // Additional 2 ply for the search, it also fails if I leave it at 1
     toggleTurn();
     if ( temp >= beta ) {
          return temp;
     }
}

This code comes right before it does its usual search of all moves, but after it has already checked to position for checkmate and stalemate.

[Hamfer]

Replace :
int temp = -searchToDepth( depth + 3, -alpha, -beta, Null_Move_Not_Allowed );

with :
int temp = -searchToDepth( depth - 3, -beta, -alpha, Null_Move_Not_Allowed );

[lucasart]

I just implemented the null move technique into my program, and it made my program start sucking at chess! Even though it was getting to plys of 10+ it failed to recognize simple captures or to protect its own pieces, even the queen. I am using a standard NegaMax algorithm with no other optimizations (except alpha beta). Here's the code I'm using for the null move:

Code: Select all

if ( !isCheck() && nullMoveAllowed ) {
     toggleTurn();
     int temp = -searchToDepth( depth + 3, -alpha, -beta, Null_Move_Not_Allowed ); // Additional 2 ply for the search, it also fails if I leave it at 1
     toggleTurn();
     if ( temp >= beta ) {
          return temp;
     }
}

This code comes right before it does its usual search of all moves, but after it has already checked to position for checkmate and stalemate.

I think the above would not only suck at chess, but simply crash eventually (stack overflow). You need to reduce the depth, not increase it. Also you must forbid to have consecutive null moves. If you allow consecutive null moves, it will suck too.

[lucasart]

I just implemented the null move technique into my program, and it made my program start sucking at chess! Even though it was getting to plys of 10+ it failed to recognize simple captures or to protect its own pieces, even the queen. I am using a standard NegaMax algorithm with no other optimizations (except alpha beta). Here's the code I'm using for the null move:

Code: Select all

if ( !isCheck() && nullMoveAllowed ) {
     toggleTurn();
     int temp = -searchToDepth( depth + 3, -alpha, -beta, Null_Move_Not_Allowed ); // Additional 2 ply for the search, it also fails if I leave it at 1
     toggleTurn();
     if ( temp >= beta ) {
          return temp;
     }
}

This code comes right before it does its usual search of all moves, but after it has already checked to position for checkmate and stalemate.

I think the above would not only suck at chess, but simply crash eventually (stack overflow). You need to reduce the depth, not increase it. Also you must forbid to have consecutive null moves. If you allow consecutive null moves, it will suck too.

Another mistake is the search window you use for recursive search. It should be (-beta,-alpha) and not (-alpha, -beta).

[CDaley11]

Thanks for your suggestions. As for the depth you are all worrying about, it is supposed to be like that. I am not decreasing the depth until it gets to zero, I am increasing it until it reaches the targeted depth. Also, it doesn't allow two null moves in a row. The problem actually was the beta and alpha being switched. Thank you for helping me out.

[lucasart]

Thanks for your suggestions. As for the depth you are all worrying about, it is supposed to be like that. I am not decreasing the depth until it gets to zero, I am increasing it until it reaches the targeted depth. Also, it doesn't allow two null moves in a row. The problem actually was the beta and alpha being switched. Thank you for helping me out.

This bug should have been spotted by an assert(). I strongly advise you to use assert() wherever relevant. It makes your code
1/ self-documenting
2/ self-debugging

For example, the beginning of my search() function looks like this:

Code: Select all

assert(depth >= 0);
assert(alpha < beta && (is_pv || alpha+1 == beta));

if (depth <= 0)
	return quiesce(...)

assert(depth >= 1);

In parciaular "assert(alpha < beta && (is_pv || alpha+1 == beta));" would have spotted the bug immediately, as well as many more potential bugs (like wrong node type passed to child when using PVS).

And even in plain and simple code, that looks straight forward, assert() are good. I cannot stress this enough, but let's take a fictitious example:

Code: Select all

if (piece == PAWN) {
	...
} else if (piece == KNIGHT) {
	...
} else if (piece is slider) {
	...
} else {
	assert(piece == KING);	// what else could it be
	...
}

This may seem like a trivial case, where the assert() is unnecessary pedantic code, but it's important for several reasons:
- self-documenting: what if the "..." are quite large and the whole code occupies several screen pages. Then when you are looking at the "else" portion, it is not self-obvious.
- self-debugging: OK initially you write code, and test it, and it works. And later on, you modify it, and screw things up. For example you remove the pawn case, because it becomes unnecessary. But you forgot that the else will then be called if it's a pawn, even though that code was written and tested with piece == KING in mind!
- another funny example. Suppose you write piece = PAWN instead of piece == PAWN, by accident (and let's assume the int value of PAWN is zero). You've introduced a deadly bug, and if you don't have an assert() your code may silently produce buggy results. Badly coded chess engines are full of silent bugs, and then they wonder why they can't exceed 2000 elo even though they have all the search techniques and eval stuff in there.

It's really by reading the source code of Fruit 2.1 back in 2004 that I changed my coding style, and understood the power and beauty of self-debugging & self-documenting code.

assert() and unit tests have saved my life countless times, and DiscoCheck would just be a buggy piece of crap without them.

[User923005]

I think that the most important contribution of Fruit (more even than the search and the evaluation methods) was the beautiful use of assert.
It is a good practice not only for chess programming but for any kind of programming.
I definitely benefited greatly from reading the Fruit code for that reason.

For algorithmic techniques, I think his pruning is the most important thing. While the evaluation is nice, Fruit is the first program that had a branching factor close to 2. I guess that if you put a simple evaluation in Fruit, like the one from Olithink, it will not change the Elo as much as reducing the pruning in such a way that the branching factor goes to 3.5 or so, which was common at the time.

As Christophe Theron put it, "Search is also knowledge".

[CDaley11]

Sorry, but what is assert()? I'm kinda a noob at this stuff compared to you guys.

[lucasart]

Sorry, but what is assert()? I'm kinda a noob at this stuff compared to you guys.

for C or C++
http://www.cplusplus.com/reference/cassert/assert/

[CDaley11]

Ahhh... Looks like a useful function. Too bad I have to write this in java for my class Although I could just implement my own version of it.