Author: John Coffey
Date: 10:48:58 09/21/98
I haven't seen very much on the net that describes an efficient hash algorithm. My first thought was that I would hash the entire board, but I am guessing that it is slow to create. Then it occured to me that I could hash just the moves made (somehow) so that if someone played Nf3, Nc6, Nc3, Nf6 in any move order I would get the same hash key. The only problem with this is that in some endgame positions you could get pieces on the same squares by many different moves. So then it occurs to me to hash each piece on each square ... I start with a hash value for the whole board and then as each piece moves then I subtract the hash value for a piece moving off of that sqaure and then I add the hash value for the piece moving to the new square. This would give me a whole-board hash that is dynamically updated. I assume that hash values will use exclusive-or's to combine them? Then there is the problem of multiple positions ending up with the same hash key. I am not sure what to do about this yet. Do I have to store the entire board position and compare that to make sure I haven't got some other position? If I end up with duplicate keys then do I erase the old position and fill it in with the new, or do I keep both positions? Do I keep positions that were found 2 to 3 moves ago? (After some real moves have been made on the board.) What do I do when the hash table starts to get full? I assume that BSP trees would be slower than hashing. How much space does each hash position usually take? John Coffey
This page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.