The idea is called semi-path dependent hashing or SPDH. The idea is to remove the bad effects of hashing when it comes to path dependent aspects of the search, such as repetitions and the 50 move rule, but still keep (most of) the benefits of the hash table.
What you do is to keep two hashkeys of the position at hand: The normal hashkey, based only on the position, and a path hashkey. The path hashkey can store any level of information you want, which is partly where the "semi" comes from. In my current implementation, I hash in the last 4 moves made. But theoretically you could hash every move in the whole game, as well as the fifty move counter, or maybe just the last move made. There is a whole continuum of possibilties, and my testing has only touched the surface.
So once you have these hashkeys, you must change the way you use the hashtable in order for them _both_ to be useful. You still store and probe based on the normal hashkey. Inside the hash entries, you keep part of the normal hashkey, and part of the path hashkey. If the normal hashkey matches the current position, you have a valid move that you can use for move ordering. Then, if the path hashkey matches as well, the score is safe to use, even for lines with repetitions and such.
It's pretty simple. I've never even heard of anyone using path information in their hashkey, so it's quite novel. The problem is, is that in my testing, with the parameters used, it slightly reduces strength. It is surprising to me though, that it doesn't dramatically reduce the search efficiency, even in the endgame. So with enough tuning, maybe the idea will be useful to someone.
I bring it up also because it elegantly solves the problem that Bob brought up. When the fifty move counter gets close to fifty, he runs through the hash table and invalidates old entries. Here's a better way to do this:
Code: Select all
if (fifty_count < 80) /* I.e. less than 40 reversible moves */
path_hashkey = hashkey; /* No change, we can just accept cutoffs regardless of path */
else
path_hashkey = hashkey ^ some_constant; /* If we are getting close to 50, then only accept cutoffs from newer searches, BUT, still use the hash move */
Code: Select all
path_hashkey = hashkey ^ some_constant[fifty_count - 80];Does that sound interesting to anyone? I was pretty disappointed that it didn't at least help...
