TT avoid nullmove flag

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

TT avoid nullmove flag

Post by ZirconiumX » Thu Aug 02, 2012 5:37 pm

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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: TT avoid nullmove flag

Post by Sven » Thu Aug 02, 2012 8:46 pm

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
Posts: 686
Joined: Thu Mar 03, 2011 3:57 pm
Location: Germany
Contact:

Re: TT avoid nullmove flag

Post by tpetzke » Thu Aug 02, 2012 8:49 pm

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
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: TT avoid nullmove flag

Post by bob » Fri Aug 03, 2012 3:23 am

ZirconiumX wrote: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
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: TT avoid nullmove flag

Post by ZirconiumX » Fri Aug 03, 2012 9:00 am

Thank you all for your explanations, I understand now.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

User avatar
Codesquid
Posts: 138
Joined: Tue Aug 23, 2011 8:25 pm
Location: Germany
Contact:

Re: TT avoid nullmove flag

Post by Codesquid » Fri Aug 03, 2012 5:06 pm

bob wrote: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.
nanos gigantium humeris insidentes

Mincho Georgiev
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: TT avoid nullmove flag

Post by Mincho Georgiev » Sat Aug 04, 2012 6:37 am

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.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: TT avoid nullmove flag

Post by Don » Wed Aug 08, 2012 2:46 pm

bob wrote:
ZirconiumX wrote: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?
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

plattyaj
Posts: 9
Joined: Mon Jul 09, 2012 12:54 pm

Re: TT avoid nullmove flag

Post by plattyaj » Wed Aug 08, 2012 4:03 pm

Don wrote: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.

User avatar
hgm
Posts: 23631
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: TT avoid nullmove flag

Post by hgm » Wed Aug 08, 2012 5:07 pm

Don wrote: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.

Post Reply