Transposition table pruning

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.
metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Transposition table pruning

Post by metax » Wed Nov 25, 2009 12:44 pm

Why isn't the transposition table used for pruning at PV nodes (at least in Stockfish)?

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

Re: Transposition table pruning

Post by hgm » Wed Nov 25, 2009 1:00 pm

Pruning the PV would print short PVs if you use the triangular-array method, and not pruning might help you to recognize rep-draws that were not accounted for in the hash.

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Transposition table pruning

Post by metax » Wed Nov 25, 2009 1:14 pm

hgm wrote:Pruning the PV would print short PVs if you use the triangular-array method, and not pruning might help you to recognize rep-draws that were not accounted for in the hash.
Thanks.

zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Transposition table pruning

Post by zamar » Wed Nov 25, 2009 3:21 pm

Values from TT are not used in PV, because:

* Extra cost is small (TT values can be used for non-PV child nodes).
* rep. draws are problemtic (as hmg pointed out)
* fifty move rule detection is problematic
* delivering mate is problematic when TT shows matescores everywhere and would need special handling.
Joona Kiiski

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Transposition table pruning

Post by mcostalba » Wed Nov 25, 2009 4:10 pm

zamar wrote:Values from TT are not used in PV, because:

* Extra cost is small (TT values can be used for non-PV child nodes).
* rep. draws are problemtic (as hmg pointed out)
* fifty move rule detection is problematic
* delivering mate is problematic when TT shows matescores everywhere and would need special handling.
This is very well written. We could add this as a comment in the code.

User avatar
michiguel
Posts: 6388
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Transposition table pruning

Post by michiguel » Wed Nov 25, 2009 4:25 pm

zamar wrote:Values from TT are not used in PV, because:

* Extra cost is small (TT values can be used for non-PV child nodes).
* rep. draws are problemtic (as hmg pointed out)
* fifty move rule detection is problematic
* delivering mate is problematic when TT shows matescores everywhere and would need special handling.
I do not use TT in PV because I like to have a full PV. But, I never had any of the other problems. Why would you have specific problems with mates scores and draws?

Miguel

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

Re: Transposition table pruning

Post by hgm » Wed Nov 25, 2009 4:27 pm

I don't understand the last point. Why would TT mate-scores in the PV need different handling than in non-PV nodes?

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table pruning

Post by bob » Wed Nov 25, 2009 6:50 pm

mcostalba wrote:
zamar wrote:Values from TT are not used in PV, because:

* Extra cost is small (TT values can be used for non-PV child nodes).
* rep. draws are problemtic (as hmg pointed out)
* fifty move rule detection is problematic
* delivering mate is problematic when TT shows matescores everywhere and would need special handling.
This is very well written. We could add this as a comment in the code.
And a good bit of that is dead wrong as well. Rep draws are problematic _everywhere_, not just along the PV branches. Ignoring the problem in part of the tree is an invitation for really subtle bugs. Ditto for 50 move draw issues. Why would you avoid hash cutoffs on the PV but not elsewhere? You fail high on a second move, and don't have time to re-search it as a PV branch due to time limits, and you make a decision based on hash cutoffs. This idea makes no sense to me whatsoever, and sounds just like the other ideas such as (1) don't store draw scores in the hash table; (2) don't store mate scores in the hash table; (3) Don't store mate bounds in the hash table. Etc...

Mate scores are not problematic in the least. I've stored mate scores/bounds since around 1976 or so when I added hash tables to blitz. And I have never done differently in any succeeding version. And I have experienced absolutely no problems in doing this.

Taking the points one at a time, as numbered above.

(1) is simply wrong. Any time you can take a quick cutoff, you avoid a significant amount of effort. A hash cutoff is faster than even searching a single node. No idea where this comment comes from but it is incorrect.

(2) & (3) rep draws and 50-move draws are problematic, to be sure. But this is not a "fix" for the problem at all.

(4) the only mate score special handling you need is to store mate-in-n from the current node, not mate-in-N from the root. This is trivial to implement and works perfectly.

I hope that most would try this stuff for themselves. I see no reason to not take advantage of a time-saver just because it might add an extra line or two of code, or require some time to consider all possible effects.

bob
Posts: 20549
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table pruning

Post by bob » Wed Nov 25, 2009 6:52 pm

michiguel wrote:
zamar wrote:Values from TT are not used in PV, because:

* Extra cost is small (TT values can be used for non-PV child nodes).
* rep. draws are problemtic (as hmg pointed out)
* fifty move rule detection is problematic
* delivering mate is problematic when TT shows matescores everywhere and would need special handling.
I do not use TT in PV because I like to have a full PV. But, I never had any of the other problems. Why would you have specific problems with mates scores and draws?

Miguel
The TT can hide a draw because it doesn't store path information. But this is true of the 50-move rule as well. I certainly do not any justification for not allowing cutoffs from hash along the PV. It is just a hack fix that actually loses significant information. This is critical for finding fine 70 early, as an example.

User avatar
michiguel
Posts: 6388
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: Transposition table pruning

Post by michiguel » Wed Nov 25, 2009 7:04 pm

bob wrote:
michiguel wrote:
zamar wrote:Values from TT are not used in PV, because:

* Extra cost is small (TT values can be used for non-PV child nodes).
* rep. draws are problemtic (as hmg pointed out)
* fifty move rule detection is problematic
* delivering mate is problematic when TT shows matescores everywhere and would need special handling.
I do not use TT in PV because I like to have a full PV. But, I never had any of the other problems. Why would you have specific problems with mates scores and draws?

Miguel
The TT can hide a draw because it doesn't store path information. But this is true of the 50-move rule as well. I certainly do not any justification for not allowing cutoffs from hash along the PV. It is just a hack fix that actually loses significant information. This is critical for finding fine 70 early, as an example.
I think you missed the word "specific" in my question. What you say is right but not specific for the PV.

Miguel

Post Reply