Effect of the Hash Table size

[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?

[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

[Laskos]

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]

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]

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.

[Laskos]

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]

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]

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

[Laskos]

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.

[Ajedrecista]

Hello Kai:

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.