How fast does your hash table fill up?

[Tommy]

I'm working on a new chess program which will feature a transposition table. It is my first time I have programmed transpositions tables and I have been unsure of what sort of performance I should expect from using them. I'm only at the stage of having written the move generation part of the chess engine so all my testing has been perft tests. The good news is my perft results are accurate with the use of transposition tables and I also get a speed boost of around 3-4 times with transposition tables compared with not using them. During my testing I found the transposition table did not fill as fast as I thought it would, so I'm wondering what is normal? Here are my results which shows the percentage of how full the table is...

Code: Select all

Fen=rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Depth= 1 Nodes=           20 NPS=   272,208 Hash=238.419%e-7%
Depth= 2 Nodes=          400 NPS=   962,890 Hash=500.679%e-6%
Depth= 3 Nodes=        8,902 NPS= 1,083,147 Hash=  0.010%
Depth= 4 Nodes=      197,281 NPS= 1,304,051 Hash=  0.191%
Depth= 5 Nodes=    4,865,609 NPS= 2,101,897 Hash=  2.585%
Depth= 6 Nodes=  119,060,324 NPS= 3,697,046 Hash= 27.708%
Depth= 7 Nodes=3,195,901,860 NPS= 4,138,088 Hash= 97.599%

Note: These results are based on a transposition table of 4,194,303 slots. Each hash record contains HashKey, Nodes, Depth.

Does this look right? Or am I doing something wrong?

Thanks,
Tom.

[hgm]

howdou you define filling fraction? How do you handle collissions? Do you overwite entries? Do you rehash?

To get the 7-py result you only visit and hash d=6 positions. There are 119M of thos, but due to transpositions only ~ 10M of those are different. This means tht the table is only overloaded by a factor 2.5. If you would do pure always-replace, the fraction of entries that was never hit would be exp(-2.5) = 8%. You see only ~3%, so you probably rehash colliding entries in places that otherwise would stay empty.

[jesper_nielsen]

I have seen at least three different approaches to hash tables.

1. Only store values returned from alpha-beta with depth at least one. Ie. exclude leaf nodes.

2. Store values returned from alpha-beta with any depth. Ie. include leaf nodes.

3. Store all values returned by alpha-beta plus all values returned from q-search.

The choice of approach will seriously affect the fill rate.

I started with 1 but switched to 2, because a test shoved it to help my engine.

1 will have a much slower fill rate than 2
2 will have a much(?) slower fill rate than 3 - havent tried this.

I guess that approach number 2 is the most common?!

[hgm]

I use (3), because both in Joker and microMax there isn't a distinction between QS and main search. I tried (1) in Joker, and it gave a significant slow-down.

But I use a replacement algorithm that is very resistent to extreme overloading of the table. Not-so-good replacement policies would of course tip the balance in favor of (1), as you could avoid overloading much longer.