Transposition table replacement strategies

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Transposition table replacement strategies

Post by zd3nik » Tue Mar 01, 2016 4:26 am

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
Posts: 20643
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table replacement strategies

Post by bob » Tue Mar 01, 2016 4:46 am

zd3nik wrote: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
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Transposition table replacement strategies

Post by zd3nik » Tue Mar 01, 2016 5:28 am

bob wrote:
zd3nik wrote: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
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Transposition table replacement strategies

Post by zd3nik » Tue Mar 01, 2016 5:54 am

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.

User avatar
hgm
Posts: 23795
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition table replacement strategies

Post by hgm » Tue Mar 01, 2016 8:44 am

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
Posts: 161
Joined: Fri Oct 22, 2010 7:47 pm
Location: Austria

Re: Transposition table replacement strategies

Post by nionita » Tue Mar 01, 2016 6:38 pm

hgm wrote: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...

User avatar
hgm
Posts: 23795
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Transposition table replacement strategies

Post by hgm » Tue Mar 01, 2016 7:27 pm

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
Posts: 20643
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Transposition table replacement strategies

Post by bob » Wed Mar 02, 2016 12:23 am

zd3nik wrote: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
Posts: 469
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Transposition table replacement strategies

Post by D Sceviour » Wed Mar 02, 2016 4:09 am

hgm wrote: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
Posts: 193
Joined: Wed Mar 11, 2015 2:34 am
Location: United States
Contact:

Re: Transposition table replacement strategies

Post by zd3nik » Wed Mar 02, 2016 4:34 am

hgm wrote: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

Post Reply