Extracting PV from TT

[bob]

How do you know an entry is a PV entry? And if you flag each one, how do you go back and remove the flag as the PV changes while searching the first move, or even as you search other root moves?

Entries with exact scores are PV entries. The amount of them in a complete search is so minuscule that you shouldn't have to evict them from your hashtable. Obviously you don't replace them by bound entries with deeper drafts.

For a new search they are evicted due to aging.

I _do_ replace them with bounds with deeper drafts. It performs better.

[Zach Wegner]

IMHO the best design is the one that works best. If you refuse to overwrite an EXACT entry, performance goes down. It's been measured by several different people using different programs, over the years.

That doesn't seem right to me. Has anyone tested it using the n-entry bucket system and PVS? Have any of the tests even been run in the last 15 years? Given that the number of PV nodes in a search numbers in the thousands, the only possible negative consequences of keeping the EXACT entries around are going to be basically equivalent to having a hash table with a few thousand less entries. And the replacement algorithm doesn't have to throw away entries that would overwrite an exact entry: with the bucket system you would just replace the lowest-draft entry that isn't an exact score.

I would also dispute your assertion that draft is the only way to determine how useful a hash entry is. It seems obvious that an entry with an exact score is much more useful than just a bound, both because it can be used to terminate the search regardless of alpha and beta, and because it represents much more work being done (an open window search versus a null window).

I agree with GCP that a working hash table should be able to reproduce a PV entirely virtually all the time. Manually keeping track of the PV would be useful for debugging purposes though.

[Jan Brouwer]

I agree with GCP that a working hash table should be able to reproduce a PV entirely virtually all the time. Manually keeping track of the PV would be useful for debugging purposes though.

Let's try to make a guestimate of the probability that a PV node is overwritten during a search:
- hash table with n entries and 4-way associativity
- one in p nodes during the search is a pv-node
- the search more or less completely fills the hash table

The probability that a single entry contains a pv node is about 1/p.
The probability that a pv node is stored while all 4 entries where it can be stored already contain a pv node is about 1/(d^5)
The probability that this happens anywhere the hash table is roughly n/(d^5)

For e.g. n = 10^7 and p is 10^3 this comes down to 10^-9, which is quite small

Is this about right?

[xsadar]

Getting things accomplished from a side effects of other algorithms is not the best design, IMHO.

Well this really the crux of the matter I guess. The PV is the single most important variation for the move ordering of the entire search. The hash table is the single most important tool for storing move ordering information. I find that being able to retrieve the most important move ordering information from the table that's supposed to store it is not a side effect, but the design requirement.

Having to work around a buggy hashtable that's not able to remember it by storing it twice...now that is IMHO bad design

Sure the PV is the single most important variation, but the transposition table was not designed to store entire variations. It was designed to store scores and bestmoves of individual positions that the search may encounter in the near future. And being able to retrieve an entire variation (including the PV) has nothing to do with move ordering, UNLESS we're about to search a position near the root of that variation. Of course at the beginning of a search it is useful to have the entire PV in the hash table, because that's the variation we want to search first, but after that, it's not as relevant. And it's trivial (both in CPU time and programming time) to feed the PV back into the TT immediately preceding a new search.

Also, saying that a design is buggy simply because it doesn't have the same set of advantages and disadvantages that you prefer is ridiculous. I could just as easily say that your design is buggy because it throws away data more relevant to the remaining search in favor of keeping PV data, which may be less relevant to the remaining search.

[bob]

IMHO the best design is the one that works best. If you refuse to overwrite an EXACT entry, performance goes down. It's been measured by several different people using different programs, over the years.

That doesn't seem right to me. Has anyone tested it using the n-entry bucket system and PVS?

First, yes to multiple entries/bucket. Cray Blitz used 8. Current Crafty uses 4. I will try a cluster test to see how things measure up on a large number of games.

Have any of the tests even been run in the last 15 years? Given that the number of PV nodes in a search numbers in the thousands, the only possible negative consequences of keeping the EXACT entries around are going to be basically equivalent to having a hash table with a few thousand less entries. And the replacement algorithm doesn't have to throw away entries that would overwrite an exact entry: with the bucket system you would just replace the lowest-draft entry that isn't an exact score.

Last time I actually counted PV nodes, there were far more than "a few thousand". That left-most branch from the root is not perfectly ordered. Just compare the PV from depth N to depth N+1. Often the best move won't change, but the PV will change significantly...

I would also dispute your assertion that draft is the only way to determine how useful a hash entry is. It seems obvious that an entry with an exact score is much more useful than just a bound, both because it can be used to terminate the search regardless of alpha and beta, and because it represents much more work being done (an open window search versus a null window).

Change that to "an EXACT represents much more work being done than a non-EXACT entry AT THE SAME DEPTH." But we are not talking about the same depth. We are talking about an EXACT entry that is near the end of the PV with small draft, vs a LOWER/UPPER entry that is farther away from tip positions with a greater draft.

I agree with GCP that a working hash table should be able to reproduce a PV entirely virtually all the time. Manually keeping track of the PV would be useful for debugging purposes though.

[michiguel]

Getting things accomplished from a side effects of other algorithms is not the best design, IMHO.

Well this really the crux of the matter I guess. The PV is the single most important variation for the move ordering of the entire search. The hash table is the single most important tool for storing move ordering information. I find that being able to retrieve the most important move ordering information from the table that's supposed to store it is not a side effect, but the design requirement.

No, that is the requirement you are imposing on your hashtable. In fact, the "hash" table is two things in one. A transposition table (which is the title of the thread) and the refutation table combined. The refutation table is the one that will hold info to reproduce the PV. Most programs seems to combine this two but that is not cast in stone. If you set another requirement for this table, the constraints are such that they will limit the ability to change things. As a said, if you decide not to store the last ply of the search, you get a truncated pv. What if you want to have more specialized tables? splitting them in TT and RF? If you get the PV from the tables, you limit them.

Having to work around a buggy hashtable that's not able to remember it by storing it twice...now that is IMHO bad design

I do not know what you mean by storing it twice. Also, I think that you definition of bug is not very orthodox.

Regarding debugging procedures, what if you want to turn off the hashtables to examine the behavior chasing a bug, how do you get a PV? This is what happens when you have routines and data that are strongly coupled with no need for it.

Miguel

[bob]

I agree with GCP that a working hash table should be able to reproduce a PV entirely virtually all the time. Manually keeping track of the PV would be useful for debugging purposes though.

Let's try to make a guestimate of the probability that a PV node is overwritten during a search:
- hash table with n entries and 4-way associativity
- one in p nodes during the search is a pv-node
- the search more or less completely fills the hash table

The probability that a single entry contains a pv node is about 1/p.
The probability that a pv node is stored while all 4 entries where it can be stored already contain a pv node is about 1/(d^5)
The probability that this happens anywhere the hash table is roughly n/(d^5)

For e.g. n = 10^7 and p is 10^3 this comes down to 10^-9, which is quite small

Is this about right?

I regularly search one billion nodes. So maybe _not_ so small. And your above math has a couple of questionable assumptions. Such as uniformly distributed hash signatures, which is not a given.

Not sure what "d" is above (1/(d^5))

[Dann Corbit]

I agree with GCP that a working hash table should be able to reproduce a PV entirely virtually all the time. Manually keeping track of the PV would be useful for debugging purposes though.

Let's try to make a guestimate of the probability that a PV node is overwritten during a search:
- hash table with n entries and 4-way associativity
- one in p nodes during the search is a pv-node
- the search more or less completely fills the hash table

The probability that a single entry contains a pv node is about 1/p.
The probability that a pv node is stored while all 4 entries where it can be stored already contain a pv node is about 1/(d^5)
The probability that this happens anywhere the hash table is roughly n/(d^5)

For e.g. n = 10^7 and p is 10^3 this comes down to 10^-9, which is quite small

Is this about right?

I regularly search one billion nodes. So maybe _not_ so small. And your above math has a couple of questionable assumptions. Such as uniformly distributed hash signatures, which is not a given.

Not sure what "d" is above (1/(d^5))

Consider correspondence chess calculations, where a single position gets at least 24 hours of compute time {and conceivably up to a month}, probably with at least 4 CPUs {and conceivably 64 or more CPUs}.

If you do not protect the exact nodes, it seems to me that pv corruption would be almost certain.

[michiguel]

I agree with GCP that a working hash table should be able to reproduce a PV entirely virtually all the time. Manually keeping track of the PV would be useful for debugging purposes though.

Let's try to make a guestimate of the probability that a PV node is overwritten during a search:
- hash table with n entries and 4-way associativity
- one in p nodes during the search is a pv-node
- the search more or less completely fills the hash table

The probability that a single entry contains a pv node is about 1/p.
The probability that a pv node is stored while all 4 entries where it can be stored already contain a pv node is about 1/(d^5)
The probability that this happens anywhere the hash table is roughly n/(d^5)

For e.g. n = 10^7 and p is 10^3 this comes down to 10^-9, which is quite small

Is this about right?

I regularly search one billion nodes. So maybe _not_ so small. And your above math has a couple of questionable assumptions. Such as uniformly distributed hash signatures, which is not a given.

Not sure what "d" is above (1/(d^5))

Consider correspondence chess calculations, where a single position gets at least 24 hours of compute time {and conceivably up to a month}, probably with at least 4 CPUs {and conceivably 64 or more CPUs}.

If you do not protect the exact nodes, it seems to me that pv corruption would be almost certain.

Not to mention that if you are a correspondence player and you do not get a full PV after spending such a long time, you are not going to be too happy.

Miguel

[Dann Corbit]

I agree with GCP that a working hash table should be able to reproduce a PV entirely virtually all the time. Manually keeping track of the PV would be useful for debugging purposes though.

Let's try to make a guestimate of the probability that a PV node is overwritten during a search:
- hash table with n entries and 4-way associativity
- one in p nodes during the search is a pv-node
- the search more or less completely fills the hash table

The probability that a single entry contains a pv node is about 1/p.
The probability that a pv node is stored while all 4 entries where it can be stored already contain a pv node is about 1/(d^5)
The probability that this happens anywhere the hash table is roughly n/(d^5)

For e.g. n = 10^7 and p is 10^3 this comes down to 10^-9, which is quite small

Is this about right?

I regularly search one billion nodes. So maybe _not_ so small. And your above math has a couple of questionable assumptions. Such as uniformly distributed hash signatures, which is not a given.

Not sure what "d" is above (1/(d^5))

Consider correspondence chess calculations, where a single position gets at least 24 hours of compute time {and conceivably up to a month}, probably with at least 4 CPUs {and conceivably 64 or more CPUs}.

If you do not protect the exact nodes, it seems to me that pv corruption would be almost certain.

Not to mention that if you are a correspondence player and you do not get a full PV after spending such a long time, you are not going to be too happy.

Miguel

I guess that if you do protect the exact nodes you will see something very funny after 1000 core hours of compute time with an 8 GB hash:
95% or so exact nodes in your transposition table! Most of which are completely useless.