Author: Heiner Marxen
Date: 09:11:15 04/22/00
Go up one level in this thread
On April 22, 2000 at 10:35:23, Matt wrote: >Hi... > >I'm a relatively lousy programmer... I've written a very basic chess engine >(around 1950 on FICS) and I would like to work on adding hash tables to it, >however I haven't found any good references to how this is done... I know the >crafty source is available, but the crafty source scares me. What I am looking >for is a very general overview of how hash tables work. Basically, you try to have a cashe for the function "search(board, depth)". When search() is called with the same board and with the same depth again, you want to remeber the result, since you are going to do the exact same computation again. The remebered result avoids the second computation. [ A closer look shows, that the computation is not exactly the same, since sometimes path dependant information is used. For the hash table this is generally neglected, but it can make problems. ] >As I understand it, it works something like this: > >1. generate hash key for position > >2. check to see if that key is already in table. if it is, return the score >from the hash table (eliminating the entire subtree, as its already been >searched before). if not, continue search as normal. ... provided the stored depth is sufficient. 3. After having continued normally, and thus generated/computed a result worth to be found in the hash table... enter it into the hash table. >This is done from within your search function if I understand correctly... Yes. >I understand how to initially create and update the hash key on moves and >takebacks, but... > >When are positions ADDED to the hash table? See point 3 above. >is the depth of the search included with the position when its added? Yes. The depth of the search is a very important parameter to the search function. You would not want to retrive a 2-ply search result and use that as result of a 7-ply search. >I assume the hash table isnt cleared after every move, how does that affect the >search depth stored in the hash tables for positions found in previous searches? Not at all. That position _was_ searched with that depth, period. But you may want to install a generation counter scema, discussed recently in this forum, in order to detect entries which have a large depth, but are from a previous search, and thus can be overwritten by a new entry, even if that has much less depth. >I am told one does not search the hash table, it performs a 'lookup'. how does >this work? You already have a hash key (your point 1 above). It should be at least 32 bit, better more (most programmers seem to find 32 bit to be not enough). 48 or 64 bit will be sufficent. From this huge value we now want to compute a "hash index", i.e. which of the N entries in the hash table to use for this hash key. Generally you can do index = key % N. When N is a power of two this is a simple masking operation. >Any help would be most appreciated. please use small words, this is all new to >me :) Hopefully my words were small, and my sentences clear. Otherwise ask again, or read the many other explanations to appear here. Of course, my explanations above describe a very simple scema. Especially the strategy for searching and replacing slots in the table can be refined. But the most simple scema is not so bad. Heiner >Matt
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.