TT avoid nullmove flag

[jwes]

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.

[G.B. Harms]

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.

Indeed, otherwise you could set this "avoid null move" flag as well for BETA and EXACT found transpositions with a draft >= draft - R

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

I've run some position tests and I am no longer convinced this is a good idea. We have replaced the primary cluster I used for testing, which means I need to slightly modify my test platform since these nodes have way more CPUS (12 per node now rather than the old 2 per node). But position tests suggest that not using this test is better overall. Only explanation I can guess is that the TT entry often has MORE draft than the NM search would use, and a deeper search would not fail high while a shallower one would. I am going to test it on 30K actual games to see if this is actually true in games as well...

[Mincho Georgiev]

Strangely enough, I'm not convinced anymore either, regardless of my previous post. After reading this topic I got back to my old sources and discovered a bug in the tt entry. After I've fixed it, this "add-on" was no longer working . No I have to test again while is removed, too bad.

[bob]

Strangely enough, I'm not convinced anymore either, regardless of my previous post. After reading this topic I got back to my old sources and discovered a bug in the tt entry. After I've fixed it, this "add-on" was no longer working . No I have to test again while is removed, too bad.

Just goes to show it is always best to test, even if you are sure about the outcome.

[Mincho Georgiev]

Yes, I always do, just the last test optimistic results are now obviously false due to that bug. I hate when a bug produces ELO, it always means more bugs

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

[diep]

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?

1) It takes an extra hash probe
2) You might not get the hash cutoff. If the node you are probing now failed low with less depth than you need, even if it ordered a null-move search and it survived in the hash table (it has a lot lower depth!), it will also not have enough depth to satisfy the null-move search you are ordering now. (Unless you already saturated to QS level.) There is no guarantee that another path reached the position after null move with more remaining depth.

Why not just try what Don posted and measure elo?

the 'avoid null flag' is a pretty dangerous flag to use.

[syzygy]

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.

[syzygy]

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.

But... if you skip the trick but allow two nullmoves in a row, then you would return to the current position and the 2nd nullmove would immediately return and show that the first nullmove is useless.

If I'm not mistaken you (Vincent) are a proponent of double nullmove. In that case I think I have to agree that the TT trick is redundant (although it might save some clock cycli).

Am I correct? I haven't though very long about this so maybe I'm missing something.