The many faces of Null Move Pruning

[jesper_nielsen]

Hello Good People!

Experimenting with null move pruning in my, still early, rewrite of Pupsi called Pupsi2, i found out, that my implementation of the "Verified Null Move Pruning" technique must have been flawed, somehow.

http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.pdf

When I changed to a standard R = 2 implementation, the engine started performing a lot better!

I made the same changes in Pupsi, and it looks like a substantial gain there aswell!

So what are your experience with verified null move pruning?
Have any of you gotten it to work "as advertised"?
Are there any undocumented requirements I might have missed?
It is not explicitely stated in the text, but i assume the research should be with the original values for alpha and beta?

Also i gathered some statistics regarding only doing null moves, when eval() is above beta. The test showed that only about 1 in 1000 null moves with eval() below beta actually resultet in a cutoff. (Too bad if that one is the one you reallly need! )

How many of you requires the evaluation to be above beta before doing a null move search?

Kind regards,
Jesper

[bob]

Hello Good People!

Experimenting with null move pruning in my, still early, rewrite of Pupsi called Pupsi2, i found out, that my implementation of the "Verified Null Move Pruning" technique must have been flawed, somehow.

http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.pdf

When I changed to a standard R = 2 implementation, the engine started performing a lot better!

I made the same changes in Pupsi, and it looks like a substantial gain there aswell!

So what are your experience with verified null move pruning?
Have any of you gotten it to work "as advertised"?
Are there any undocumented requirements I might have missed?
It is not explicitely stated in the text, but i assume the research should be with the original values for alpha and beta?

Also i gathered some statistics regarding only doing null moves, when eval() is above beta. The test showed that only about 1 in 1000 null moves with eval() below beta actually resultet in a cutoff. (Too bad if that one is the one you reallly need! )

How many of you requires the evaluation to be above beta before doing a null move search?

Kind regards,
Jesper

I tried it when it was originally published, and for me it did not work... it was slower and in testing it was always inferior to what I do now...

[hgm]

I think verified null-move pruning was supposed only to be competative cmpared to non-recursive null-move pruning, where you allow at most one null move per tree branch. In that case an advantage would come from the fact that you could do an irresponsibly large reduction on this null move, because you would catch errors during the verification. This verification had a lower reduction than with plain null move, but, unlike the former, would allow reductions deeper in the tree by other null moves.

Compared to recursive null move this advantage would not exist.

[MartinBryant]

I used to use verified but it was a pain to get it working right (might still have been buggy!) and I actually dropped it recently producing a small gain. (Glad to see it go tell you the truth )

Tried the eval thing a long while back but it didn't look good, but I didn't really test it properly. Maybe I should try putting it back in!

FWIW I think Fruit uses both.

[Ron Murawski]

I use a null move verification search and it works for me. NMV search overhead slows down my search by about 4%, but in actual games it plays stronger than plain null move. My null move and NMV search are not "standard".

my null move:

• * Up to 3 null moves allowed per search line (mostly twice) depending on search depth and game stage
  * Null-move reduction range R = 2->4.5 plies, depending on material and zugswang danger

my null-move verification search :

• * NMV search done to depth: (depth - R), where R is same as null move R
  * NMV search allowed to use null-move
  * for cutoffs, stores actual NMV search score into the hash
  * for cutoffs returns actual NMV search score, not beta

Warning: I have not compared my weird null-move/NMV search to standard null move in a long time...

Ron

[hgm]

Also i gathered some statistics regarding only doing null moves, when eval() is above beta. The test showed that only about 1 in 1000 null moves with eval() below beta actually resultet in a cutoff. (Too bad if that one is the one you reallly need! )

How many of you requires the evaluation to be above beta before doing a null move search?

I don't do null move if CurEval < Beta. It can only fail high if you have some irrefutable threat on the board, like a fork. This is very rare, and if you worry about missing that, it would probably pay off much more if you would recognize such threats in Eval. (In which case CurEval would be >= Beta, so you would automatically try the null move as well.)

[Pradu]

Also i gathered some statistics regarding only doing null moves, when eval() is above beta. The test showed that only about 1 in 1000 null moves with eval() below beta actually resultet in a cutoff. (Too bad if that one is the one you reallly need! )

How many of you requires the evaluation to be above beta before doing a null move search?

I don't do null move if CurEval < Beta. It can only fail high if you have some irrefutable threat on the board, like a fork. This is very rare, and if you worry about missing that, it would probably pay off much more if you would recognize such threats in Eval. (In which case CurEval would be >= Beta, so you would automatically try the null move as well.)

Doing nullmove on ALL nodes is not always bad. You will get good move ordering on CUT nodes from the "null-killers". For Buzz the improved move ordering gives a bigger boost to search than the extra overhead of the nullmove search. I'm also not doing IID, so perhaps for engines with IID this won't be as big an issue.

[hgm]

I guess it depends on the implemetation details of your engine, so testing it will always be decisive.

But the chance that a null move when CurEval < Beta will come up with a useful killer seems pretty bleak to me. Any move that is not an outright blunder will do to refute that null move, there is no need for the opponent to do anything constructive. If he could, he would just immediately reply with another null move, as his CurEval >= Beta. If not allowing two null moves in a row is what prevents him from doing this, he will just use any meaningless move in stead.

Unless a good one happens to lead your static move ordering. But then searching the normal moves would have found that easily as well.

[Pradu]

I guess it depends on the implemetation details of your engine, so testing it will always be decisive.

But the chance that a null move when CurEval < Beta will come up with a useful killer seems pretty bleak to me. Any move that is not an outright blunder will do to refute that null move, there is no need for the opponent to do anything constructive. If he could, he would just immediately reply with another null move, as his CurEval >= Beta. If not allowing two null moves in a row is what prevents him from doing this, he will just use any meaningless move in stead.

Unless a good one happens to lead your static move ordering. But then searching the normal moves would have found that easily as well.

Indeed what you say is true for zero windows. I guess doing nullmove always will help more when you're not doing zero window searches because then the condition for the opponent will be CurEval >= alpha+1. Nevertheless even with zero windows, doing nullmove unconditionally does seem to help. I don't allow two nullmoves as you say so it makes sure that the killer move isn't bad and that it's just decent. Also you might get more hash hits for later nullmoves. Here's some values from Buzz with the eval()>beta, qsearch()>beta and no conditions:

Code: Select all

13 11 11045 27892057 d4 d5 Nc3 Nc6 e4 dxe4 d5 Nb4 a3 Bg4 Qd2 e3 fxe3 <= no condition
13 11 11665 28345785 d4 d5 Nc3 Nc6 e4 dxe4 d5 Nb4 a3 Bg4 Qd2 e3 <= qsearch() >= beta
13 11 11875 29066260 d4 d5 Nc3 Nc6 e4 dxe4 d5 Nb4 a3 Bg4 Qd2 e3 <= eval() >= beta

And here are the conditions I use for nullmove

Code: Select all

	#ifdef NULLMOVE_PRUNING
		if(
			#ifdef NULLMOVE_NO_ALLNODE //Turned Off
			nodeType!=ALL_NODE &&
			#endif
			#ifdef NULLMOVE_NO_OPENNODE //Turned Off
			nodeType!=OPEN_NODE &&
			#endif
			#ifdef NULLMOVE_NO_MULTI_NULLMOVE //(No double nullmove)Turned on
			!extractSFNull(pos.SF) &&
			#endif
			#ifdef NULLMOVE_NO_BETAMATE  //Turned on
			beta<MATE_MIN &&
			#endif
			#ifdef NULLMOVE_DEPTH_LEFT_LIMIT //Turned on, dfl=2
			depth>=NULLMOVE_DEPTH_LEFT_LIMIT &&
			#endif
			!inCheck(pos,pos.side) && 
			popcnt(pos.PiecesSide[pos.side]&~(pos.Pieces[P]|pos.Pieces[K]))>PIECES_NULLMOVE_OFF
			
			#ifdef NULLMOVE_NO_QS_ABOVE_BETA
			&& qsearchRoot(&pos,alpha,beta,dfr)>=beta //I change the code here around
			#endif
			)

[hgm]

Should I understand from this that you would do the null-move search itself with an open window, if the node from which you start it has an open window?