Transposition Age Tutorial

[D Sceviour]

It would be nice to have a tutorial on how to implement a transposition age for hash. The wiki definition on aging gives:

While early implementations and programs relying on root pre-processing to guide search and evaluation were obligated to clear the hash table between root positions, most todays programs do not, to profit from entries of previous searches. Nevertheless, to avoid persistence of old entries which may no longer occur from the current root, aging is used to likely replace those entries by new ones, even if their draft and flags would otherwise protect them.

https://chessprogramming.wikispaces.com ... tion+Table

This is helpful for describing a theoretical purpose of transposition age, but is vague on implementation. My current empirical tests (without using any transposition age information) show that erasing the hash table between iterations will slightly weaken overall play. Another observation is that erasing everything but the hash best move between iterations produces the same results as not erasing anything. That is, erasing the hash scores between iteration makes no difference. This indicates the most important aspect of a hash table is to keep a best move to search first, and not to hold too strict to a value bound.

How does aging differ from hash depth?
How many bits should be allocated for a time stamp in the hash save?
What happens if the transposition age is not saved, and the hash table is not erased between root moves?
How is transposition age affected by threading, or is threading duplication the only reason for transposition age?
Will lazy SMP make a new adjustment to aging?

[mar]

aging does not clear hash table. age is simply a hint that helps to choose which entry to replace when storing new value into TT (you prefer fresh values); I only use age to distinguish between current and old searches

I increment the age counter at the start of iterative deepening loop => this means that lazy SMP helpers will use the same age as current main search thread (copied into lazy SMP state before ID loop)

how many bits... well I use 6 now (stored in the same byte as hash bounds [2 bits]), but it's well possible that it's more than necessary

this is what I do, YMMV

[D Sceviour]

aging does not clear hash table. age is simply a hint that helps to choose which entry to replace when storing new value into TT (you prefer fresh values); I only use age to distinguish between current and old searches

I increment the age counter at the start of iterative deepening loop => this means that lazy SMP helpers will use the same age as current main search thread (copied into lazy SMP state before ID loop)

how many bits... well I use 6 now (stored in the same byte as hash bounds [2 bits]), but it's well possible that it's more than necessary

this is what I do, YMMV

The best that I can understand is that transposition age is only a flag to indicate whether time can be save by not re-storing hash values if the same information was found from a previous search. That is, it accomplishes nothing and in no way affects the scoring or outcome of a search.

If this is true then what is the wiki quotation talking about when it refers to "early implementations and programs relying on root pre-processing to guide search and evaluation were obligated to clear the hash table between root positions..." ?

[mar]

The best that I can understand is that transposition age is only a flag to indicate whether time can be save by not re-storing hash values if the same information was found from a previous search. That is, it accomplishes nothing and in no way affects the scoring or outcome of a search.

No.
Think of age as a counter whose n lsbits help you distinguish current from old searches; so that storing into TT will always prefer to overwrite entries from old searches.
This is exactly what you want - to get rid of old entries as the game progresses, but not at all costs (you can still get TT hits from old searches not overwritten by more recent searches, so they "fade out" rather than being wiped out by clearing TT)

[D Sceviour]

This is exactly what you want - to get rid of old entries as the game progresses...

Understood. However, it is not necessary to consider transposition age to do this. Simply overwrite the existing hash entry - period.

...but not at all costs (you can still get TT hits from old searches not overwritten by more recent searches, so they "fade out" rather than being wiped out by clearing TT)

Not understood. A transposition probe comes before a transposition write. A TT hit can come without considering transposition age. At least I have seen no examples from other source code where transposition age is considered during the hash probe phase.

[bob]

aging does not clear hash table. age is simply a hint that helps to choose which entry to replace when storing new value into TT (you prefer fresh values); I only use age to distinguish between current and old searches

I increment the age counter at the start of iterative deepening loop => this means that lazy SMP helpers will use the same age as current main search thread (copied into lazy SMP state before ID loop)

how many bits... well I use 6 now (stored in the same byte as hash bounds [2 bits]), but it's well possible that it's more than necessary

this is what I do, YMMV

The best that I can understand is that transposition age is only a flag to indicate whether time can be save by not re-storing hash values if the same information was found from a previous search. That is, it accomplishes nothing and in no way affects the scoring or outcome of a search.

If this is true then what is the wiki quotation talking about when it refers to "early implementations and programs relying on root pre-processing to guide search and evaluation were obligated to clear the hash table between root positions..." ?

The idea is "what do I overwrite?" The answer is "first overwrite positions stored from older searches since the game has moved on and they might not be useful. Then overwrite using whatever criteria you choose, such ad depth-preferred, or whatever."

If the table age is different from the current age, overwrite immediately. If they are the same, use other criteria. This is a well-known idea that originated in blitz/cray blitz a LONG time ago as a way of avoiding clearing the hash and losing possibly useful information.

[bob]

aging does not clear hash table. age is simply a hint that helps to choose which entry to replace when storing new value into TT (you prefer fresh values); I only use age to distinguish between current and old searches

I increment the age counter at the start of iterative deepening loop => this means that lazy SMP helpers will use the same age as current main search thread (copied into lazy SMP state before ID loop)

how many bits... well I use 6 now (stored in the same byte as hash bounds [2 bits]), but it's well possible that it's more than necessary

this is what I do, YMMV

The best that I can understand is that transposition age is only a flag to indicate whether time can be save by not re-storing hash values if the same information was found from a previous search. That is, it accomplishes nothing and in no way affects the scoring or outcome of a search.

If this is true then what is the wiki quotation talking about when it refers to "early implementations and programs relying on root pre-processing to guide search and evaluation were obligated to clear the hash table between root positions..." ?

The idea is "what do I overwrite?" The answer is "first overwrite positions stored from older searches since the game has moved on and they might not be useful. Then overwrite using whatever criteria you choose, such ad depth-preferred, or whatever."

If the table age is different from the current age, overwrite immediately. If they are the same, use other criteria.

[Evert]

...but not at all costs (you can still get TT hits from old searches not overwritten by more recent searches, so they "fade out" rather than being wiped out by clearing TT)

Not understood. A transposition probe comes before a transposition write. A TT hit can come without considering transposition age. At least I have seen no examples from other source code where transposition age is considered during the hash probe phase.

Where is considering the age for hits mentioned?
A hit is a hit. The age is only important when you store, and even then only if you need to decide what entry to overwrite. If you don't use one, the TT will fill up with stale deep entries that are never replaced (to a degree - you should always store something, so something will get overwritten at every store).

[Evert]

If the table age is different from the current age, overwrite immediately. If they are the same, use other criteria.

So I guess that with respect to the question "how many bits should be in the age counter", the answer is "at least 1, but more is better"?

Has that ever been looked at? I would guess that 1 bit is considerably better than no history counter at all, and then you see diminishing returns until the period for the counted to wrap is longer than the life-time of an entry. I have no idea how long the latter is (I suppose that would be easy enough to test though).

[D Sceviour]

The idea is "what do I overwrite?" The answer is "first overwrite positions stored from older searches since the game has moved on and they might not be useful. Then overwrite using whatever criteria you choose, such ad depth-preferred, or whatever."

If the table age is different from the current age, overwrite immediately. If they are the same, use other criteria. This is a well-known idea that originated in blitz/cray blitz a LONG time ago as a way of avoiding clearing the hash and losing possibly useful information.

If the current age is the same as the hash entry, that indicates a previous hash miss due to bounds. One could still overwrite everything without generating an error.

Why not overwrite everything? That is, what type of error could be expected if everything is not overwritten by considering/ignoring transposition age? Is the only difference the amount of time saved by avoiding a few bit shifts during the hash save process? If so, there must be a trade-off with the amount of extra calculation extracting, updating and cache loading a tt->transposition_age.

I take it that erasing the hash table during the Cray period was a wasted effort. What type of error was expected if the hash table was not erased (other than lost information)?