TT avoid nullmove flag

[ZirconiumX]

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

[Sven]

In Crafty 23.4, function HashProbe() in "hash.c" contains the following comment which might explain what you are looking for:

Code: Select all

 *   We also return an "avoid_null" status if the matched   *
 *   entry does not have enough draft to terminate the      *
 *   current search but does have enough draft to prove     *
 *   that a null-move search would not fail high.  This     *
 *   avoids the null-move search overhead in positions      *
 *   where it is simply a waste of time to try it.          *

The implementation is:

Code: Select all

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

which matches the explanation above very well.

Since at most nodes a zero window is used, i.e. alpha == beta-1, a value < beta which is also an upper bound implies that the null-move search would fail low.

Sven

[tpetzke]

Hi,

I think it is documented in the crafty source. The idea is that the TT score you retrieve has a depth associated. This depth might not have enough draft to be used but it tells you something for searches you perform with a lower depth from here (like null move and R=2 or 3).

The down side is that if you skip the null move you don't get a threat move and maybe it is useful to have one.

Thomas...

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

[ZirconiumX]

Thank you all for your explanations, I understand now.

Matthew:out

[Codesquid]

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

Thanks, good explanation. Really does sound simple. I'm going to try it out in Octochess.

[Mincho Georgiev]

Just to mention that while ago, we had a discussion around here somewhere. I was able to measure about 5 elo points gain from that flag.

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

[plattyaj]

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?

It saves the cost of making (and unmaking) the null move and the TT probe you would do there. And depending on your implementation you might drop straight into qsearch and from there call the evaluation.

[hgm]

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.