Author: Scott Gasch
Date: 22:18:37 01/17/02
Go up one level in this thread
On January 17, 2002 at 23:25:47, Sean Mintz wrote: >Can someone give me a little how-to on making hash tables w/ the 0x88 board >representation? I use two boards (color,piece) if that makes much difference. > A hash table implementation doesn't depend much on the style of board representation you use. The first step towards making a hash table is to be able to generate a hash key from a board position. That usually means having a signature for board positions. You want the signature to change based on all aspects of the position (where the pieces are, whose move it is, who can castle how, where en passant can happen etc...). Most people use a 64 bit position signature as it has been found that a 32 bit signatures are not long enough. You can generate a signature every time you need one (slow) or you can generate it once and keep it incrementally as aspects of the signature change. For example, if your signature is based on the locations of pieces on the board and a piece moves, change the signature for that one moved piece. Search for webpages about Zorbist hashing for more info about this. Once you have a way of generating a hash key for a position (some subset of that position's signature, usually) you can store data about a position in a memory table. The typical data stored about a position is: score, depth, bound type, and best move. You'll want to store data in this table when you are done searching a node and query the table before you start searching a node. This way if you have already searched a position to depth d and, later on, you need to search it to depth 1..d again you can simply lookup the result of the depth d search in the hash table and spend your search time elsewhere in the tree. Also note another advantage of hashing is on move ordering. If, when you enter a node, you find that the position is in the hash but the depth it was searched to in the hash is not sufficient to allow you to skip researching it, you still have valuable information. You know the best move you found the last time you searched that position. You should try that best move first when you are researching with greater depth. Scott
This page took 0 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.