Author: Matt
Date: 00:16:14 04/23/00
Go up one level in this thread
I appreciate the help! I found your explanation most helpful. As always though, your explanation generates even more questions! On April 22, 2000 at 12:11:15, Heiner Marxen wrote: >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. Am I correct in saying that it is not necesssary to have this generation counter schema? hash tables will work without this modification? This is my first attempt at doing hash tables, I want to keep it as simple as possible ;) >>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. I was planning on using a 64 bit hash key for now.... I was going to use position, en passant, and castling permissions to generate the key, and leave out the 50 move and 3 move rep info for now. This should be enough to make them functional, right? I think this next part is the part I am getting hung up on. Please let me know if this is incorrect. if we are searcing for this position in the hash table, we do key_of_current_position%N and find where the position WOULD be stored if it is there. the % function will return a number 0 to N-1, which represents the various 'slots' for a hash table entry. Then we compare the hash key in the table with the one for the current position. if the keys are the same, it is almost certainly the same position. We check the depth of the info in the hash table, and if it is >= to the current search depth, return the score from the hash table. if the keys are different, then there is a key for another position residing in the same spot as the key for this position would be. So even though theres a stored position here, it is a different position. we continue with a regular search then overwrite the info in the hash table with the info for the position we just searched. That brings up another question... If we find the wrong position in our hash table, do we ALWAYS overwrite it? Also, is there any case in which the hash table SHOULD be cleared? And finally, when somebody mentions a hash table collision, are they referring to a case where two positions have the same hash key? Also, if thats the case, how does one detect this? Ok I lied, one more question. Do we store these hash entries regardless of search depth? ie do we store them at depth 0? >>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. I'm looking for the most simple right now. Once i get a handle on that, I can start breaking it with "improvements" ;) >Heiner > >>Matt Thanks again for all the help
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.