Transposition table pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Transposition table pruning
Why isn't the transposition table used for pruning at PV nodes (at least in Stockfish)?
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Transposition table pruning
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.
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Transposition table pruning
Thanks.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.
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: Transposition table pruning
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.
* 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
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Transposition table pruning
This is very well written. We could add this as a comment in the code.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.
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Transposition table pruning
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?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.
Miguel
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Transposition table pruning
I don't understand the last point. Why would TT mate-scores in the PV need different handling than in non-PV nodes?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Transposition table pruning
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...mcostalba wrote:This is very well written. We could add this as a comment in the code.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.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Transposition table pruning
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.michiguel wrote: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?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.
Miguel
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Transposition table pruning
I think you missed the word "specific" in my question. What you say is right but not specific for the PV.bob wrote: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.michiguel wrote: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?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.
Miguel
Miguel