Hashed PVs

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.
xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Hashed PVs

Post by xmas79 » Mon Aug 19, 2013 8:30 am

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.

User avatar
lucasart
Posts: 3040
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Hashed PVs

Post by lucasart » Mon Aug 19, 2013 12:17 pm

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.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Hashed PVs

Post by xmas79 » Mon Aug 19, 2013 12:49 pm

Hi Lucas,
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
I already discovered by myself a long time ago...
lucasart wrote:What you should do it backup the PV through the search:
http://web.archive.org/web/200404270138 ... ing/pv.htm
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: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.
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...

Thanks,
Natale.

User avatar
lucasart
Posts: 3040
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Hashed PVs

Post by lucasart » Mon Aug 19, 2013 1:09 pm

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.

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Hashed PVs

Post by xmas79 » Mon Aug 19, 2013 1:38 pm

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".

xmas79
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Hashed PVs

Post by xmas79 » Mon Aug 19, 2013 3:57 pm

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.

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

Re: Hashed PVs

Post by bob » Mon Aug 19, 2013 6:34 pm

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.
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.

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.

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

Re: Hashed PVs

Post by bob » Mon Aug 19, 2013 6:35 pm

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.
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
Posts: 286
Joined: Mon Jun 03, 2013 5:05 pm
Location: Italy

Re: Hashed PVs

Post by xmas79 » Mon Aug 19, 2013 8:30 pm

bob wrote:
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.
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).
Yes I mean "done only when alpha < value < beta". In summary, I follow the same principle of PV backups:
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;

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

Re: Hashed PVs

Post by bob » Mon Aug 19, 2013 10:54 pm

xmas79 wrote:
bob wrote:
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.
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).
Yes I mean "done only when alpha < value < beta". In summary, I follow the same principle of PV backups:
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;
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...

Post Reply