Extended Null-Move Reductions

[jwes]

one more bit of info. Using this approach, and allowing null-move search with pawn-only endings is worth about -100 Elo, so this is not much of a verification good news test.

Just realized I reported that wrong. Using R=4 and doing null-move in KP endings is a -11 Elo deal in Crafty. Going to R=5 drops it to -100, again doing this in KP endings (my normal null-move only triggers if the side on move has a single piece or more...)

An idea I had was to allow null move if the side on move has no pieces if it is significantly down in material (I would guess more than a piece). The idea is that if you're lost anyway, it probably doesn't take zugzwang to beat you.

[edwardyu]

The thing with all null-move verification schemes is that zugzwangs are simply too rare in elo terms and good balance between verification search depth and reliable zugzwangs detection simply doesn't exist.

This is another myth to be debunked.

I don't know who is the fellow that come up with the idea that null verification search is needed for zugzwangs....and I also don't know how was it possible that a lot of people followed that statement blindly as dumb sheeps follow the shepherd.

Hint: null verification has nothing to do with zugzwangs, especially at very high depths.

You don't believe ? Ok, pick up all the positions where null search at big depth failed high and following verification failed low, print on your screen and try to find the zugzwang in them..you will be surprised you will find none (or very few).

If null verification has nothing to do with zugzwangs, what is it used for? I saw elo drop if I don't do null verification.

[bob]

one more bit of info. Using this approach, and allowing null-move search with pawn-only endings is worth about -100 Elo, so this is not much of a verification good news test.

Just realized I reported that wrong. Using R=4 and doing null-move in KP endings is a -11 Elo deal in Crafty. Going to R=5 drops it to -100, again doing this in KP endings (my normal null-move only triggers if the side on move has a single piece or more...)

An idea I had was to allow null move if the side on move has no pieces if it is significantly down in material (I would guess more than a piece). The idea is that if you're lost anyway, it probably doesn't take zugzwang to beat you.

Once the current batch of tests are done, I'll give that a check. In pawn-only endgames or not???

[bob]

The thing with all null-move verification schemes is that zugzwangs are simply too rare in elo terms and good balance between verification search depth and reliable zugzwangs detection simply doesn't exist.

This is another myth to be debunked.

I don't know who is the fellow that come up with the idea that null verification search is needed for zugzwangs....and I also don't know how was it possible that a lot of people followed that statement blindly as dumb sheeps follow the shepherd.

Hint: null verification has nothing to do with zugzwangs, especially at very high depths.

You don't believe ? Ok, pick up all the positions where null search at big depth failed high and following verification failed low, print on your screen and try to find the zugzwang in them..you will be surprised you will find none (or very few).

If null verification has nothing to do with zugzwangs, what is it used for? I saw elo drop if I don't do null verification.

There are positions where doing nothing is bad, and some where it is not so bad. The verification search is just an expensive way of reducing the number of wrong fail highs.

I removed verification from stockfish and saw a 2-3 elo improvement when I tested. I saw a slight reduction in Crafty's Elo when I added verification. I use R=3 everywhere in Crafty, and do null move at _all_ nodes so long as the current side has at least one piece and is not in check. Adding other restrictions or verification hurt elo in every case.

[michiguel]

Hi,
has anyone tried this?

http://www.omiddavid.com/pubs/nmr.pdf

if so what were your results and conclusions?
best regards,
Alvaro

I have been doing something similar with Gaviota for ~10 years. This is really not a new concept. See a discussion in 2002:

http://www.stmintz.com/ccc/index.php?id=210745
http://www.stmintz.com/ccc/index.php?id=210999

The top of the thread
http://www.stmintz.com/ccc/index.php?id=210702

This may not be the best for engine-engine contests, but something of that sort is useful for analysis. Losing some elo points is nothing compared to the potential problem of having blind spots, no matter how infrequent the programmer thinks those are. They are not that infrequent with the positions that humans feed the engines. That thread is one example.

Miguel

[jwes]

one more bit of info. Using this approach, and allowing null-move search with pawn-only endings is worth about -100 Elo, so this is not much of a verification good news test.

Just realized I reported that wrong. Using R=4 and doing null-move in KP endings is a -11 Elo deal in Crafty. Going to R=5 drops it to -100, again doing this in KP endings (my normal null-move only triggers if the side on move has a single piece or more...)

An idea I had was to allow null move if the side on move has no pieces if it is significantly down in material (I would guess more than a piece). The idea is that if you're lost anyway, it probably doesn't take zugzwang to beat you.

Once the current batch of tests are done, I'll give that a check. In pawn-only endgames or not???

Since you already do null moves when the side on move has a piece, try also doing null moves when the side on move has no pieces and is significantly down in material.

[michiguel]

Hi,
has anyone tried this?

http://www.omiddavid.com/pubs/nmr.pdf

if so what were your results and conclusions?
best regards,
Alvaro

I have been doing something similar with Gaviota for ~10 years. This is really not a new concept. See a discussion in 2002:

http://www.stmintz.com/ccc/index.php?id=210745
http://www.stmintz.com/ccc/index.php?id=210999

The top of the thread
http://www.stmintz.com/ccc/index.php?id=210702

This may not be the best for engine-engine contests, but something of that sort is useful for analysis. Losing some elo points is nothing compared to the potential problem of having blind spots, no matter how infrequent the programmer thinks those are. They are not that infrequent with the positions that humans feed the engines. That thread is one example.

Miguel

I found a 2001 Dieter Buerssner's post at the old WB forum where he mentions what he was doing in YACE (I reference that in the post above).

http://www.open-aurec.com/wbforum/viewt ... ove#p12641

It is an interesting twist compared to a verification search or a nullmove reduction, but basically the same (the order is switched):

"Yes. Also, disabling nullmove in late endgame, when in check and perhaps other cases. In Yace, I don't use double null move, as described by Vincent. Before the null move is done, I search the position at much reduced depth. Only when this gets a fail high, I try nullmove. But in principle, I believe this is the same thing.
There is also some indication, that in "real games", this does not really help. I believe, i.e. Fritz does not do this. When doing double nullmove or similar, you will get less nullmove cutoffs, and reach the same search depth only after longer time in general."

For a little while, YACE was the strongest amateur free engine, just above Crafty.

Miguel

[Pablo Vazquez]

For R=3 (first run) this appears to drop 24 Elo after 3,000 games. Will let it run to completion for accuracy. Also have R=4 and R=5 queued up since the paper uses R=4...

Code: Select all

 Crafty-23.4          2681    4    4 30000   66%  2557   22% 
 Crafty-23.3          2673    4    4 30000   65%  2557   22% 
 Crafty-23.4R01       2657   11   11  2730   64%  2551   23% 

One question about your implementation. When you finish the search and store in the transposition table, do you use the original depth or the reduced one?

[Gerd Isenberg]

The thing with all null-move verification schemes is that zugzwangs are simply too rare in elo terms and good balance between verification search depth and reliable zugzwangs detection simply doesn't exist.

This is another myth to be debunked.

I don't know who is the fellow that come up with the idea that null verification search is needed for zugzwangs....and I also don't know how was it possible that a lot of people followed that statement blindly as dumb sheeps follow the shepherd.

Hint: null verification has nothing to do with zugzwangs, especially at very high depths.

You don't believe ? Ok, pick up all the positions where null search at big depth failed high and following verification failed low, print on your screen and try to find the zugzwang in them..you will be surprised you will find none (or very few).

But isn't NM fails high but verification fails low the definition of zugzwang?

From Georgy Adelson-Velsky, Vladimir Arlazarov and Mikhail Donskoy (1975). Some Methods of Controlling the Tree Search in Chess Programs. Artificial Intelligence, Vol. 6, No. 4, pp. 361-371. ISSN 0004-3702.

2. The Order of Move Considerations:
A less trivial idea was that sometimes an extension of the game tree by introducing of dummy move can lead to a reduction of the search tree. In positions with material advantage (with respect to limits) it was permitted to try a so-called "blank" move in which ones own pieces are not moved. Certainly in positions with "Zugzwang" (the side to move must weaken his position) this may lead to errors.

However, the standard of the program's play is still such that such errors do not essentially lower it. (We plan to develop in the future a procedure for recognizing "Zugzwang" positions, and to forbid a blank move in them.) The reduction of search takes place in this case, because the blank move proves to be a closing one and furthermore does not generate complex forcing variations.

[Ralph Stoesser]

But isn't NM fails high but verification fails low the definition of zugzwang?

Yes, these are zugzwang positions by definition, within the (reduced) search horizon.
Maybe a few position examples from Marco could clear up the mystery..?