I _do_ replace them with bounds with deeper drafts. It performs better.Gian-Carlo Pascutto wrote: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.bob wrote: 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?
For a new search they are evicted due to aging.
Extracting PV from TT
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Extracting PV from TT
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: Extracting PV from TT
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.bob wrote: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.
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.
-
- Posts: 201
- Joined: Thu Mar 22, 2007 7:12 pm
- Location: Netherlands
Re: Extracting PV from TT
Let's try to make a guestimate of the probability that a PV node is overwritten during a search:Zach Wegner wrote: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.
- 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?
-
- Posts: 147
- Joined: Wed Jun 06, 2007 10:01 am
- Location: United States
- Full name: Mike Leany
Re: Extracting PV from TT
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.Gian-Carlo Pascutto wrote: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.michiguel wrote:Getting things accomplished from a side effects of other algorithms is not the best design, IMHO.
Having to work around a buggy hashtable that's not able to remember it by storing it twice...now that is IMHO bad design
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Extracting PV from TT
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.Zach Wegner wrote:That doesn't seem right to me. Has anyone tested it using the n-entry bucket system and PVS?bob wrote: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.
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...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.
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 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.
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Extracting PV from TT
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.Gian-Carlo Pascutto wrote: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.michiguel wrote:Getting things accomplished from a side effects of other algorithms is not the best design, IMHO.
I do not know what you mean by storing it twice. Also, I think that you definition of bug is not very orthodox.
Having to work around a buggy hashtable that's not able to remember it by storing it twice...now that is IMHO bad design
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
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Extracting PV from TT
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.Jan Brouwer wrote:Let's try to make a guestimate of the probability that a PV node is overwritten during a search:Zach Wegner wrote: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.
- 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?
Not sure what "d" is above (1/(d^5))
-
- Posts: 12549
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Extracting PV from TT
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}.bob wrote: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.Jan Brouwer wrote:Let's try to make a guestimate of the probability that a PV node is overwritten during a search:Zach Wegner wrote: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.
- 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?
Not sure what "d" is above (1/(d^5))
If you do not protect the exact nodes, it seems to me that pv corruption would be almost certain.
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Extracting PV from TT
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.Dann Corbit wrote: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}.bob wrote: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.Jan Brouwer wrote:Let's try to make a guestimate of the probability that a PV node is overwritten during a search:Zach Wegner wrote: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.
- 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?
Not sure what "d" is above (1/(d^5))
If you do not protect the exact nodes, it seems to me that pv corruption would be almost certain.
Miguel
-
- Posts: 12549
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Extracting PV from TT
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:michiguel wrote: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.Dann Corbit wrote: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}.bob wrote: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.Jan Brouwer wrote:Let's try to make a guestimate of the probability that a PV node is overwritten during a search:Zach Wegner wrote: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.
- 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?
Not sure what "d" is above (1/(d^5))
If you do not protect the exact nodes, it seems to me that pv corruption would be almost certain.
Miguel
95% or so exact nodes in your transposition table! Most of which are completely useless.