"It just isn't conceivable that you can design a program strong enough to beat players like me."

October 23, 2016

Hash Baby Hash!

A popular frequently asked question by most chess engine users is: "How many memory should i set for hash tables?".

It's totally natural that the dilemma persists because there is not crystal clear answer to it. There are many parameters in the unknown equation:
* Computing speed
* Available RAM
* RAM access speed
* Time control used
* Time management style of the engine
If there are others that i'm not aware of, i'd say it's possible. You tell me.

And before i share what i've got in hand, a few notices:
* I just tell what i know and how i proceed for myself. I can't suggest i'm always correct.
* Most engines use hash size as power of 2. Even if you calculate let's say 395MB for the optimum size, you'll have to choose between 256 and 512MB.
* The optimum size is different from one engine to another.

After reading a lot here and there since years, i think various methods may come handy. Use them and decide for your case:


Check the available free RAM in your system, be it Windows or Android and allocate the nearest half of it for engine-to-engine games or the nearest lower size for a single engine. This is the simplest method which doesn't care about the engine. It may cause slowdowns in extreme cases like bullet games on a device with plenty of RAM.

Example: My Galaxy Note 2 has 2GB RAM with approx 900MB free on average. In this case, 900/2=450MB rounded down to the nearest 256MB is an acceptable choice for an engine tourney or i can set 512MB when i play vs Komodo (I wouldn't do that btw...)


The old utility i've shared HERE in my repository at box.com is designed to help calculate the hash size. It uses two different selectable formulas: Direct correlation with CPU frequency or Houdini 1.5 formula. I think both methods are insufficient with today's software/hardware combinations and they don't match well with Android but they can give an overall idea anyway.

Example with Std.Formula: Galaxy Note 2 has 4 cores running at 1600Mhz. For the default 900+1 TC of Rapidroid and 60 moves/game on average, the utility calculates 204.8MB and suggests 128MB.

Example using Houdini formula: There's no Fritz Benchmark for Android, so an interpolation is necessary. My PC is getting 5000 with Fritz Benchmark and runs SF7 at 2800 knps. As Galaxy Note 2 runs SF7 at 750 knps, it should get (5000/2800)*750 = 1340 knps with Fritz. I enter this to the utility. With all other parameters unchanged, it calculates 214.4MB and suggests 128MB once again.


For this, you absolutely need to monitor the hash usage during a test run. On a PC, Arena does the job. On an Android device, there was nothing until the latest build of Droidfish by Aprijal Pasaribu but now you can do the same on your cell phone too.

Komodo method is based on the assumption that the engine may need to use up to 3 times the average time per move of a typical game of 60 moves played with Fisher clocks. They suggest that the hash size must be high enough to ensure such 3x time usage does not fill more than 40% of the hash.

Above description is not easy to understand at once but it sounds reasonable, though i still find 40% is way too safe.

Komodo team says: Take the minutes as second and add the increment. Since Rapidroid uses 900+1 TC, for me that makes a test of (15+1) x 3 = 48 seconds. Therefore i run Komodo 10 on Galaxy Note 2 with hash display version of Droidfish. With 256MB hash, the usage trend goes like the following:
12" 16%
18" 24%
24" 32%
33" 44%
35" 46%
39" 54%
42" 55%
52" 65%
61" 73%
70" 80%
84" 86%
104" 93%

According to Komodo practice, my 256MB setting is low and i need something like 48 / ( 31 / 41 * 40 ) * 256 = 406 MB for 900+1 TC. However, i will continue to use 256MB no matter what. The 3x should correspond to 60% which still seems safe for me.


This method is simple too but can mislead when used for shortest time control targets. You may simply conduct a series of fixed time analysis from the starting position, using a different hash setting for each run, from the smallest to the biggest, one by one. You will notice a quick increase in smallest settings but it will diminish somewhere. You must then stop and take the setting where the knps don't increase anymore. The test duration of each run must match the TC you want to use. Don't forget to use 3x for Fischer TC. For fixed time per move, 1x should be enough for the beginning and middlegame but i didn't verify 1x for endgame phase.

Conclusion: There is no high precision value to calculate. You'd better practice all above methods and choose the most common suggestion. Remember that your games or engine tests will not be non sense just because you have choosen 128MB instead of a better 256MB or vice versa. You only have to beware the extremely bad settings.


Alex Borisov said...

Gurcan, thank you for the article! Better late than never :-)

Alex Borisov said...

What about Cfish and Brainfish for the next Rapidroid? They are out of playing zone :(

Gurcan Uckardes said...

There's room for one Stockfish. Introducing Brainfish wouldn't be fair as it gets time advantage when it plays first move from book. Cfish has no book but it must always follow the main branch. So main branch must stay in Rapidroid. However, i will schedule a closed tournament separately. I already have 20000+ blitz games between development versions and two newbies can join this Fishpit.