Transposition table replacement strategies

[zd3nik]

I've recently started tinkering with selective transposition table entry replacement strategies. Until now I've always used the simplest approach: 1 entry per hash slot and always replace.

What I'm experimenting with currently is 4 entries per hash slot (total bytes = 64) and the following replacement strategy:

1. use entry with exact key match if present
-- otherwise
2. use first entry with different "root move count" value if present
-- otherwise
3. use first entry with smallest search depth value

"Root move count" is the move number at the root of the search tree. So when searching root move number 7 any hash entries found with a root move number not equal to 7 (if any) will be replaced in step 2 wherever step 1 isn't satisfied.

With this logic I see a very slight Nodes/Second decrease (expected) and no real difference in playing strength (unexpected). Based on conversations I've seen on this site regarding this topic I was expecting a noticeable difference.

Has anyone out there made a similar change (gone from always replace strategy to something more "intelligent") and 1) seen a significant difference 2) measured/recorded the difference? And if so would you be willing to share your replacement strategy or provide some pointers?

I'm wondering if the difference made by such a change only surfaces under certain conditions. I've tried test positions as well as short tournaments.

Thanks,
STC

[bob]

I've recently started tinkering with selective transposition table entry replacement strategies. Until now I've always used the simplest approach: 1 entry per hash slot and always replace.

What I'm experimenting with currently is 4 entries per hash slot (total bytes = 64) and the following replacement strategy:

1. use entry with exact key match if present
-- otherwise
2. use first entry with different "root move count" value if present
-- otherwise
3. use first entry with smallest search depth value

"Root move count" is the move number at the root of the search tree. So when searching root move number 7 any hash entries found with a root move number not equal to 7 (if any) will be replaced in step 2 wherever step 1 isn't satisfied.

With this logic I see a very slight Nodes/Second decrease (expected) and no real difference in playing strength (unexpected). Based on conversations I've seen on this site regarding this topic I was expecting a noticeable difference.

Has anyone out there made a similar change (gone from always replace strategy to something more "intelligent") and 1) seen a significant difference 2) measured/recorded the difference? And if so would you be willing to share your replacement strategy or provide some pointers?

I'm wondering if the difference made by such a change only surfaces under certain conditions. I've tried test positions as well as short tournaments.

Thanks,
STC

You really HAVE to do an always replace strategy. The only issue is what do you replace. Not replacing something is not an option however, if you want reasonable performance.

[zd3nik]

I've recently started tinkering with selective transposition table entry replacement strategies. Until now I've always used the simplest approach: 1 entry per hash slot and always replace.

What I'm experimenting with currently is 4 entries per hash slot (total bytes = 64) and the following replacement strategy:

1. use entry with exact key match if present
-- otherwise
2. use first entry with different "root move count" value if present
-- otherwise
3. use first entry with smallest search depth value

"Root move count" is the move number at the root of the search tree. So when searching root move number 7 any hash entries found with a root move number not equal to 7 (if any) will be replaced in step 2 wherever step 1 isn't satisfied.

With this logic I see a very slight Nodes/Second decrease (expected) and no real difference in playing strength (unexpected). Based on conversations I've seen on this site regarding this topic I was expecting a noticeable difference.

Has anyone out there made a similar change (gone from always replace strategy to something more "intelligent") and 1) seen a significant difference 2) measured/recorded the difference? And if so would you be willing to share your replacement strategy or provide some pointers?

I'm wondering if the difference made by such a change only surfaces under certain conditions. I've tried test positions as well as short tournaments.

Thanks,
STC

You really HAVE to do an always replace strategy. The only issue is what do you replace. Not replacing something is not an option however, if you want reasonable performance.

The flow I give above always replaces something.

[zd3nik]

Let me clarify. When I say I started with "always replace" I meant always replace the one entry assigned to the hash slot the position maps to.

The new scheme has 4 entries to choose from per hash slot and the 3 step flow I describe above is used to decide which of the 4 entries to replace.

So, both strategies are "always replace" strategies. But the 3 step flow, in theory, will try to preserve the more valuable entries.

[hgm]

To see any effect of replacement strategy, you must work under conditions where a lot of replacement goes on. When there is nothing to replace it does not matter much how you do it. In particular, there isn't much replacement when the search tree is not at least 10x larger than the table. So if you do 1-min games (~1 sec/move) and your engine does 1Mnps, you will only start to see an effect when the hash table has fewer than 100K entries (i.e. < 1.6MB).

[nionita]

you will only start to see an effect when the hash table has fewer than 100K entries (i.e. < 1.6MB).

But then the whole TT will be in L3 cache, which again will be faster. So probably only longer time controls will be good for tests, but playing enough games will also take too long. Hard problem...

[hgm]

The point is that you should not try to test this by playing games. You should just measure time-do depth for a few hundred test positions.

[bob]

I've recently started tinkering with selective transposition table entry replacement strategies. Until now I've always used the simplest approach: 1 entry per hash slot and always replace.

What I'm experimenting with currently is 4 entries per hash slot (total bytes = 64) and the following replacement strategy:

1. use entry with exact key match if present
-- otherwise
2. use first entry with different "root move count" value if present
-- otherwise
3. use first entry with smallest search depth value

"Root move count" is the move number at the root of the search tree. So when searching root move number 7 any hash entries found with a root move number not equal to 7 (if any) will be replaced in step 2 wherever step 1 isn't satisfied.

With this logic I see a very slight Nodes/Second decrease (expected) and no real difference in playing strength (unexpected). Based on conversations I've seen on this site regarding this topic I was expecting a noticeable difference.

Has anyone out there made a similar change (gone from always replace strategy to something more "intelligent") and 1) seen a significant difference 2) measured/recorded the difference? And if so would you be willing to share your replacement strategy or provide some pointers?

I'm wondering if the difference made by such a change only surfaces under certain conditions. I've tried test positions as well as short tournaments.

Thanks,
STC

Root move counter idea seems bad. You do iteration N and move A is best. At N+1 A is replaced by B. You REALLY want to overwrite A's entry as you search other moves, just because it was bumped down to the second slot?

I don't see the reasoning behind that. Much more logical is to use an age replacement, so that positions from previous searches (not previous iterations) are replaced first. If that fails, replace shallowest draft.

[D Sceviour]

To see any effect of replacement strategy, you must work under conditions where a lot of replacement goes on. When there is nothing to replace it does not matter much how you do it. In particular, there isn't much replacement when the search tree is not at least 10x larger than the table. So if you do 1-min games (~1 sec/move) and your engine does 1Mnps, you will only start to see an effect when the hash table has fewer than 100K entries (i.e. < 1.6MB).

What is the point?

To demonstrate a multi-entry has table does anything, one must reduce the size of the hash table to force collisions. It certainly does not make sense to cripple the hash table just to get multi-entry hash to do something, as the results are probably unreliable anyway. Thus, at best you will see a break-even effect. In the early days of hashing, programmers were fighting with 512K hash tables. Multi-entry hash seems to be a desperate effort to wring out as much as possible from limited resources. With today’s available memory, multi-entry hash does not seem to make much difference.

[zd3nik]

To see any effect of replacement strategy, you must work under conditions where a lot of replacement goes on. When there is nothing to replace it does not matter much how you do it. In particular, there isn't much replacement when the search tree is not at least 10x larger than the table. So if you do 1-min games (~1 sec/move) and your engine does 1Mnps, you will only start to see an effect when the hash table has fewer than 100K entries (i.e. < 1.6MB).

Good point.

The testing I have done so far includes playing gauntlets with TT size set to 512MB and time control set to 2 min +1 sec inc or 1 min + 0.5 sec inc. Plus some EPD testing with short time limits.

I will try lowering the TT size and adjusting the time controls in my testing. Perhaps then I will see some difference.

Thanks,
STC