Convekta Logo
Chess Software Sourcebook
Join Chess Reviews<>
Convekta Logo
[Image]
 
Hash - how much is enough?
keywords: hash tables, CPU, endgame, middlegame, opening
Robert Pawlak
Wednesday, April 09, 2003
Hash tables provide a way for the chess engine to store the results of intermediate calculations for later use. The larger the hash tables, the more results can be saved in them.

Setting the appropriate hash table size for your chess engine should be a relatively simple matter, right?  Well, as it turns out, the optimum hash table size depends on the position. In this article, I will take a look at some test results that show some interesting phenomena. The machine used to run these tests was an Athlon XP 2400+ with 166Mhz front side bus speed, 12X bus multiplier, and 7-3-3 2.5 CAS latency DRAM.

Most of us operate under the assumption that bigger hash tables are always better. While this is not always the case, it is a good general rule to follow. But, it is not too difficult to find instances where a smaller hash table size can mean better performance out of an engine, as this article will show.

Three different positions were examined during tests with the default CA engine (Tiger 15). The first position was simply the initial position on the chessboard when a game starts. Shown below is a plot of time to reach a certain ply depth as a function of the hash table size. We can see that for all depths, increasing the hash table size seems to increase performance by only a very small amount. If you were to take the slope of the curves shown on this plot, you would see that you get about a 1% increase in performance for every doubling of the hash tables.

Starting position (no book)
[Starting position]


Note that for a depth of 16, using 24M of hash will actually slow the engine down somewhat. This is contrary to what will be shown in subsequent plots.

The second position is an example of a typical middlegame position where there are a fair number of transpositional possibilities. Here we see that doubling the hash table size results in about a 10% increase in performance (on the average), across the various ply depths. We also see that there appears to be a "sweet spot" at around 24Mb of hash. This behavior is also evident in our next set of results as well.

rnbq2k1/p1r2p1p/1p1p1Pp1/1BpPn1N1/P7/2P5/6PP/R1B1QRK1 w - -
[rnbq2k1/p1r2p1p/1p1p1Pp1/1BpPn1N1/P7/2P5/6PP/R1B1QRK1 w - -]

Below we see the effect of hash table size on the endgame. Now, the increase in performance is about 20% (i.e. it takes about 20% less time to reach an equivalent depth with each doubling of hash table size). Also note the appearance of the 24M sweet spot here as well. It's also interesting to note that we see even greater increases in performance at the higher depths. This is not a big surprise, since we would expect this in the endgame (which is rich in transpositional possibilities).

8/5k2/3K4/3P4/8/8/2R5/3r4 b - -
[8/5k2/3K4/3P4/8/8/2R5/3r4 b - -]


In all the cases that were examined, there was only a small penalty for using large hash tables (i.e. a decreasing number of nodes per second processed), and there appears to be no one point where hash table usage is most efficient 100% of the time. Note also that in some of the tables, there are multiple depths listed. This is a characteristic of negascout algorithms, sometimes they search again at the same depth.

One conclusion that can be drawn from this data, is that doubling the hash table size decreases the time to reach a certain analysis depth by about 10% for some middlegame positions. At higher depths, there is an even greater benefit, while at lower depths, there is not as much. For endgame positions, there is about a 20% speedup in time to reach a certain depth. Thus we see a practical illustration of  larger hash tables being more important in the endgame.  

Surely it would be nice to extend this analysis with additional machines and positions, but these results should get you thinking about the subject. Note that extrapolating these results to other engines would probably not be a wise thing to do. Rather, these results provide graphical confirmation of the effect of hash table sizing for one engine, with a particular subset of positions.







ChessAssistant is a trademark of ChessOK
Syndication available through rss.xml
Click on my name to send me e-mail (must have javascript on)