LMR and null move selectivity

[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

[mjlef]

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

Thanks Sam,

Especially for publishing the number of games. Often people post vague replies like "it does not work for my program", but then they do not give the test criteria. Having things like specific game results gives us a better measure to know how likley a given result is.

Mark

[bob]

Doesn't seem to hurt. But doesn't help either.

That's true when it comes down to LMR. For null move i would say that there is a noticeable difference.I mean "if(!pvnode)" for null move definitely hurts. I'm talking about my own tests of course. May be someone would disagree.

Same for me. _any_ restriction on where Null-move is tried, with the exception of the transposition table trick, hurts performance in my cluster testing.

[Don]

Doesn't seem to hurt. But doesn't help either.

That's true when it comes down to LMR. For null move i would say that there is a noticeable difference.I mean "if(!pvnode)" for null move definitely hurts. I'm talking about my own tests of course. May be someone would disagree.

Same for me. _any_ restriction on where Null-move is tried, with the exception of the transposition table trick, hurts performance in my cluster testing.

What is the transposition table trick?

I am now NOT reducing any move after a null move. This is mostly due to superstition. In testing it comes out 1 or 2 ELO stronger but with a margin of error much greater (about 5) so it's not clear whether it's any kind of benefit or not.

[bob]

Doesn't seem to hurt. But doesn't help either.

That's true when it comes down to LMR. For null move i would say that there is a noticeable difference.I mean "if(!pvnode)" for null move definitely hurts. I'm talking about my own tests of course. May be someone would disagree.

Same for me. _any_ restriction on where Null-move is tried, with the exception of the transposition table trick, hurts performance in my cluster testing.

What is the transposition table trick?

I am now NOT reducing any move after a null move. This is mostly due to superstition. In testing it comes out 1 or 2 ELO stronger but with a margin of error much greater (about 5) so it's not clear whether it's any kind of benefit or not.

This was first mentioned by someone I do not remember. The idea is this...

When you do a hash probe, often the draft is not sufficient and you can use the best move, but not the score/bound. But if you take the current depth, and subtract the usual null-move depth from it, you check the draft against this limit, which is what you will do in a null-move search anyway. If the draft is now sufficient, but the probe result says the score or bound will _not_ fail high here, then we just proved that a null-move search would not fail high here either. I return a flag "avoid_null = 1" to Search() which then refuses to try the null-move since we know it will be wasted.

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

[bob]

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...

[Don]

Doesn't seem to hurt. But doesn't help either.

That's true when it comes down to LMR. For null move i would say that there is a noticeable difference.I mean "if(!pvnode)" for null move definitely hurts. I'm talking about my own tests of course. May be someone would disagree.

Same for me. _any_ restriction on where Null-move is tried, with the exception of the transposition table trick, hurts performance in my cluster testing.

What is the transposition table trick?

I am now NOT reducing any move after a null move. This is mostly due to superstition. In testing it comes out 1 or 2 ELO stronger but with a margin of error much greater (about 5) so it's not clear whether it's any kind of benefit or not.

This was first mentioned by someone I do not remember. The idea is this...

When you do a hash probe, often the draft is not sufficient and you can use the best move, but not the score/bound. But if you take the current depth, and subtract the usual null-move depth from it, you check the draft against this limit, which is what you will do in a null-move search anyway. If the draft is now sufficient, but the probe result says the score or bound will _not_ fail high here, then we just proved that a null-move search would not fail high here either. I return a flag "avoid_null = 1" to Search() which then refuses to try the null-move since we know it will be wasted.

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

Thanks for the explanation Bob. This seems like one of those things you should probably do because its' free, but how much time does it save? Is it more than 1 or 2 percent?

[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

[bob]

Doesn't seem to hurt. But doesn't help either.

That's true when it comes down to LMR. For null move i would say that there is a noticeable difference.I mean "if(!pvnode)" for null move definitely hurts. I'm talking about my own tests of course. May be someone would disagree.

Same for me. _any_ restriction on where Null-move is tried, with the exception of the transposition table trick, hurts performance in my cluster testing.

What is the transposition table trick?

I am now NOT reducing any move after a null move. This is mostly due to superstition. In testing it comes out 1 or 2 ELO stronger but with a margin of error much greater (about 5) so it's not clear whether it's any kind of benefit or not.

This was first mentioned by someone I do not remember. The idea is this...

When you do a hash probe, often the draft is not sufficient and you can use the best move, but not the score/bound. But if you take the current depth, and subtract the usual null-move depth from it, you check the draft against this limit, which is what you will do in a null-move search anyway. If the draft is now sufficient, but the probe result says the score or bound will _not_ fail high here, then we just proved that a null-move search would not fail high here either. I return a flag "avoid_null = 1" to Search() which then refuses to try the null-move since we know it will be wasted.

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

Thanks for the explanation Bob. This seems like one of those things you should probably do because its' free, but how much time does it save? Is it more than 1 or 2 percent?

I really never measured this, although I suppose I could run a test on the cluster with and without to see if there is significant difference. I'll start that running right now for giggles to see. It is one of those things that is obviously correct, and it does happen in the search in real games, and the cost is essentially zero. But as to the actual improvement, I will post the answer to this tonight.

[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. 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.