nullmove verification vs avoid null

[bob]

This is a well-known optimization, nothing more. Not related to verification or anything...

Then why it helps to solve the above mentioned positions? Without it, Crafty is blind in these. So it must be more than just an optimization. A side effect perhaps?

Certainly an unintentional side-effect...

IF the positions contain zugzwang, not doing a null is a perfect defense to making such errors. IE the hash table suggests the null-move won't fail high, but in reality it will because the side on move is in zugzwang. But that's not the reason for the trick, it is to avoid null-moves searches that fail low and waste nodes...

[lucasart]

Nullmove verification helps in some (not all) problematic positions, like these (taken from a testsuite - I believe these should be attributed to Gerd Isenberg):

8/8/1p1r1k2/p1pPN1p1/P3KnP1/1P6/8/3R4 b - -
4KBkr/7p/6PP/4P3/8/3P1p2/8/8 w - -

However verification costs some elo (in my case 3 +-5 so nothing dramatic)
I know that Bob doesn't use verification search but Crafty has no problem with the above positions.
To my suprise (always thought it's just an optimization), removing avoid null from Crafty made it blind in these positions
so it's obvious that null verification and avoid null flag actually accomplish the same.
So I wonder whether using a similar approach (avoid null flag in TT entry) would do better than verification search.
Any opinions?

How is avoid null flag actually used? I have never heard of that one. Is it used when the hash table score is based on a null move search at this node?

No. If you get a hash signature match, but the draft of the entry is not enough to let you use the entry, you can still check to see what happened (for example, did the previous search fail low (store UPPER bound)? If so, is the draft comparable to the null-move remaining depth (depth - 1 - REDUCTION (3 for me). If the depth is enough, and we failed low on a real move, we are almost certainly going to fail low on a null-move, which is theoretically worse than any possible move unless we are in zugzwang, so there is no point in doing the null-search and wasting effort...

This is a well-known optimization, nothing more. Not related to verification or anything...

How often does that happen, in practice ?
Did it really make a measurable ELO impact in Crafty ?

I've implemented it in Stockfish, and results don't look promising, so far
http://tests.stockfishchess.org/tests/v ... 749a54acec

[mar]

I've implemented it in Stockfish, and results don't look promising, so far
http://tests.stockfishchess.org/tests/v ... 749a54acec

Maybe in combination with the removal of null verification. Just a random idea but obviously this optimization has a useful side effect.

[bob]

Nullmove verification helps in some (not all) problematic positions, like these (taken from a testsuite - I believe these should be attributed to Gerd Isenberg):

8/8/1p1r1k2/p1pPN1p1/P3KnP1/1P6/8/3R4 b - -
4KBkr/7p/6PP/4P3/8/3P1p2/8/8 w - -

However verification costs some elo (in my case 3 +-5 so nothing dramatic)
I know that Bob doesn't use verification search but Crafty has no problem with the above positions.
To my suprise (always thought it's just an optimization), removing avoid null from Crafty made it blind in these positions
so it's obvious that null verification and avoid null flag actually accomplish the same.
So I wonder whether using a similar approach (avoid null flag in TT entry) would do better than verification search.
Any opinions?

How is avoid null flag actually used? I have never heard of that one. Is it used when the hash table score is based on a null move search at this node?

No. If you get a hash signature match, but the draft of the entry is not enough to let you use the entry, you can still check to see what happened (for example, did the previous search fail low (store UPPER bound)? If so, is the draft comparable to the null-move remaining depth (depth - 1 - REDUCTION (3 for me). If the depth is enough, and we failed low on a real move, we are almost certainly going to fail low on a null-move, which is theoretically worse than any possible move unless we are in zugzwang, so there is no point in doing the null-search and wasting effort...

This is a well-known optimization, nothing more. Not related to verification or anything...

How often does that happen, in practice ?
Did it really make a measurable ELO impact in Crafty ?

I've implemented it in Stockfish, and results don't look promising, so far
http://tests.stockfishchess.org/tests/v ... 749a54acec

I really have not tested it independently of anything else. I will queue up a couple of test runs right now, with the disable-null-move disabled...

More in the AM.

[jd1]

How often does that happen, in practice ?
Did it really make a measurable ELO impact in Crafty ?

I've implemented it in Stockfish, and results don't look promising, so far
http://tests.stockfishchess.org/tests/v ... 749a54acec

FWIW, in Toga I use exactly the same flag that Crafty uses. It scored 50.7% in 10000 games self-play, so it likely was a small improvement.

Jerry

[lucasart]

How often does that happen, in practice ?
Did it really make a measurable ELO impact in Crafty ?

I've implemented it in Stockfish, and results don't look promising, so far
http://tests.stockfishchess.org/tests/v ... 749a54acec

FWIW, in Toga I use exactly the same flag that Crafty uses. It scored 50.7% in 10000 games self-play, so it likely was a small improvement.

Jerry

I am convinced that Bob's avoid null move trick is right, at least in theory:
* when the TT tells you that no move will beat alpha, a fortiori a null move won't, so the null search can safely be skipped
* in cases of zugzwang where the null search would fail high, it's actually better, because we've saved ourselves the blunder of returning a fail high after the null search in a zugzwang.

But in practice, I am worried that it happens so rarely, it may not justify the extra code and complexity.

In 15"+0.05", the patch passed the pre-filter with a score of 50.22% after 63k games. It indicates some small positive effect, but probably not enough to commit (patches that add complexity like that need to justify with some non trivial elo gain).

[lucasart]

How frequently the condition occurs, probably depends a lot on what the TT replacement scheme is. Maybe it is more useful in Crafty and Toga, because the TT replacement scheme is different. I don't know.

[jd1]

How frequently the condition occurs, probably depends a lot on what the TT replacement scheme is. Maybe it is more useful in Crafty and Toga, because the TT replacement scheme is different. I don't know.

Here are some stats for Toga (latest development version):

- depth 10 search, startpos:
avoid null flag = true: 84
do null: 14873

- depth 19 search, startpos:
avoid null flag = true: 22525
do null: 2701140

- depth 21 search startpos:
avoid null flag = true: 47851
do null: 8496896

I'm not sure what it is like for Stockfish or Crafty.

Jerry

[bob]

Nullmove verification helps in some (not all) problematic positions, like these (taken from a testsuite - I believe these should be attributed to Gerd Isenberg):

8/8/1p1r1k2/p1pPN1p1/P3KnP1/1P6/8/3R4 b - -
4KBkr/7p/6PP/4P3/8/3P1p2/8/8 w - -

However verification costs some elo (in my case 3 +-5 so nothing dramatic)
I know that Bob doesn't use verification search but Crafty has no problem with the above positions.
To my suprise (always thought it's just an optimization), removing avoid null from Crafty made it blind in these positions
so it's obvious that null verification and avoid null flag actually accomplish the same.
So I wonder whether using a similar approach (avoid null flag in TT entry) would do better than verification search.
Any opinions?

How is avoid null flag actually used? I have never heard of that one. Is it used when the hash table score is based on a null move search at this node?

No. If you get a hash signature match, but the draft of the entry is not enough to let you use the entry, you can still check to see what happened (for example, did the previous search fail low (store UPPER bound)? If so, is the draft comparable to the null-move remaining depth (depth - 1 - REDUCTION (3 for me). If the depth is enough, and we failed low on a real move, we are almost certainly going to fail low on a null-move, which is theoretically worse than any possible move unless we are in zugzwang, so there is no point in doing the null-search and wasting effort...

This is a well-known optimization, nothing more. Not related to verification or anything...

How often does that happen, in practice ?
Did it really make a measurable ELO impact in Crafty ?

I've implemented it in Stockfish, and results don't look promising, so far
http://tests.stockfishchess.org/tests/v ... 749a54acec

I really have not tested it independently of anything else. I will queue up a couple of test runs right now, with the disable-null-move disabled...

More in the AM.

Got the results this morning. This is one of those plus 2-3 Elo things. Very small, but also a very simple idea that very slightly reduces the size of the tree overall...

[bob]

How often does that happen, in practice ?
Did it really make a measurable ELO impact in Crafty ?

I've implemented it in Stockfish, and results don't look promising, so far
http://tests.stockfishchess.org/tests/v ... 749a54acec

FWIW, in Toga I use exactly the same flag that Crafty uses. It scored 50.7% in 10000 games self-play, so it likely was a small improvement.

Jerry

I am convinced that Bob's avoid null move trick is right, at least in theory:
* when the TT tells you that no move will beat alpha, a fortiori a null move won't, so the null search can safely be skipped
* in cases of zugzwang where the null search would fail high, it's actually better, because we've saved ourselves the blunder of returning a fail high after the null search in a zugzwang.

But in practice, I am worried that it happens so rarely, it may not justify the extra code and complexity.

In 15"+0.05", the patch passed the pre-filter with a score of 50.22% after 63k games. It indicates some small positive effect, but probably not enough to commit (patches that add complexity like that need to justify with some non trivial elo gain).

This doesn't add significantly to complexity.

The tt test looks like this:

Code: Select all

    if ((type & UPPER) && depth - null_depth - 1 <= draft && val < beta)
      avoid_null = AVOID_NULL_MOVE;

When I call HashProbe, that "AVOID_NULL" constant is returned and tested:

Code: Select all

    switch (HashProbe(tree, ply, depth, wtm, alpha, beta, &value)) {
      case HASH_HIT:
        return (value);
      case AVOID_NULL_MOVE:
        do_null = 0;
      case HASH_MISS:
        break;
    }

do_null is passed in to search as a 1, unless the move at the previous ply is a null-move, which causes a zero to be passed in...

This adds a total of 4 lines of code, which includes one non-executable label. Seems worth it to get 2-3 elo...