Determining the age of TT buckets

[JuLieN]

I'm currently into the process of rewriting my engine's TT system, and I4m going for a multi-bucket one, with replacement of the oldest entries. But how does one determine a bucket age? How do those who use this system do it? My first idea is to maintain a total_node_count from the game's start and store it as the age (smaller values = older), but such an index would be 64bits (8 bytes) long, which takes quite a lot of room in a TT... is it worth it, or are there less costly schemes?

[bob]

I'm currently into the process of rewriting my engine's TT system, and I4m going for a multi-bucket one, with replacement of the oldest entries. But how does one determine a bucket age? How do those who use this system do it? My first idea is to maintain a total_node_count from the game's start and store it as the age (smaller values = older), but such an index would be 64bits (8 bytes) long, which takes quite a lot of room in a TT... is it worth it, or are there less costly schemes?

Simplest idea is to use a small "age counter" stored in each entry. Then you use a global "age" counter that is incremented each time a real move is made on the board, not during a search. Every time you store an entry, you store the global age counter. All entries stored during a single search will have the same age value. After you actually make a move, and increment the counter, you can tell whether an entry is current or old by comparing the stored age to the global age counter. Pretty simple idea that works...

[JuLieN]

I'm currently into the process of rewriting my engine's TT system, and I4m going for a multi-bucket one, with replacement of the oldest entries. But how does one determine a bucket age? How do those who use this system do it? My first idea is to maintain a total_node_count from the game's start and store it as the age (smaller values = older), but such an index would be 64bits (8 bytes) long, which takes quite a lot of room in a TT... is it worth it, or are there less costly schemes?

Simplest idea is to use a small "age counter" stored in each entry. Then you use a global "age" counter that is incremented each time a real move is made on the board, not during a search. Every time you store an entry, you store the global age counter. All entries stored during a single search will have the same age value. After you actually make a move, and increment the counter, you can tell whether an entry is current or old by comparing the stored age to the global age counter. Pretty simple idea that works...

Thanks, Bob, that looks simple and efficient! And I guess a 1024 (10bits) plies at max counter would be more than enough! (Most of my integer counters are set to 600 plies at most, but 512 < 600 <1024 plies...).

[hgm]

I use a 4-bit counter for the purpose, although probably two bit would already be sufficient. I want to distinguish the current search from the previous one from earlier. If an entry was not hit in the previous or current search, I overwrite it. If unused entries survive long enough to see the counter wrap, and be mistaken for entries that are still in use... Well, bad luck. Under conditions where this can happen, hash entries apparently are not a resource that is very much in demand. Better to have more entries in their because they are small, and waste some. (I use five 12-byte entries per bucket. The remaining 4 bytes are for aging counters and flags.)

[JuLieN]

I use a 4-bit counter for the purpose, although probably two bit would already be sufficient. I want to distinguish the current search from the previous one from earlier. If an entry was not hit in the previous or current search, I overwrite it. If unused entries survive long enough to see the counter wrap, and be mistaken for entries that are still in use... Well, bad luck. Under conditions where this can happen, hash entries apparently are not a resource that is very much in demand. Better to have more entries in their because they are small, and waste some. (I use five 12-byte entries per bucket. The remaining 4 bytes are for aging counters and flags.)

You're right, H.G., a 10-bits counter would just be totally oversized, because a stored position becomes useless whenever we reach the point when it can't happen again on the board... and that is when a pawn is moved or a piece is captured. So, at most, this counter should get at most 50 moves, after which this is a draw.

If one wanted to play safe one would then use a 6bits counter, but your 4bits one should be more than enough too, as a 16-moves old position probably has nothing to do anymore with the current one...

[hgm]

I should say that I update the age in the hash to the current counter value every time an entry is used. So if the counter would reach 16 it does not just mean it was first encountered 16 ply ago, but that it actually was not seen at all in the tree during a period of 16 ply.

Your 50-move reasoning is not completely sound, btw: a position after a Pawn move could already have been in the tree before that pawn move was made on the board.

[bob]

I'm currently into the process of rewriting my engine's TT system, and I4m going for a multi-bucket one, with replacement of the oldest entries. But how does one determine a bucket age? How do those who use this system do it? My first idea is to maintain a total_node_count from the game's start and store it as the age (smaller values = older), but such an index would be 64bits (8 bytes) long, which takes quite a lot of room in a TT... is it worth it, or are there less costly schemes?

Simplest idea is to use a small "age counter" stored in each entry. Then you use a global "age" counter that is incremented each time a real move is made on the board, not during a search. Every time you store an entry, you store the global age counter. All entries stored during a single search will have the same age value. After you actually make a move, and increment the counter, you can tell whether an entry is current or old by comparing the stored age to the global age counter. Pretty simple idea that works...

Thanks, Bob, that looks simple and efficient! And I guess a 1024 (10bits) plies at max counter would be more than enough! (Most of my integer counters are set to 600 plies at most, but 512 < 600 <1024 plies...).

3 bits is enough. It's not about "plies". If you use the age trick, those should be the first entries overwritten on the next search, which means they won't last long...

[Don]

I use a 4-bit counter for the purpose, although probably two bit would already be sufficient. I want to distinguish the current search from the previous one from earlier. If an entry was not hit in the previous or current search, I overwrite it. If unused entries survive long enough to see the counter wrap, and be mistaken for entries that are still in use... Well, bad luck. Under conditions where this can happen, hash entries apparently are not a resource that is very much in demand. Better to have more entries in their because they are small, and waste some. (I use five 12-byte entries per bucket. The remaining 4 bytes are for aging counters and flags.)

You're right, H.G., a 10-bits counter would just be totally oversized, because a stored position becomes useless whenever we reach the point when it can't happen again on the board... and that is when a pawn is moved or a piece is captured. So, at most, this counter should get at most 50 moves, after which this is a draw.

If one wanted to play safe one would then use a 6bits counter, but your 4bits one should be more than enough too, as a 16-moves old position probably has nothing to do anymore with the current one...

As HG says, 2 bits is enough. Even 1 bit would not be terrible but I think I would prefer at least 2 bits. If you are filling up the hash table on each search you would overwriting 99% of the previous entries, so no harm done. With 1 bit you might mistake the search done 2 moves ago for the current search and lose a little bit of space but with 2 bits there will be very little laying around from 3 searches earlier. Of course if your hash table is really large there might be a lot laying around, but then it doesn't matter than much anyway since you have plenty of space.

For Komodo, the number changes whenever I experiment with the hash tables. I use whatever bits are left over in the tt structure after provisioning everyone else. The smallest number I am comfortable with is 2 bits but at the moment it is 8 bits simply because I need 8 bits to align the size.

[Aleks Peshkov]

It may have sense to increment age counter not every new search, but only if an non-reversible move or non-reversible opponent reply have been made.

[bob]

It may have sense to increment age counter not every new search, but only if an non-reversible move or non-reversible opponent reply have been made.

Danger, Will Robinson...

If you do that, you end up with LOTS of old entries that cause problems. Deep Draft entries for old positions are bad news. If you are move 90, having made 45 whole moves since the last irreversible move, you will have great trouble storing things. And those positions from 45 moves ago may well not mean very much this deep into the game because they don't include rep / 50 move info and are going to be pretty misleading.

Most simply want to preserve entries during a single search (not single iteration, but a complete N-iteration search) while it is in progress, but as soon as it is done, overwrites can occur on everything from that search since we have started a new search... And we will prefer to overwrite old search positions first...