TT avoid nullmove flag

[diep]

I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.

I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.

Could someone tell me how this is supposed to work?

Something in the back of my head says to check if the TT score fails low.

Matthew:out

Simple explanation.

First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.

When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."

How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?

You aren't missing anything. It's safer to allow nullmove and sit and wait for that hashtable cutoff, as an upperbound node stored for this position is pretty meaningless.

No, it is really different. The short explanation has already been given: the side to move is different.

The TT trick avoids nullmove if the current position is in the hashtable, but not with enough depth for a cutoff, but with enough depth to compare against a (reduced) nullmove search (and if the stored score indicates that nullmove would/should be useless).

If you don't use this trick but just do the nullmove, the position does not stay the same because the side to move switches. If you now look in the hashtable, you are looking at a different positon, so you are not going to find the score that helped you if you had done the TT trick. So it is really different.

I would add that if the parent position was not in the hashtable with sufficient depth for a cutoff, it seems likely that the position after the nullmove won't be in the hashtable with sufficient reduced depth. If you are now at depth d for the parent position, but its TT entry has depth d-1, then doing a nullmove and probing the hashtable would more likely find an entry with depth (d-1) - R -1 than one with depth d - R -1, simply because the reason it is in the hashtable at all is that it was searched when a nullmove was tried for the parent positon at depth d-1.

I don't know if the TT trick helps elowise compared to not doing the trick, but it certainly makes a difference.

Since you're saying "it is safer to allow nullmove" we might in fact already mostly agree on this. My point is only that it is not the same as Don suggested.

Basically i read Don's comment as: "if all i save out for a big risk just 1 call to hashtable, why do it, as it has the same EFFECT?"

I said 'ack' to that.

Doing the nullmove is always better of course. And i don't say that from theoretical viewpoint only - believe me when i say i really tested this BIGTIME. I don't see how this trick can work for others.
Maybe bad testing or just super-bullet testing.

For sure doing this trick loses elo if any - it sure doesn't win elo.

It's a programming trick that simply doesn't work.

[syzygy]

Basically i read Don's comment as: "if all i save out for a big risk just 1 call to hashtable, why do it, as it has the same EFFECT?"

I said 'ack' to that.

If it has exactly the same effect, it may not be worth the trouble, but then there is also no big risk.

I think the effect is certainly not the same. It might be the case that elowise it is bad, even though intuitively it seems to be a good idea.

Doing the nullmove is always better of course. And i don't say that from theoretical viewpoint only - believe me when i say i really tested this BIGTIME. I don't see how this trick can work for others.

Yes, if testing shows it is bad, then there is not much more that can be said. But from a theoretical viewpoint it makes sense not to try a nullmove if we know that the side to move has a real move, which (normally) should be at least as good as a nullmove. If you know that your nullmove is going to be futile, you can skip it.

What I find interesting is that this TT trick in a way seems to be a variation on double null move. Didn't you use that?

[bob]

I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.

I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.

Could someone tell me how this is supposed to work?

Something in the back of my head says to check if the TT score fails low.

Matthew:out

Simple explanation.

First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.

When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."

How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?

You aren't missing anything. It's safer to allow nullmove and sit and wait for that hashtable cutoff, as an upperbound node stored for this position is pretty meaningless.

No, it is really different. The short explanation has already been given: the side to move is different.

The TT trick avoids nullmove if the current position is in the hashtable, but not with enough depth for a cutoff, but with enough depth to compare against a (reduced) nullmove search (and if the stored score indicates that nullmove would/should be useless).

If you don't use this trick but just do the nullmove, the position does not stay the same because the side to move switches. If you now look in the hashtable, you are looking at a different positon, so you are not going to find the score that helped you if you had done the TT trick. So it is really different.

I would add that if the parent position was not in the hashtable with sufficient depth for a cutoff, it seems likely that the position after the nullmove won't be in the hashtable with sufficient reduced depth. If you are now at depth d for the parent position, but its TT entry has depth d-1, then doing a nullmove and probing the hashtable would more likely find an entry with depth (d-1) - R -1 than one with depth d - R -1, simply because the reason it is in the hashtable at all is that it was searched when a nullmove was tried for the parent positon at depth d-1.

I don't know if the TT trick helps elowise compared to not doing the trick, but it certainly makes a difference.

Since you're saying "it is safer to allow nullmove" we might in fact already mostly agree on this. My point is only that it is not the same as Don suggested.

I only assume EVERYONE takes care of WTM in the hash signature match. If not, they will be totally unable to solve positions like fine 70 which is all about zugzwang.

Some notes:

(1) if you just play the null and hope for a hash hit, you won't get one if you did the side-to-move hash signature update correctly, so you will do some nulls where you might not get any benefit from them.

(2) by the same token, the depth is often more than needed which means you are using information the null-move search would not have. Whether that is more accurate or not is difficult to say.

(3) whether the avoid-null-move trick works or not is not so clear. Logically, it is the right thing to do. But testing on positions produced mixed results. When I can get my cluster stuff updated to run on our new cluster, and then verify that the results are consistent, I am going to test with and without this trick to see if there is any benefit/cost...

[Don]

I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.

I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.

Could someone tell me how this is supposed to work?

Something in the back of my head says to check if the TT score fails low.

Matthew:out

Simple explanation.

First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.

When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."

How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?

The side to move is different.

You seem obsessed with side to move. Of course it's just incorrect if that is not taken into consideration, Komodo knows the different between white to move and black to move positions in the hash table and with respect to null move.

[diep]

Basically i read Don's comment as: "if all i save out for a big risk just 1 call to hashtable, why do it, as it has the same EFFECT?"

I said 'ack' to that.

If it has exactly the same effect, it may not be worth the trouble, but then there is also no big risk.

I think the effect is certainly not the same. It might be the case that elowise it is bad, even though intuitively it seems to be a good idea.

Doing the nullmove is always better of course. And i don't say that from theoretical viewpoint only - believe me when i say i really tested this BIGTIME. I don't see how this trick can work for others.

Yes, if testing shows it is bad, then there is not much more that can be said. But from a theoretical viewpoint it makes sense not to try a nullmove if we know that the side to move has a real move, which (normally) should be at least as good as a nullmove. If you know that your nullmove is going to be futile, you can skip it.

What I find interesting is that this TT trick in a way seems to be a variation on double null move. Didn't you use that?

Not trying a nullmove is a very bad idea simply because it's so cheap to try one. Always nullmoving is always going to prune more nodes than whatever limit to not try to prune (other than being in check, or beta being infinite). That's also true for double nullmove.

Note that double nullmove is far cheaper in overhead as it requires 2 consecutive nullmoves prior to forbidding to prune.

It's not even needed to elowise test this - besides that it's rather impossible to do so. Just take a 200 positions and search for a couple of minutes a position. Of course at a core or 8...

You'll see a significant difference then.

I run such tests fully automated.

When i debugged what was the big difference; it is the 'learning effect' that causes it of a hashtable storing bigger search depths that cutoff a smaller search depth. So a position simply changes signature after nullmove.

From lowerbound to upperbound and upperbound to lowerbound, not seldom caused by crappy form of nullmove last 4 plies.

[syzygy]

How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?

The side to move is different.

You seem obsessed with side to move. Of course it's just incorrect if that is not taken into consideration, Komodo knows the different between white to move and black to move positions in the hash table and with respect to null move.

Huh? He is only telling you the "something" that you were missing.

[syzygy]

Not trying a nullmove is a very bad idea simply because it's so cheap to try one. Always nullmoving is always going to prune more nodes than whatever limit to not try to prune (other than being in check, or beta being infinite). That's also true for double nullmove.

Note that double nullmove is far cheaper in overhead as it requires 2 consecutive nullmoves prior to forbidding to prune.

My point is that if you allow double nullmove, you are effectively already using the TT trick. For this case, Don's reasoning does apply (with a twist).

Let's look at this in detail.
A) using the TT trick.
- we search a node at depth d.
- TT gives an upperbound v < beta for depth d' with d - R - 1 <= d' < d. We can't use this for an alpha cut off.
- However, we can use this to predict that doing a nullmove and a reduced search will return a score < beta, i.e. to predict that nullmove will not fail high. Therefore we skip the nullmove because it is predicted to be useless, and search the real moves.

B) not using the TT trick, but using double nullmove.
- we search a node at depth d.
- TT gives an upperbound v < beta for depth d'. We can't use this for an alpha cut off.
- We do a first nullmove. Side to move switches. We search at depth d - R - 1.
- We probe the TT. Let's assume no hit.
- We do a second nullmove. Side to move switches back. We search at depth d - 2R - 2.
- We probe the TT. TT gives an upperbound v < beta for depth d' with d' >= d - R - 1, so certainly d' >= d - 2R -2.
- We have an alpha cutoff. So we immediately return.
- The 2nd nullmove search failed high. This means this 2nd nullmove "succeeded", since we use this to predict that some real move will fail high as well. So we immediately return a fail low.
- We are back at the node where we started. Null move failed low (without actually searching anything!), so we search the real moves.

So both techniques effectively avoid the nullmove search. Technique B) takes more operations, but is of course more general. Technique B) avoids more nullmove searches.

Whether A and B gain or lose elo, I cannot say. But if A) is bad, then B) would seem to be worse.

[diep]

cut the crap ronald.

If you have an algorithm to detect zugzwang that is doing:

We start with position P depthleft D.

if( !move[-1] && ![move-2] )

knowing that each one of them is using reduction factor R.

Then this position P'' relative to P has had a reduction of at least 2R+2 ply or so (most in fact increase R).

So the statistical odds for having a 'ban' for nullmove based upon double nullmove is really small. Note this gets used to detect a ZUGZWANG.

And yes it does require more nodes - obviously.

This where just forbidding nullmove based upon having an entry that is upperbound of this position, that's like 5-7% of the positions or so

So not only is it a total crap compare from your viewpoint. Also it's statistical not even in the same league of total number of positions. You speak about a hard forbidding of nullmove in 5-7% of the cases based upon 1 total unreliable upperbound result stored in your hashtable, versus an algorithm that gets used in 0.0x% of the positions that does eat more nodes yet it's there to detect a zugzwang.

In fact detecting zugzwangs some find so important nowadays, that after nullmove they still do a verification search - obviously eating more nodes than double nullmove, yet of course also catching that zugzwang very well.

So my invention was pretty to the point... ...and your rambling here doesn't make any sense at all.

[syzygy]

and your rambling here doesn't make any sense at all.

If you don't mind, I'll leave that to others who do take the trouble to actually read what I wrote.

I have explained why double null move effectively encompasses the TT move trick.

Hmm, I wrote "search at depth d" which is confusing. What I meant is search with depth d left.

[syzygy]

if( !move[-1] && ![move-2] )

knowing that each one of them is using reduction factor R.

Then this position P'' relative to P has had a reduction of at least 2R+2 ply or so (most in fact increase R).

So the statistical odds for having a 'ban' for nullmove based upon double nullmove is really small. Note this gets used to detect a ZUGZWANG.

I'm not talking about banning the 3rd nullmove. I am talking about the 2nd nullmove search failing high, causing the 1st nullmove search to immediately fail low. This 2nd nullmove search in that case has the effect of "avoiding" the 1st nullmove search. If the fail high of the 2nd nullmove search is caused by probing the TT, we are in the same situation as when the TT trick applies.