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
TT avoid nullmove flag
Moderators: hgm, Rebel, chrisw
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
TT avoid nullmove flag
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: TT avoid nullmove flag
In Crafty 23.4, function HashProbe() in "hash.c" contains the following comment which might explain what you are looking for:
The implementation is:
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
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. *
Code: Select all
if ((type & UPPER) && depth - null_depth - 1 <= draft && val < beta)
avoid_null = AVOID_NULL_MOVE;
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
-
- Posts: 686
- Joined: Thu Mar 03, 2011 4:57 pm
- Location: Germany
Re: TT avoid nullmove flag
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...
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...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: TT avoid nullmove flag
Simple explanation.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
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..."
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: TT avoid nullmove flag
Thank you all for your explanations, I understand now.
Matthew:out
Matthew:out
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 138
- Joined: Tue Aug 23, 2011 10:25 pm
- Location: Germany
Re: TT avoid nullmove flag
Thanks, good explanation. Really does sound simple. I'm going to try it out in Octochess.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..."
nanos gigantium humeris insidentes
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: TT avoid nullmove flag
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.
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: TT avoid nullmove flag
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?bob wrote:Simple explanation.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
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..."
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
-
- Posts: 9
- Joined: Mon Jul 09, 2012 2:54 pm
Re: TT avoid nullmove flag
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.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?
-
- Posts: 27809
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: TT avoid nullmove flag
1) It takes an extra hash probeDon 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?
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.