Page 1 of 2
Effect of the Hash Table size
Posted: Sun Apr 28, 2013 9:01 pm
by Laskos
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?
Re: Effect of the Hash Table size
Posted: Sun Apr 28, 2013 9:43 pm
by Steve Maughan
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
Re: Effect of the Hash Table size
Posted: Sun Apr 28, 2013 10:02 pm
by Laskos
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.
Re: Effect of the Hash Table size
Posted: Sun Apr 28, 2013 10:29 pm
by Steve Maughan
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
Re: Effect of the Hash Table size
Posted: Sun Apr 28, 2013 10:59 pm
by hgm
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.
Re: Effect of the Hash Table size
Posted: Sun Apr 28, 2013 11:30 pm
by Laskos
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?
Re: Effect of the Hash Table size
Posted: Mon Apr 29, 2013 8:12 pm
by ernest
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.
Re: Effect of the Hash Table size
Posted: Wed May 01, 2013 1:11 am
by Don
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
Re: Effect of the Hash Table size
Posted: Wed May 14, 2014 11:36 am
by Laskos
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.
Re: Effect of the hash table size.
Posted: Wed May 14, 2014 12:06 pm
by Ajedrecista
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.