Transposition Age Tutorial

[mar]

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.

sure, if you always overwrite and your bucket size is 1 then you don't need any aging scheme

assume your TT entry is 8 bytes and use bucket size of 8 entries
(assuming cacheline size is 64 bytes)
in this case you iterate entries and compute a score of what to replace
simply put:
- matching signature has highest weight (assume higher score = better candidate for being replaced) => you can abort right away
- mismatching age has second highest weight
- depth difference has third highest weight
- (what I do) exact value from pv nodes have fourth highest weight

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

i don't follow, sorry why would you want to consider age in probing? aging simply helps to decide what to replace during TT store (naturally you can only probe entries stored in TT at the time of probing)

[bob]

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

This is not about errors. But if you do a probe, get a hit, the bound or draft is not sufficient so you do a real search. You MUST store the result of this new search, not keep the old one. Remember, it did NOT provide any help.

The reason for clearing was if you use a simple depth-preferred format, you eventually can fill up the table with deep-draft entries that came from so far back in the game they are (a) useless and (b) can't be replaced due to their deep draft.

You always want current info, but you want to wisely choose what to replace. If you get a key match but can't use the entry, you would always want to overwrite that with something that is better, the result from the current search once it completes.

You want to keep the entries that save you the most work. these are (in no particular order) those with the deepest draft, since they will cut the search off closer to the root and save more effort; those from the current search, rather than a previous search (not iteration, but different root position search) since advancing along in the game makes older positions more and more irrelevant.

[bob]

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

If you use one, you can't differentiate between a position stored two moves ago and one stored this search, which would be somewhat problematic. I believe I am using 9 bits, but only because I use a 16 byte hash entry and have the bits handy. I worked on an 8 byte hash entry last year, but decided it was too dangerous. There I cut it back to 3 bits.

In Cray Blitz, we only used 1 bit, in fact, as we used a shorter table entry and space was tight.

[D Sceviour]

You want to keep the entries that save you the most work. these are (in no particular order) those with the deepest draft, since they will cut the search off closer to the root and save more effort; those from the current search, rather than a previous search (not iteration, but different root position search) since advancing along in the game makes older positions more and more irrelevant.

Draft has to be read in conjunction with hash type. I found frequently that a hash type could flip back and forth between fail-high and fail low with every significant change in alpha/beta bounds. It is quite possible to overwrite a fail-high that has been searched 12 ply, with a new fail-low that has been searched only 5 ply (for example, found in a null move search transposition) and vice-versa. If there is no error involved, then there is no problem with completely overwriting an entry with a shallower draft. In fact, it is looking more comfortable to do this.

[hgm]

Age is only important for replacement. If you have a replace-always table, there is nothing you need the age for. But better replacement schemes preferably not overwrite entries with a large draft ('depth preferred'). E.g. they can store each position in two (or four) slots, and then overwrite the entry with the lowest draft of those two (four).

This then causes the problem that entries with large draft will almost never be overwritten, except by entries of even larger draft, which then are even more difficult to overwrite. So near the end of the game 50% of your transposition table (or 75%) will be filled with entries of very large draft from searches made some 20 moves ago, which can never be reached anymore from the current root position because of irreversible moves played since. The engine will then have to work with the remaining half (or quarter) of the hash table only, for the positions of the current search, as the useless positions cannot be overwritten by them due to their high draft.

It is for this problem that people use age counters. Actually I think you need two bits: you want to disticnguish two kind of positions belonging to the current search (already visited and not yet visited), and older entries. So you cannot safely replace entries that were visited in the previous search yet during the current one, as they might be visited yet. So when you mark every accessed entry with a two-bit number representing the current search, you can safely overwrite what has the age counter set two or three searches earlier.

[D Sceviour]

If you have a replace-always table, there is nothing you need the age for.

This helps considerable in the basic understanding of transposition age. However, there are some other uses for age that might need clarifying. First is for analyzing a position. When clicking up and down the move list, it is obviously not necessary to overwrite anything if the position has already been searched before. On the other hand, one might want to see the complete search tree, so erasing the hash table can be of some use, and again transposition age is of no use.

The other case is strictly for PV nodes. If a previous search has calculated a PV to a depth of 12, then a subsequent iteration would be in error overwriting a PV to a depth of 6 since the depth is not sufficient to expose any useful alpha bounds, and it would wipe out the previous best move and path. Here, perhaps the algorithm could test a PV flag rather than a transposition depth.

[hgm]

If you would have a PV node of depth 12, you should never have anything of depth 6 to replace it with. If you need a depth 6 result, you would use the hash entry, and return the result immediately (hash cutoff).

Note that during analysis I found aging extremely counter-productive. Because you inndeed back up through the game very often, and it was extremely annoying this would lose you the correct scores of the side branches you analyzed before. Just because at some point the engine threw awayy these valuable results because it considered them 'old'. So in Shokidoki I now suppress incrementing the search number during analysis. Basically an interactive analysis session is one big search, the part closest to the root guided by hand.

[D Sceviour]

Note that during analysis I found aging extremely counter-productive. Because you inndeed back up through the game very often, and it was extremely annoying this would lose you the correct scores of the side branches you analyzed before. Just because at some point the engine threw awayy these valuable results because it considered them 'old'. So in Shokidoki I now suppress incrementing the search number during analysis. Basically an interactive analysis session is one big search, the part closest to the root guided by hand.

For analysis, perhaps the best thing to do is to erase everything but the best move. That way, the search is not interfered with noise but rather only accelerated. At least this helps for me.

[jwes]

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.

There is one case where you should consider the age while probing. If the TT has a depth and value that you can use without searching, then you should ensure that the age is set to the current age.

[bob]

You want to keep the entries that save you the most work. these are (in no particular order) those with the deepest draft, since they will cut the search off closer to the root and save more effort; those from the current search, rather than a previous search (not iteration, but different root position search) since advancing along in the game makes older positions more and more irrelevant.

Draft has to be read in conjunction with hash type. I found frequently that a hash type could flip back and forth between fail-high and fail low with every significant change in alpha/beta bounds. It is quite possible to overwrite a fail-high that has been searched 12 ply, with a new fail-low that has been searched only 5 ply (for example, found in a null move search transposition) and vice-versa. If there is no error involved, then there is no problem with completely overwriting an entry with a shallower draft. In fact, it is looking more comfortable to do this.

You want to try to avoid overwriting a 12 ply draft entry with a 5 ply entry if possible. But if the sigs match, overwrite it is...

I am not sure what you mean by "no error involved" however...