Hash table hit rate

[Stef Luijten]

What is a typical hit rate that you can expect from a sound hash table implementation? I see only about a 10% hit rate in the opening / middlegames, but have read somewhere that 20% is supposed to be a normal hit rate. In the endgame Wing's hitrate very often goes up to > 30%. By hit rate I mean number of hash hits / number of hash probes.
Wing has two hash tables ('depth preferred' and 'replace always').
Stef.

[Gerd Isenberg]

What is a typical hit rate that you can expect from a sound hash table implementation? I see only about a 10% hit rate in the opening / middlegames, but have read somewhere that 20% is supposed to be a normal hit rate. In the endgame Wing's hitrate very often goes up to > 30%. By hit rate I mean number of hash hits / number of hash probes.
Wing has two hash tables ('depth preferred' and 'replace always').
Stef.

I don't store/probe in qsearch - i use IID and ETC.
My table replaces depth+flags prefered - 8 consecutive interleaved and shared slots. Only one TT-table to avoid too much tlb-trashing.

In a position like
r1b1r1k1/ppq2p1p/3b2pQ/3pn3/8/2P4P/PPBN1PP1/R1B1R1K1 b - -
my program has ~27% hits including ~9% hash-cuts and exact scores.

Here after some seconds,
6k1/5p1p/P1pb1nq1/6p1/3P4/1BP2PP1/1P1Nb2P/R1B3K1 b - -
IsiChess has ~40% with about 13% cuts.

For Fine 70 it has about 80..70% and 35% cuts.

Gerd

[Scott Gasch]

I don't store/probe in qsearch - i use IID and ETC.
My table replaces depth+flags prefered - 8 consecutive interleaved and shared slots. Only one TT-table to avoid too much tlb-trashing.

In a position like
r1b1r1k1/ppq2p1p/3b2pQ/3pn3/8/2P4P/PPBN1PP1/R1B1R1K1 b - -
my program has ~27% hits including ~9% hash-cuts and exact scores.

Here after some seconds,
6k1/5p1p/P1pb1nq1/6p1/3P4/1BP2PP1/1P1Nb2P/R1B3K1 b - -
IsiChess has ~40% with about 13% cuts.

For Fine 70 it has about 80..70% and 35% cuts.

My program is much like Gerd's except I do not use ETC. My hash table is a 4 entry probe with a complicated replacement scheme. Here are my numbers in the same positions, FWIW:

1. 26% hits, 10% useful
2. 25% hits, 13% useful
3. 95% hits, 45% useful

Scott

[H.G.Muller]

I've just taken up chess programming after a pause of some 15 years, and at the moment I am playing a bit with the various concepts that in my previous life as a chess programmer didn't really exist, just to get a feel for what one can do with those. Hash tables is one such feauture, on the machine I wrote my first chess program for, the memory would not even fit a hash table that could handle a KPK end game...

What is the customary replacement policy for such hash tables? My first impulse was to jealously saveguard entries that were evaluated at large depth, and only in cases of equal depth go for the superior type (i.e. an exact evaluation over a limit, and for similar limits the sharpest one). The idea was that much effort had gone in calculating the deep result.

This led to very sick behavior in the KPK end game, though: on improving the search depth the node count slowly increased to several hundred- thousands, but then on going one ply deeper suddenly jumped to over a hundred million. (Which is pretty ridiculous if you realize that this end-game has only several thousand positions, and even including KQK it is only half a million.)

The problem seemed to be that the hash table locked itself into a state with all positions evaluated very deep, but with evaluations that were all upper or lower limits (which is what most evaluations are, if your alpha-beta works efficiently). As the window jumped to a completely different range (upon queening or mate comming within the horizon) these limits became completely useless, but since they were evaluated at large depth, they were never replaced. In essence, this completely turned off the hash table, so that it started to do a full recursive minimax search without any hashing (which of course was disastrously slow).

The problem went away when I made the type of the score the dominant criterion for replacement, i.e. always replace an entry for which the table value was merely a limit, even if the table entry had a very large evaluation depth and the currently calculated value almost none. Only if the table result is an exact score, I let the deepest evaluation prevail. The rationalization is that a low-depth result, although it is easy to (re)calculate, is visited an enormous number of times near the end-leaves of the trea, and so it is still very useful to have it in the table.

With that policy my benchmark KPK (W:Ke1,e2;B:Ke8) jumped to a search depth of 75 ply in a few seconds with black to move (returning all draw scores) while with white to move it stopped even earlier on finding a forced mate. The old replacement scheme already got in trouble on ply 18, or so, unless I forced the window completely open (-inf,inf) on every ply (so that only exact scores were generated, but at the expense of scoring many irrelevant positions).

Is there a generally accepted best way to do this? I can imagine fancy schemes keeping track of both upper and lower limits for every position, and the depth to which these are valid, but I wonder if it's worth it...

[Richard Pijl]

Simplest way to combine the storage of the 'most valuable' entries with the entries that will cause localized hits would be a multi-probe method.
Suppose do don't store just one record in a hashtable slot, but multiple. When you want to insert a new record, you'll replace the least valuable one (independent of the depth to which it was searched) with the new record. So a new record will always be stored in the hashtable. It's 'value' determines how long it will be in there though.
Richard.

[smcracraft]

What is a typical hit rate that you can expect from a sound hash table implementation? I see only about a 10% hit rate in the opening / middlegames, but have read somewhere that 20% is supposed to be a normal hit rate. In the endgame Wing's hitrate very often goes up to > 30%. By hit rate I mean number of hash hits / number of hash probes.
Wing has two hash tables ('depth preferred' and 'replace always').
Stef.

About 20%-35% for the main transposition hash table (single probe)
and 90%-99% for the pawn structure transposition has table (single probe)
(pawn structure evaluation is essentially nearly free.)

My %'s above were calculated with the hash hits / hash probes in both
cases.

Mine is a replace always as long as the depth being stored is >= the
depth that is being replaced.

Greetings,

Stuart

[diepeveen]

What is a typical hit rate that you can expect from a sound hash table implementation? I see only about a 10% hit rate in the opening / middlegames, but have read somewhere that 20% is supposed to be a normal hit rate. In the endgame Wing's hitrate very often goes up to > 30%. By hit rate I mean number of hash hits / number of hash probes.
Wing has two hash tables ('depth preferred' and 'replace always').
Stef.

openingsposition

11 ply :
Hash Q: perc=8.94 total cutoffs=381145 calls=4265281 stored=3880283
Hash M: perc=14.96 total cutoffs=254447 calls=1701388 stored=1456746
Eval : perc= 25.12 hash= 1237266 calls=4924884 from which m-e=0
Pawn : perc= 90.99 hash= 3355549 calls=3687618
Bishop: perc= 0.00 hash= 0 calls=0
Eval from hash: perc= 14.47 hash= 863432 calls=5966669
Eval from hash for q-null: perc= 16.03 hash= 224240 calls=1398652