Extracting PV from TT

[bob]

I have so far run 4 sets of 40,000 games. Version 23.1 is the current version that stores in the hash table as follows:

I use 3 passes (if needed) to choose one entry from a bucket of four.

1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.

2. If that fails, I check to see if any entry is old, based on the "age" field. This would mean the entry came from the previous search (not the previous iteration). If there are any "old" entries, I replace one with the shallowest draft.

3. Otherwise, I simply search for the one with the shallowest draft and replace it, no matter what its origin and type.

Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.

so far:

Code: Select all

Crafty-23.1-1        2593    4    4 40000   48%  2610   23% 
Crafty-23.1-2        2591    4    4 40000   47%  2610   22% 
Crafty-23.1a-2       2589    4    4 40000   47%  2610   22% 
Crafty-23.1a-1       2588    3    4 40000   47%  2610   22% 

Not much difference, but the new version which never replaces EXACT entries from the same search unless the replacement is also EXACT seems to be a little worse. I am running each test 2 more times to see if they consistently rank lower than the normal pure depth-preferred replacement.

[bob]

I have so far run 4 sets of 40,000 games. Version 23.1 is the current version that stores in the hash table as follows:

I use 3 passes (if needed) to choose one entry from a bucket of four.

1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.

2. If that fails, I check to see if any entry is old, based on the "age" field. This would mean the entry came from the previous search (not the previous iteration). If there are any "old" entries, I replace one with the shallowest draft.

3. Otherwise, I simply search for the one with the shallowest draft and replace it, no matter what its origin and type.

Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.

so far:

Code: Select all

Crafty-23.1-1        2593    4    4 40000   48%  2610   23% 
Crafty-23.1-2        2591    4    4 40000   47%  2610   22% 
Crafty-23.1a-2       2589    4    4 40000   47%  2610   22% 
Crafty-23.1a-1       2588    3    4 40000   47%  2610   22% 

Not much difference, but the new version which never replaces EXACT entries from the same search unless the replacement is also EXACT seems to be a little worse. I am running each test 2 more times to see if they consistently rank lower than the normal pure depth-preferred replacement. Note that the error bar causes them to overlap so this difference is not very significant.

[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?

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

Oops, the p has tumbled over. Should be 1/(p^5).

[Dann Corbit]

I have so far run 4 sets of 40,000 games. Version 23.1 is the current version that stores in the hash table as follows:

I use 3 passes (if needed) to choose one entry from a bucket of four.

1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.

2. If that fails, I check to see if any entry is old, based on the "age" field. This would mean the entry came from the previous search (not the previous iteration). If there are any "old" entries, I replace one with the shallowest draft.

3. Otherwise, I simply search for the one with the shallowest draft and replace it, no matter what its origin and type.

Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.

so far:

Code: Select all

Crafty-23.1-1        2593    4    4 40000   48%  2610   23% 
Crafty-23.1-2        2591    4    4 40000   47%  2610   22% 
Crafty-23.1a-2       2589    4    4 40000   47%  2610   22% 
Crafty-23.1a-1       2588    3    4 40000   47%  2610   22% 

Not much difference, but the new version which never replaces EXACT entries from the same search unless the replacement is also EXACT seems to be a little worse. I am running each test 2 more times to see if they consistently rank lower than the normal pure depth-preferred replacement. Note that the error bar causes them to overlap so this difference is not very significant.

I think an interesting test would be to check the percentage of EXACT scores for a 4 CPU search of 6 seconds, one minute, 10 minutes and 100 minutes when EXACT scores are never removed. It seems logical to me that EXACT scores will crowd out the other kinds over time, even though they are a lot more rare on average.

The problem could be exacerbated easily by choosing a tiny hash of (for example) 1 MB. Though this would clearly amplify the problem, it would also illustrate what would happen to a larger hash table over time more easily.

[Gian-Carlo Pascutto]

1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.
[...]
Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.

This sounds wrong. So if an old PV node now fails low or high, you keep the result as if it were a PV node?

That should cause some performance loss indeed.

[Gian-Carlo Pascutto]

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.

How is it not relevant? The PV is relevant to the entire search, unless you know for sure the current iterations is your last (and even then, you want the PV, so you need to store it ANYWAY).

And it's trivial (both in CPU time and programming time) to feed the PV back into the TT immediately preceding a new search.

If you do this, you're just using two tables to do what could be accomplished by one.

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.

But it's not - as explained above the PV is always relevant - so again you're just proving my case for me.

[Gian-Carlo Pascutto]

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.

If we're going to talk about some kind of TT that is not at all like the classical one that stores move ordering and bound information per position, my comments quite obviously don't hold.

But the original question was about a Gerbil/Ferret style program with such a hashtable, so your comment is irrelevant.

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.

This is too vague to comment a lot on, but in general I never turn off the hashtables since about 50% of my program would stop working, and the PV will be the last of my worries then. It's a bit like asking how to debug a program with the move generator disabled

[xsadar]

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.

How is it not relevant? The PV is relevant to the entire search, unless you know for sure the current iterations is your last (and even then, you want the PV, so you need to store it ANYWAY).

And it's trivial (both in CPU time and programming time) to feed the PV back into the TT immediately preceding a new search.

If you do this, you're just using two tables to do what could be accomplished by one.

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.

But it's not - as explained above the PV is always relevant - so again you're just proving my case for me.

Notice that I never said the PV is not relevant to the rest of the search; I only said that it is not as relevant to the rest of the search. There's a big difference. All that means is that there are other positions that are more relevant to the remaining search than at least some of the PV positions.

[bob]

I have so far run 4 sets of 40,000 games. Version 23.1 is the current version that stores in the hash table as follows:

I use 3 passes (if needed) to choose one entry from a bucket of four.

1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.

2. If that fails, I check to see if any entry is old, based on the "age" field. This would mean the entry came from the previous search (not the previous iteration). If there are any "old" entries, I replace one with the shallowest draft.

3. Otherwise, I simply search for the one with the shallowest draft and replace it, no matter what its origin and type.

Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.

so far:

Code: Select all

Crafty-23.1-1        2593    4    4 40000   48%  2610   23% 
Crafty-23.1-2        2591    4    4 40000   47%  2610   22% 
Crafty-23.1a-2       2589    4    4 40000   47%  2610   22% 
Crafty-23.1a-1       2588    3    4 40000   47%  2610   22% 

Not much difference, but the new version which never replaces EXACT entries from the same search unless the replacement is also EXACT seems to be a little worse. I am running each test 2 more times to see if they consistently rank lower than the normal pure depth-preferred replacement. Note that the error bar causes them to overlap so this difference is not very significant.

I think an interesting test would be to check the percentage of EXACT scores for a 4 CPU search of 6 seconds, one minute, 10 minutes and 100 minutes when EXACT scores are never removed. It seems logical to me that EXACT scores will crowd out the other kinds over time, even though they are a lot more rare on average.

The problem could be exacerbated easily by choosing a tiny hash of (for example) 1 MB. Though this would clearly amplify the problem, it would also illustrate what would happen to a larger hash table over time more easily.

I did a little of this. I never use multiple-cpu tests as the results are impossible to reproduce, but for a 1 cpu test, hitting around 2.5Mnodes per second on the usual 8-core box I run on, I ran a few positions for 1 minute, using 16M hash entries. A rough guess is that at 150M nodes, with probably 80% of them not hashed due to q-search hashing not being done in Crafty, that left about 30M real nodes to store. About 2x the table capacity.

One position I ran only had 1000 EXACT scores when the search finished. A particularly bad position had over 4M EXACT scores after the search completed, but this position had multiple PV changes per iteration, and each new iteration would repeat but even the PVs themselves would change. It would probably be hard to produce 16M EXACT entries unless I did as you suggested and either multiplied the speed by 8x, or increased the time per search, or both.

[bob]

1. If the current hash signature matches any of the 4 table entries exactly, I overwrite that entry, period.
[...]
Version 23.1a does the same, except steps 1 and 3 do not replace a type of EXACT, unless the new entry itself is of type EXACT. The depth/draft is still used exactly as above.

This sounds wrong. So if an old PV node now fails low or high, you keep the result as if it were a PV node?

That should cause some performance loss indeed.

How are you going to stop that? All you had said was "if type is EXACT then it is a PV node".

My test was simply

In a set of four entries, find an old entry (previous search, not previous iteration). and choose the shallowest draft from that set of old entries;

if that fails;

Find the shallowest-draft non-EXACT and replace that;

If there are none,

Find the shallowest draft EXACT entry and replace but only if _this_ entry is also EXACT.

What other options can you suggest?

EXACT means that at some point during the current set of iterations, this position was evaluated as > alpha and < beta. Whether it was later replaced with another best move/path or not, this one sticks around for all time, or at least until the current search (not iteration) terminates at which time all current EXACT entries don't mean anything as they are now "old".