LMR and null move selectivity

[Don]

If that isn't clear, let me know and I will do a more formal explanation.

Could you please do a more formal explanation ? I got the idea but I think I still miss the details.

Thanks in advance
Marco

Sure. First the code from hash.c:

at the top of HashProbe():

avoid_null = 0;

In hash probe after I have matched the signature to prove this is the correct entry:

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

Explanation:

type = 0 Entry is "worthless"
type = 1 Entry is LOWER, that is, the search that produced this entry failed high, which means the bound given in the entry is a lower bound for the true result and it might be higher (this table bound was the "beta" value when the search failed high, so we know the score is >= this beta value, but we do not know how much better it might be).
type = 2 Entry is UPPER, that is, the search that produced this entry failed low, which means the bound given in the entry is an upper bound for the true result, which might be even lower than this bound (this is the value of alpha where the searched failed low).
type = 3 Entry is EXACT, which means this is a true score.

type & UPPER will be true if this is an EXACT score or UPPER bound.

The normal null search is to depth - null-depth - 1, so I compare this value to the draft to make sure that the draft is at least this deep, or better, or I can't make this test work.

val < beta simply asks "Is the table value < beta" which is another way of asking "If I search to depth - null-depth -1, is the resulting value going to be < beta? If so, the null-search will not fail high and there is no point in doing it.

If I exit the HashProbe() function without being able to return a "show-stopper" type result (a result that will terminate the search with no further effort required) I then return the "avoid_null_ value above rather than "0" where the 0 says "no useful hash information found..."

If avoid_null == 1, then I skip the null-move search completely, no matter what else might be done.

For Don:

Got the cluster test running. WIll report some 40K game results this evening to compare Crafty with and without this feature. I suspect it will be small, but measurable with 40K games.

Thanks Bob, I'm definitely interested in seeing the result of that.

[Gerd Isenberg]

at the top of HashProbe():

Code: Select all

avoid_null = 0;

In hash probe after I have matched the signature to prove this is the correct entry:

Code: Select all

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

Thanks for explaining your implementation. Do you store avoid_null inside the hash?

[Tord Romstad]

It is one of those things that is obviously correct,

It is only "obviously correct" if you don't use the null move search for anything besides pruning. Without the threat move returned by the null move search, it is harder to forward prune safely.

Another factor worth noting is that in the cases where this trick can be applied, the null move search will normally be even cheaper than usual, because most branches of the subtree will be pruned directly by transposition table lookups. I think a few extra nodes searched is a fair price to pay for getting a good threat move.

But of course, intuition isn't a very reliable tool in this case, and the only way to know is to test.

[mcostalba]

If that isn't clear, let me know and I will do a more formal explanation.

Could you please do a more formal explanation ? I got the idea but I think I still miss the details.

Thanks in advance
Marco

Sure.

Thanks for your explanation.

I have measured some quick statistics and it seems that with this trick would be possible to avoid about 5% of null move searches (not a biggie indeed given that null searches are already a small percent of total search time).

It is anyhow interesting to see that is not 100% accurate because a very small percent of null moves that satisfy the conditions fail high the same also if they shouldn't, about 340 on more then 120K so less then 0.3%

I didn't had the time to further analyse what kind of positions fail the rule.

[rvida]

It is anyhow interesting to see that is not 100% accurate because a very small percent of null moves that satisfy the conditions fail high the same also if they shouldn't, about 340 on more then 120K so less then 0.3%

I didn't had the time to further analyse what kind of positions fail the rule.

It can fail because you dont know which node type the hash entry comes from. An entry from a (former) PV node was reduced less, with more accurate result. Result from more reduced non-PV search of that node may differ.

[Zach Wegner]

If that isn't clear, let me know and I will do a more formal explanation.

Could you please do a more formal explanation ? I got the idea but I think I still miss the details.

Thanks in advance
Marco

Sure.

Thanks for your explanation.

I have measured some quick statistics and it seems that with this trick would be possible to avoid about 5% of null move searches (not a biggie indeed given that null searches are already a small percent of total search time).

It is anyhow interesting to see that is not 100% accurate because a very small percent of null moves that satisfy the conditions fail high the same also if they shouldn't, about 340 on more then 120K so less then 0.3%

I didn't had the time to further analyse what kind of positions fail the rule.

Actually, when it "fails", it's a good thing. If the bound in the hash table has the UPPER bit, then it wasn't from a null move search since it failed low. So if the normal search failed low but null move will fail high, then you have a zugzwang-type position (or just some search stability noise), and you don't want to null move at all.

EDIT: what you might actually want to do is, if you're null-moving despite whatever's in the hash, and it fails according to the above, store a "zugzwang" bit in the hash table, and THEN don't null-move next time. You still don't get the threat move though, so maybe just don't accept the cutoffs from null move if the hash table says not to. Or maybe a separate "zugzwang threat move" table

[BubbaTough]

This is a good idea to try...I don't remember trying it before. My instinct is that engines with conservative null move / LMR depths will not benefit from being even more conservative...but that maybe folks with more aggressive approaches (say, folks that ramp up LMR and null move a lot depending on position) might. Thus, I expect it would hurt engines like Crafty or DIEP, but perhaps engines like LearningLemming, Weid, or ZCT (or Now?) would benefit. I will run a few tests and report back (nothing as comprehensive as Bob's test of course).

-Sam

EDIT:

Preliminary result 1. Tactical testbed of 86 moves at 8 seconds a move:

Normal: 69 / 86 4:34
don't LMR when null moving: 66/86 4:59

Hmmm....not that promising. I'll try some games

Normal:
games at short time control: 328 / 700
longer: 428/800
total: 754/1500
no LMR when null moving:
short: 340.5/700
longer: 402.5/800
total 743/1500

It looks probable that it does not help, even for aggressive reduction engines such as mine.

-Sam

The problem I see in the above is that this is not a big Elo booster. Which means you need way more than 800 games to measure the actual effect...

I think you mean way more than 1500 games to measure the effect . Of course, that may well be true...but those of us with lesser resources must muddle through the best we can. Luckily, its not like I am looking for 99% probability of improvement measures to justify publishing my results in a journal or something...I just ran enough to give myself a feel (combined with tactical testbed results) and moved on.

-Sam

[Edsel Apostol]

It is one of those things that is obviously correct,

It is only "obviously correct" if you don't use the null move search for anything besides pruning. Without the threat move returned by the null move search, it is harder to forward prune safely.

Another factor worth noting is that in the cases where this trick can be applied, the null move search will normally be even cheaper than usual, because most branches of the subtree will be pruned directly by transposition table lookups. I think a few extra nodes searched is a fair price to pay for getting a good threat move.

But of course, intuition isn't a very reliable tool in this case, and the only way to know is to test.

Hi Tord, how much improvement do you get from using null move threat to re-search a reduced move when the null move verification fails low? I tried that idea but I can't see any improvement on my engine. Note that I'm doing null move only when the position's eval is greater than or equal to beta. Is there an advantage in doing null move when the position's eval is less than beta?

[bob]

at the top of HashProbe():

Code: Select all

avoid_null = 0;

In hash probe after I have matched the signature to prove this is the correct entry:

Code: Select all

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

Thanks for explaining your implementation. Do you store avoid_null inside the hash?

No. It is simply a by-product of a probe where the hash table entry has insufficient draft (remaining depth) to terminate the search, but does have enough draft, and a score that proves that a null-move search could not fail high.

[bob]

If that isn't clear, let me know and I will do a more formal explanation.

Could you please do a more formal explanation ? I got the idea but I think I still miss the details.

Thanks in advance
Marco

Sure.

Thanks for your explanation.

I have measured some quick statistics and it seems that with this trick would be possible to avoid about 5% of null move searches (not a biggie indeed given that null searches are already a small percent of total search time).

It is anyhow interesting to see that is not 100% accurate because a very small percent of null moves that satisfy the conditions fail high the same also if they shouldn't, about 340 on more then 120K so less then 0.3%

I didn't had the time to further analyse what kind of positions fail the rule.

I don't see how that could happen. Null-move searches only fail high when our current position is so good that even if we don't make a move we are still winning. I don't see how the hash table could say "score is <= X yet a null-move search could fail high." _UNLESS_ you are catching zugzwang positions, since that can certainly happen in those, and represent an error to boot.