Hashed PVs

[xmas79]

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.

[lucasart]

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.

[xmas79]

Hi Lucas,

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

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.

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.

[lucasart]

I don't understand the point of using a PV hash table. You still have overwriting and grafting going on in this hash table.

[xmas79]

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]

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]

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]

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]

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]

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