## Effect of the Hash Table size

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Posts: 10949
Joined: Wed Jul 26, 2006 8:21 pm

### Effect of the Hash Table size

I wanted to see how the strength of the engine (Houdini 3) is affected by the Hash Table size when the size of the table is reasonable for given time control (1'+1'' games).

Code: Select all

``````   Program                                   Score       %     Elo    +   -    Draws

1 Houdini 3 64MB                       &#58; 2062.5/4000  51.6   3005   8   8   40.6 %
2 Houdini 3  4MB                       &#58; 1937.5/4000  48.4   2995   8   8   40.6 %
``````
+11 Elo points for a factor of 16 in Hash Table size, meaning close to 3 points per doubling the Hash Table size at reasonable size (when pretty much the hash fills up). Do others have empirical data on this?

Steve Maughan
Posts: 1089
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

### Re: Effect of the Hash Table size

The time control probably has a lot to do with the results. At this fast time control you're not super-saturating the smaller hash table, so the benefits of the larger hash table are not shining through.

Steve

Posts: 10949
Joined: Wed Jul 26, 2006 8:21 pm

### Re: Effect of the Hash Table size

Steve Maughan wrote:The time control probably has a lot to do with the results. At this fast time control you're not super-saturating the smaller hash table, so the benefits of the larger hash table are not shining through.

Steve
With the average 2 seconds per move, 3M nps, the required Hash Table is about 100MB or so for Houdini 3, so even the larger Hash is usually close to be saturated.

Steve Maughan
Posts: 1089
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

### Re: Effect of the Hash Table size

Hi Kai,

You're right. I hadn't done the maths. If there are 16 bytes per entry the hash table would be 91 Mb for 3 mnps after 2 seconds .

Maybe this emphasizes the importance of the hash table for cuttoffs due to recent search activity. The large table may also have a detrimental impact on the cache hits.

But knowing this I am surprise that the difference between 4 Mb and 64 Mb is so small in terms of strength.

Best regards,

Steve

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

### Re: Effect of the Hash Table size

I never measured Elo directly, but when I was evaluating replacement schemes my best result (equidistributed-draft replacement) produced doubling of the search time for a 4096-fold reduction of hash size. Assuming Elo=100 ln T, this would mean 100/12 = 8.33 Elo per hash doubling.

Posts: 10949
Joined: Wed Jul 26, 2006 8:21 pm

### Re: Effect of the Hash Table size

hgm wrote:I never measured Elo directly, but when I was evaluating replacement schemes my best result (equidistributed-draft replacement) produced doubling of the search time for a 4096-fold reduction of hash size. Assuming Elo=100 ln T, this would mean 100/12 = 8.33 Elo per hash doubling.
Isn't it log(2)*100/12 ~ 5.8 Elo per doubling?

ernest
Posts: 1945
Joined: Wed Mar 08, 2006 7:30 pm

### Re: Effect of the Hash Table size

Laskos wrote:With the average 2 seconds per move, 3M nps, the required Hash Table is about 100MB or so for Houdini 3
What are your assumptions (concerning Houdini hash "filling")?
If you assume 2 nodes => 1 hash entry (hash in qsearch), that gives a "filling" of only 2*3*16/2 = about 50MB.

Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

### Re: Effect of the Hash Table size

SzG wrote:Years ago I did tests of this kind and found an increase of about 5 Elos for every doubling of hash size.
The quoted figure used to be 7% per doubling, but that was years ago. Of course as usual that is based on the assumption that the hash table is currently too small.

Don
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

Posts: 10949
Joined: Wed Jul 26, 2006 8:21 pm

### Re: Effect of the Hash Table size

Steve Maughan wrote:The time control probably has a lot to do with the results. At this fast time control you're not super-saturating the smaller hash table, so the benefits of the larger hash table are not shining through.

Steve
I went to the safe side, well saturating the hash table, and measured another way the benefit of hash table of Houdini 4, with time-to-depth (TTD) on 100 positions. Average time per position 30 seconds, speed on 4 cores about 8-9Mnps, the hash table needed is well above 1GB. I used 4MB and 256MB hash tables for comparison on TTD, well inside the necessary:

Code: Select all

``````H4 on 4 cores&#58;
100 positions Depth=21   4MB time&#58; 53&#58;02
100 positions Depth=21 256MB time&#58; 32&#58;32``````
The benefit, assuming 100*log[time] Elo points per doubling time is 11 Elo points from doubling the hash table, when the hash table is clearly saturated.

A similar result I get in direct games with SF, but direct games are more tedious: 1' + 1'' hash 1MB and hash 16MB, both well saturated in games:

Code: Select all

``````Score of SF 16MB vs SF 1MB&#58; 293 - 96 - 834  &#91;0.58&#93; 1223
ELO difference&#58; 56
Finished match
``````
Here 14 Elo points for doubling hash table, but at somewhat shorter TC. I guess 11 Elo points is safe to say at blitz and a bit longer TC for SF too.

Ajedrecista
Posts: 1578
Joined: Wed Jul 13, 2011 7:04 pm
Contact:

### Re: Effect of the hash table size.

Hello Kai:

Code: Select all

``````H4 on 4 cores&#58;
100 positions Depth=21   4MB time&#58; 53&#58;02
100 positions Depth=21 256MB time&#58; 32&#58;32``````
The benefit, assuming 100*log[time] Elo points per doubling time is 11 Elo points from doubling the hash table, when the hash table is clearly saturated.
Could you explain a little more from where do you obtain the figure of 11 Elo with your data, please? I am a bit blind today.