Hi all,
I was fixing my problems with truncated PV by implementing hashing of PVs in a separate table. It seems I already got it (semi)right (as now I get complete PVs where I couldn't before), but I still get a lot of truncated PVs...
What I do is: every time I backup PVs (on every alpha improvement, draw detection, mate detection) I store this PV into a separate hashtable, and everytime I do a hash hit with an exact score I retrieve it from that hashtable and backup it. I do it in search and in qsearch.
For semplicity I implemented this in the same way of main TT, multislot for each hash key index, hash index based on zobrist key etc... I initially thought that 1024 slots should be enough, but I'm really wrong on this as I found that this bad behaviour depends on the size of this second hashtable. ... Something wrong with my idea of hashed PVs? Something easier/better?
Regards,
Natale.
Hashed PVs
Moderators: hgm, Rebel, chrisw
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Hashed PVs
Walking through the TT to collect the PV is a simplistic and flawed method. There is no way to make it correct and reliable:
https://groups.google.com/forum/?fromgr ... vVCY5A8PIw
What you should do it backup the PV through the search:
http://web.archive.org/web/200404270138 ... ing/pv.htm
And if you disable TT pruning at PV nodes (ELO impact is so small it's not even measurable), your PVs are never truncated: problem solved.
PS: your problem is not just that PVs are truncated. PVs are *very often* wrong with the TT method.
https://groups.google.com/forum/?fromgr ... vVCY5A8PIw
What you should do it backup the PV through the search:
http://web.archive.org/web/200404270138 ... ing/pv.htm
And if you disable TT pruning at PV nodes (ELO impact is so small it's not even measurable), your PVs are never truncated: problem solved.
PS: your problem is not just that PVs are truncated. PVs are *very often* wrong with the TT method.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Hashed PVs
Hi Lucas,
Thanks,
Natale.
I already discovered by myself a long time ago...lucasart wrote:Walking through the TT to collect the PV is a simplistic and flawed method. There is no way to make it correct and reliable:
https://groups.google.com/forum/?fromgr ... vVCY5A8PIw
This is how I'm already doing the basic PV backup stuff. I'm trying to store PVs in another hash table, different from the main TT, not blowed up by search stuff. AFAICT, it seems this new table gets filled anyway. Now I'm investigating.lucasart wrote:What you should do it backup the PV through the search:
http://web.archive.org/web/200404270138 ... ing/pv.htm
I just disabled TT pruning at PV nodes, it seems PVs are all screwed up. If I enable they at least are correct, short, but correct...lucasart wrote:And if you disable TT pruning at PV nodes (ELO impact is so small it's not even measurable), your PVs are never truncated: problem solved.
PS: your problem is not just that PVs are truncated. PVs are *very often* wrong with the TT method.
Thanks,
Natale.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Hashed PVs
I don't understand the point of using a PV hash table. You still have overwriting and grafting going on in this hash table.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Hashed PVs
Not so sure about grafting. This should be an "per iteration" hash table, and overwriting should not be a problem since PV nodes are certainly less than ALL/CUT nodes.... The point of this is: "I'm already able to collect PVs from search, the only problem is during EXACT_SCORE TT match. Let's save PV into another place so we can retrieve it later if we land in a node with an EXACT_SCORE TT hit".
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Hashed PVs
I found the problem. I was polluting the table by filling it on every node termination. This is bad. PV hash must be done only when alpha is improved. Now it works better, but I still get some truncated PVs.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashed PVs
Answer: You do very FEW actual score backups. You don't store into the PV hash unless alpha < value < beta. No point in storing fail-highs since there is no PV anyway.lucasart wrote:I don't understand the point of using a PV hash table. You still have overwriting and grafting going on in this hash table.
If you do this correctly, you (a) get full PVs at least 99% of the time (and more if you are willing to use a large PV hash to eliminate overwrites); (b) you don't cripple the program with the nonsensical ideas such as don't allow EXACT hits on PV path and such. Why ignore perfectly good information that will make the search more efficient?
I've been doing the PV hash for a few years in Crafty and it works perfectly.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashed PVs
I hope you mean "done only when alpha < value < beta". You don't want to do this on a fail high, which does improve alpha (brings it up to beta).xmas79 wrote:I found the problem. I was polluting the table by filling it on every node termination. This is bad. PV hash must be done only when alpha is improved. Now it works better, but I still get some truncated PVs.
-
- Posts: 286
- Joined: Mon Jun 03, 2013 7:05 pm
- Location: Italy
Re: Hashed PVs
Yes I mean "done only when alpha < value < beta". In summary, I follow the same principle of PV backups:bob wrote:I hope you mean "done only when alpha < value < beta". You don't want to do this on a fail high, which does improve alpha (brings it up to beta).xmas79 wrote:I found the problem. I was polluting the table by filling it on every node termination. This is bad. PV hash must be done only when alpha is improved. Now it works better, but I still get some truncated PVs.
1) when "alpha<value<beta" ---> store PV and backup
2) when an exact TT hit occurs probe hashtable for PV hit:
2a) if PV hit ---> retrieve and then backup
2b) if not PV hit ---> Truncate PV by setting pv->length = 0;
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashed PVs
That is pretty much what I described when I started doing this a few years back. My default size is 65536 entries, and I don't see very many <HT> truncated PVs displayed...xmas79 wrote:Yes I mean "done only when alpha < value < beta". In summary, I follow the same principle of PV backups:bob wrote:I hope you mean "done only when alpha < value < beta". You don't want to do this on a fail high, which does improve alpha (brings it up to beta).xmas79 wrote:I found the problem. I was polluting the table by filling it on every node termination. This is bad. PV hash must be done only when alpha is improved. Now it works better, but I still get some truncated PVs.
1) when "alpha<value<beta" ---> store PV and backup
2) when an exact TT hit occurs probe hashtable for PV hit:
2a) if PV hit ---> retrieve and then backup
2b) if not PV hit ---> Truncate PV by setting pv->length = 0;