Effect of the Hash Table size

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

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Laskos
Posts: 9441
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Effect of the Hash Table size

Post by Laskos » Sun Apr 28, 2013 7:01 pm

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                       : 2062.5/4000  51.6   3005   8   8   40.6 %
  2 Houdini 3  4MB                       : 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?

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

Re: Effect of the Hash Table size

Post by Steve Maughan » Sun Apr 28, 2013 7:43 pm

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

User avatar
Laskos
Posts: 9441
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Effect of the Hash Table size

Post by Laskos » Sun Apr 28, 2013 8:02 pm

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.

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

Re: Effect of the Hash Table size

Post by Steve Maughan » Sun Apr 28, 2013 8:29 pm

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

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

Re: Effect of the Hash Table size

Post by hgm » Sun Apr 28, 2013 8:59 pm

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.

User avatar
Laskos
Posts: 9441
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Effect of the Hash Table size

Post by Laskos » Sun Apr 28, 2013 9:30 pm

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: 1860
Joined: Wed Mar 08, 2006 7:30 pm

Re: Effect of the Hash Table size

Post by ernest » Mon Apr 29, 2013 6:12 pm

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.

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

Re: Effect of the Hash Table size

Post by Don » Tue Apr 30, 2013 11:11 pm

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.

User avatar
Laskos
Posts: 9441
Joined: Wed Jul 26, 2006 8:21 pm
Full name: Kai Laskos

Re: Effect of the Hash Table size

Post by Laskos » Wed May 14, 2014 9:36 am

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:
100 positions Depth=21   4MB time: 53:02
100 positions Depth=21 256MB time: 32: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: 293 - 96 - 834  [0.58] 1223
ELO difference: 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.

User avatar
Ajedrecista
Posts: 1398
Joined: Wed Jul 13, 2011 7:04 pm
Location: Madrid, Spain.
Contact:

Re: Effect of the hash table size.

Post by Ajedrecista » Wed May 14, 2014 10:06 am

Hello Kai:
Laskos wrote:

Code: Select all

H4 on 4 cores:
100 positions Depth=21   4MB time: 53:02
100 positions Depth=21 256MB time: 32: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.

Thanks in advance.

Regards from Spain.

Ajedrecista.

Post Reply