Hash tables flood my mind

[Gabor Szots]

Geschrieben von: / Posted by: Gabor Szots at 03 April 2000 08:55:05:
Hello everybody,
I have posted a question in CCC forum, but the answers I got haven't quite satisfied me. I'm afraid I was misunderstood. Perhaps here somebody can help.
I feel strongly that for each and every machine-chess engine-time control combination there must be an absolute hash table size limit over which you cannot increase performance. Why? Because with a given maximal NPS and a given maximal time for a move, the memory that can be filled with data while thinking on a move is also limited. I believe that the maximal hash size that still makes sense is can be obtained by the following product:
(NPS) x (time/one move) x (number of bytes needed to store the data for one node)
To allocate a bigger hash is simply wasting memory. Even the memory obtained by the above formula may be too big for practical purposes, and a sensible compromise shall be chosen.
Your comments in this matter would be highly appreciated. Thanks in advance.
Gabor

[Inmann Werner]

Geschrieben von: / Posted by: Inmann Werner at 03 April 2000 11:38:15:
Als Antwort auf: / As an answer to: Hash tables flood my mind geschrieben von: / posted by: Gabor Szots at 03 April 2000 08:55:05:

Hello everybody,
I have posted a question in CCC forum, but the answers I got haven't quite satisfied me. I'm afraid I was misunderstood. Perhaps here somebody can help.
I feel strongly that for each and every machine-chess engine-time control combination there must be an absolute hash table size limit over which you cannot increase performance. Why? Because with a given maximal NPS and a given maximal time for a move, the memory that can be filled with data while thinking on a move is also limited. I believe that the maximal hash size that still makes sense is can be obtained by the following product:
(NPS) x (time/one move) x (number of bytes needed to store the data for one node)
To allocate a bigger hash is simply wasting memory. Even the memory obtained by the above formula may be too big for practical purposes, and a sensible compromise shall be chosen.
Your comments in this matter would be highly appreciated. Thanks in advance.
Gabor

The whole thing is not as simple
As hashing says, you do not fill the hashtables sequentially, but by hashcode.
After filling of about 20%, the collisions begin, and something is thrown out of the hashtable (maybe something important). As the hash fills further, the collisions increase.
Second, many programs do never clean the hash. So it would be good to have the last move, the ponder and the accurate thought move in Hash.
Then, many progs use more than 1 hash.(Pawn hashing)
I can show on my prog, InmiChess, but it will be not so different to others.
Example:
Pawnhash: about 132000 entrys = 6 MB
Hashtable 1: 1000000 entrys = 16MB
Hashtable 2: 500000 entrys = 8MB
At Pawn hashing, you store the evals of pawn positions. As there are not so many different pawn positions possible (exactly pawns and kings), 132000 entrys is IMHO good. That costs fix 6 MB.
The two hashtables, you can count together simple, so we have 24 MB hash, makes 1500000 entrys.
I did the position LCTCMB01 for test
1)
1595323 nodes searched, 171308 entrys in first hash, 1189 hash entrys in second, 574 collissions.
2)
23 sec, 4000000 nodes searched, 412316 entrys in first hash, 10939 in second, 7785 collissions (ok)
In a match, with 2) it would be ok. After this search, I ponder filling the hash, if ponder fails, i have to make a full search in next node, all filling the hash tables. The next searches do not fill as extensive, as the first one, as the hash is already filled with useful things, but after all 3 searches, the hash would be filled maybe more than 50% and the collisions increase.
So now, what about a formula????
Most important, make the hash small enough, that nothing is in a swap file!!!!, or you get killed!
for 4.000.000 Nodes per search, i would like 32 MB real hash most. (at my 170 KNPS Engine)
doubling nodes is doubling hash....
for analyse mode, you need only half of the hash for same search nodes.(as you only look at one position, no ponder etc.)
So what if I play 3 mins/per move games with my 170 KNPS engine?
if possible, and i have a lot of ram, i would give 200 MB!!!!!
(But because i do not have, i play with 24 MB)
So what, if I play 5/5 blitz at ICC?
I use 12 MB. it is enough...
The increase in play strength and hash size is not linear. Having some hash brings a big increase. But as you increase more, the benefit decreases. The benefit gets 0, if you have no collissions at all. When begins the wasting?
Werner

[Gabor Szots]

Geschrieben von: / Posted by: Gabor Szots at 03 April 2000 12:41:55:
Als Antwort auf: / As an answer to: Re: Hash tables flood my mind geschrieben von: / posted by: Inmann Werner at 03 April 2000 11:38:15:

I feel strongly that for each and every machine-chess engine-time control combination there must be an absolute hash table size limit over which you cannot increase performance. Why? Because with a given maximal NPS and a given maximal time for a move, the memory that can be filled with data while thinking on a move is also limited. I believe that the maximal hash size that still makes sense is can be obtained by the following product:
(NPS) x (time/one move) x (number of bytes needed to store the data for one node)
To allocate a bigger hash is simply wasting memory. Even the memory obtained by the above formula may be too big for practical purposes, and a sensible compromise shall be chosen.
Your comments in this matter would be highly appreciated. Thanks in advance.
Gabor

The whole thing is not as simple
As hashing says, you do not fill the hashtables sequentially, but by hashcode.
After filling of about 20%, the collisions begin, and something is thrown out of the hashtable (maybe something important). As the hash fills further, the collisions increase.
Second, many programs do never clean the hash. So it would be good to have the last move, the ponder and the accurate thought move in Hash.
Then, many progs use more than 1 hash.(Pawn hashing)
I can show on my prog, InmiChess, but it will be not so different to others.
Example:
Pawnhash: about 132000 entrys = 6 MB
Hashtable 1: 1000000 entrys = 16MB
Hashtable 2: 500000 entrys = 8MB
At Pawn hashing, you store the evals of pawn positions. As there are not so many different pawn positions possible (exactly pawns and kings), 132000 entrys is IMHO good. That costs fix 6 MB.
The two hashtables, you can count together simple, so we have 24 MB hash, makes 1500000 entrys.
I did the position LCTCMB01 for test
1)
1595323 nodes searched, 171308 entrys in first hash, 1189 hash entrys in second, 574 collissions.
2)
23 sec, 4000000 nodes searched, 412316 entrys in first hash, 10939 in second, 7785 collissions (ok)
In a match, with 2) it would be ok. After this search, I ponder filling the hash, if ponder fails, i have to make a full search in next node, all filling the hash tables. The next searches do not fill as extensive, as the first one, as the hash is already filled with useful things, but after all 3 searches, the hash would be filled maybe more than 50% and the collisions increase.
So now, what about a formula????
Most important, make the hash small enough, that nothing is in a swap file!!!!, or you get killed!
for 4.000.000 Nodes per search, i would like 32 MB real hash most. (at my 170 KNPS Engine)
doubling nodes is doubling hash....
for analyse mode, you need only half of the hash for same search nodes.(as you only look at one position, no ponder etc.)
So what if I play 3 mins/per move games with my 170 KNPS engine?
if possible, and i have a lot of ram, i would give 200 MB!!!!!
(But because i do not have, i play with 24 MB)
So what, if I play 5/5 blitz at ICC?
I use 12 MB. it is enough...
The increase in play strength and hash size is not linear. Having some hash brings a big increase. But as you increase more, the benefit decreases. The benefit gets 0, if you have no collissions at all. When begins the wasting?
Werner

Dear Werner,
I am most grateful having your exhaustive answer. I don't declare I have understood everything, but it made clear that I had been extremely naive making my above assumption. A big thank goes to you!
Only if I knew what IMHO means and what LCTCMB01 is!
Kind regards,
Gabor

[Inmann Werner]

Geschrieben von: / Posted by: Inmann Werner at 03 April 2000 12:58:46:
Als Antwort auf: / As an answer to: Re: Hash tables flood my mind geschrieben von: / posted by: Gabor Szots at 03 April 2000 12:41:55:

Dear Werner,
I am most grateful having your exhaustive answer. I don't declare I have understood everything, but it made clear that I had been extremely naive making my above assumption. A big thank goes to you!
Only if I knew what IMHO means and what LCTCMB01 is!
Kind regards,
Gabor

IMHO in my humble opinion
LCTCMB01 is a tactical position out of the LCTII Testsuite. Just for the test...
all the best
Werner
P.S: maybe, if in german, i could have explained better. But it is complicated theme and english is not my mother tongue.....