by **H.G.Muller** » 09 Dec 2005, 12:33

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...