Transposition Age Tutorial

[D Sceviour]

It might be possible to overwrite an important hash entry that has not been searched yet in the current iteration. Therefore, would it be prudent to test transposition age + 2 to make sure that an about-to-be used entry is not overwritten prematurely?

In theory you could replace the one with the oldest age first. I use depth + age myself. If an entry comes from an older iteration, I replace the one with the lowest draft.

If an entry has been missed for at least one iteration, then the likelihood of it ever being used should be nil. Of course, all these conditional tests take time, as if there wasn't already a ton of stuff to re-test.
Instead of testing (age != transposition_age), test (age + 1 < transposition_age).

[mar]

Instead of testing (age != transposition_age), test (age + 1 < transposition_age).

this won't work because of limited storage age is cyclic; also I'm pretty sure you meant trans_age + 1 < age

[bob]

It might be possible to overwrite an important hash entry that has not been searched yet in the current iteration. Therefore, would it be prudent to test transposition age + 2 to make sure that an about-to-be used entry is not overwritten prematurely?

In theory you could replace the one with the oldest age first. I use depth + age myself. If an entry comes from an older iteration, I replace the one with the lowest draft.

If an entry has been missed for at least one iteration, then the likelihood of it ever being used should be nil. Of course, all these conditional tests take time, as if there wasn't already a ton of stuff to re-test.
Instead of testing (age != transposition_age), test (age + 1 < transposition_age).

How do you come to that conclusion? Each successive iteration searches the same basic tree, extending it one ply deeper. I suspect you don't mean iteration above, but unique search from a different root position?

[D Sceviour]

It might be possible to overwrite an important hash entry that has not been searched yet in the current iteration. Therefore, would it be prudent to test transposition age + 2 to make sure that an about-to-be used entry is not overwritten prematurely?

In theory you could replace the one with the oldest age first. I use depth + age myself. If an entry comes from an older iteration, I replace the one with the lowest draft.

If an entry has been missed for at least one iteration, then the likelihood of it ever being used should be nil. Of course, all these conditional tests take time, as if there wasn't already a ton of stuff to re-test.
Instead of testing (age != transposition_age), test (age + 1 < transposition_age).

How do you come to that conclusion? Each successive iteration searches the same basic tree, extending it one ply deeper. I suspect you don't mean iteration above, but unique search from a different root position?

Crafty updates the transposition age after every probe and not just after every hash save. Therefore the older the age, the more likely the entry will never be used again. It may be theoretically possible for a critical position to exist in the tt whose age has not yet been updated and is older than the current transposition age. It is in danger of being overwritten if the test is (age != transposition_age). The frequency of such a critical occurrence is unknown. The age+1 suggestion was intended as a quick-fix try to avoid overwriting an important hash entry. Ideally it would be best to loop through the entries to locate the oldest age to overwrite, but of course that takes extra resources.

Another suggestion from the OP is to root pre-process the hash table between iterations and zero any entries whose transposition age exceeds a critical value. This should reduce some decision overhead.

[bob]

It might be possible to overwrite an important hash entry that has not been searched yet in the current iteration. Therefore, would it be prudent to test transposition age + 2 to make sure that an about-to-be used entry is not overwritten prematurely?

In theory you could replace the one with the oldest age first. I use depth + age myself. If an entry comes from an older iteration, I replace the one with the lowest draft.

If an entry has been missed for at least one iteration, then the likelihood of it ever being used should be nil. Of course, all these conditional tests take time, as if there wasn't already a ton of stuff to re-test.
Instead of testing (age != transposition_age), test (age + 1 < transposition_age).

How do you come to that conclusion? Each successive iteration searches the same basic tree, extending it one ply deeper. I suspect you don't mean iteration above, but unique search from a different root position?

Crafty updates the transposition age after every probe and not just after every hash save. Therefore the older the age, the more likely the entry will never be used again. It may be theoretically possible for a critical position to exist in the tt whose age has not yet been updated and is older than the current transposition age. It is in danger of being overwritten if the test is (age != transposition_age). The frequency of such a critical occurrence is unknown. The age+1 suggestion was intended as a quick-fix try to avoid overwriting an important hash entry. Ideally it would be best to loop through the entries to locate the oldest age to overwrite, but of course that takes extra resources.

Another suggestion from the OP is to root pre-process the hash table between iterations and zero any entries whose transposition age exceeds a critical value. This should reduce some decision overhead.

If you are talking about the "age" field, it updates the age (only) when I get a signature match but the ages do not match. But what if you are at iteration 20, on the way to 30? At 20 you likely won't have hit all the positions from the previous search that might be useful, as the tree is not deep enough. Once you get to higher depths (iteration numbers) you begin to hit those entries. Since I start at iteration 1, it might be a while before I hit any of the old positions from higher depths (lower drafts).

Looping to find oldest age is trivial and free, because I already loop to find age mismatch and shallowest draft... I just had better tree sizes with draft-preferred, even when choosing among older ages, so I went with the current algorithm. That's why the age field is so big, but since there was no incentive to reduce it after it failed, I left it as is but using depth-preferred-old-entry as the second threshold. Final pass goes with pure best draft.

I certainly don't want to root preprocess after each iteration either. I often run with 64 gigs of hash entries, 4B entries. I don't want to loop over that as it will flush EVERYTHING out of cache, not to mention taking a significant amount of time. I believe Cray Blitz was the first program to use the AGE approach, rather than clearing the hash completely. We did it for speed, even back in 1980 or so. I don't see how this would reduce any decision-making overhead either. You STILL have to pass over the entries.

[D Sceviour]

I certainly don't want to root preprocess after each iteration either. I often run with 64 gigs of hash entries, 4B entries. I don't want to loop over that as it will flush EVERYTHING out of cache, not to mention taking a significant amount of time. I believe Cray Blitz was the first program to use the AGE approach, rather than clearing the hash completely. We did it for speed, even back in 1980 or so. I don't see how this would reduce any decision-making overhead either. You STILL have to pass over the entries.

Not after every iteration, but after every move. I have been using 1G hash table clearing, and partial table clearing, between moves for a number of different reasons and experiments. There is no noticeable delay although it was not timed. I am not sure about 64G.

I do not know enough about hardware cache usage to understand why that would flush EVERYTHING out of the cache. The speed advantage is that a null entry can be found before testing everything in the bucket.

[bob]

I certainly don't want to root preprocess after each iteration either. I often run with 64 gigs of hash entries, 4B entries. I don't want to loop over that as it will flush EVERYTHING out of cache, not to mention taking a significant amount of time. I believe Cray Blitz was the first program to use the AGE approach, rather than clearing the hash completely. We did it for speed, even back in 1980 or so. I don't see how this would reduce any decision-making overhead either. You STILL have to pass over the entries.

Not after every iteration, but after every move. I have been using 1G hash table clearing, and partial table clearing, between moves for a number of different reasons and experiments. There is no noticeable delay although it was not timed. I am not sure about 64G.

I do not know enough about hardware cache usage to understand why that would flush EVERYTHING out of the cache. The speed advantage is that a null entry can be found before testing everything in the bucket.

Cache replaces using an LRU algorithm. If you stomp through 1gb, that will be the most recently used data and since it is larger than cache, it will be almost the only thing left in cache after the loop completes. I say "almost all" because the loop itself (code) will be in cache, obviously.

And you can't avoid testing everything in the bucket, because you first have to see if you have an exact signature match before adding a new entry, so you pass over the bucket irregardless. I don't see any gain whatever in trying to avoid the simple "age" idea. As the saying goes, "if it works..."

[Zenmastur]

... Note that the number of unique positions in a tree is often an order of magnitude lower than the number of nodes the search reports, due to transpositions. In the graphs I showed earlier you can see that the search only starts to slow down when the overload factor gets above 10 (= total nodes in tree 10 times larger than the number of hash entries).

I think you're misinterpreting your graph. Taken from an elementary course on algorithms:

“Theorem 6.16 The expected number of items needed to fill all slots of a hash table of size k is between k ln k +1/2k and k ln k +k.”

If you construct a table with k set to 2^n for n=10 to 40 you will notice that when n~=14 it takes about 10 times the number of unique stores as entries in the table to fill it. However, when n=34 it takes about 24 times as many unique stores as the table has entries to completely fill it. This is for a bucket size of one. I haven't done an analysis for larger bucket sizes but, it should be intuitively obvious that the number of unique stores will not be smaller with larger bucket sizes. So, I think you are misinterpreting the cause of the delayed fill times. It is primarily a function of hash table size for a "simple" hash table. If the number of unique positions were really an order of magnitude less than the number of nodes searched then the hash table should never be full before 10*(k*ln k + k/2) nodes are processed. If you have a cache hit rate of 15% then this automatically implies there aren't that many transpositions or you have a worthlessly small and/or ineffective TT. The TT should never be full before (10*k*ln k + k/2)/(1-TT hit %) nodes have been processed if what you say is true.

There are clearly other factors involved besides this theorem that affect the number of nodes processed before the hash table is filled, like cache hit rate, the fact that the data being stored isn't IID, and bucket sizes to name a few.

Regards,

Forrest

[hgm]

This theorem uses 'full' in a meaning that has no practical relevance. I don't care if if there still is a single empty entry in a table of a million, and that it would take a million more stores to get a hit on that entry that fills it. From a performance point of view a table that is still 10% empty is practically indistinguishable from a full table. The performance starts to fall when you start to overwirte entries, and this in fact happens significantly before the number of stores equals the table size. In an always-replace table of size k after k stores 1/e of the table would still be empty. But only by virtue that 1/e of the stored entries have already been overwritten, which will cause a very significant performance drop.

I vaguely recall that for perft(6) the number of unique positions is already an order of magnitude smaller than the number of nodes.

[Zenmastur]

This theorem uses 'full' in a meaning that has no practical relevance. I don't care if if there still is a single empty entry in a table of a million, and that it would take a million more stores to get a hit on that entry that fills it. From a performance point of view a table that is still 10% empty is practically indistinguishable from a full table. The performance starts to fall when you start to overwirte entries, and this in fact happens significantly before the number of stores equals the table size. ...

I disagree. The purpose of a hash table is to get hits. One factor controlling the number of hits is the percentage of entries in the table that are occupied. If the TT is empty then it's completely worthless.
So, I guess you need to define the word “performance” explicitly as your current usage seems counter-intuitive and vague. I think a TT is performing at it's best when it's completely full since this is when it has the highest probability of producing a hit when all other factors are held constant.

This graph of yours:


Effect of hash-table size on search time

Seems to contradict your statement that “performance starts to fall when you start to overwirte entries". It's not clear how “loading factor” is defined as used in the graph but, assuming it is related to the number of unique stores in to a table of k entries in a linear way, (e.g. a loading factor of 10 represents 10 * k unique stores into a hash table of k entries), then it looks to me like the performance stays about the same over a wide range of “loading factors”. i.e. from ~ 0.5 to ~5. This contradicts your 1/e example.

...In an always-replace table of size k after k stores 1/e of the table would still be empty. But only by virtue that 1/e of the stored entries have already been overwritten, which will cause a very significant performance drop. ...

A “significant performance drop” as compared to what? An infinite size table?

I doubt this is true and your graph certainly doesn't support this conclusion. In order for there to be any degradation in performance a location has to be referenced at least 3 times. Once to place an entry in it, once to overwrite it, and once to reference the original data and this has to happen in that order. If the data in the cell is referenced and produces a hit before its over-written no performance is lost. At least not until another (fourth) reference to that location is made.

... I vaguely recall that for perft(6) the number of unique positions is already an order of magnitude smaller than the number of nodes.

I think I'll stand by my previous assertion that the number of entries in the hash table is the controlling factor here and not the number of transpositions, since if the transpositions were the cause of this effect the cache hit rate would be VERY high. Besides, what engine uses a full width search without Alpha-Beta which is what this statement seems to imply.

Regards,

Zen