Author: James Robertson
Date: 21:49:05 01/03/99
Go up one level in this thread
On January 04, 1999 at 00:01:05, Robert Hyatt wrote: >On January 03, 1999 at 21:54:13, James Robertson wrote: > >>On January 03, 1999 at 20:32:56, Robert Hyatt wrote: >> >>>On January 03, 1999 at 18:44:15, James Robertson wrote: >>> >>>>I am trying to put hash tables into my program, but am completely unsure of how >>>>to start. Can anyone explain in GREAT DETAL (I am kind of stupid) how to do >>>>this? Also, maybe where to look for info too. Stuff like "Look in the Crafty >>>>code" does not help, as I have no idea what to look for. >>>> >>>>Thanks! >>>>James >>> >>> >>>This is a real difficult question for a short answer, but here goes: >>> >>>first a few definitions: >>> >>>draft: the depth below this position that the search reached. IE if we >>>are at ply=4, doing a 7 ply search, then the draft at ply=4 is 3, as the >>>search went 3 plies beyond the current ply. >>> >>>best move: the best move at the current position. If we are backing up a >>>real score, the best move for the current ply is in pv[ply][ply]. If this is >>>a fail-high case, then the current move we tried at this ply is the "best >>>move". >>> >>>alpha: lower search bound for this position. >>> >>>beta: upper search bound for this position. >>> >>>OK, on to the explanation. First, when you search at a ply in the tree, >>>there are only three (3) possible outcomes: >>> >>>(1) you search every move at this ply, and when you finish, best_score is >>>> alpha, and < beta, which means this is a true or EXACT score for this >>>position. You back up this score to the previous ply. >>> >>>(2) you search every move at this ply, and when you finish, best_score is >>>still equal to alpha. This means every move was tried but refuted by the >>>move at the next ply. This is a "fail-low" move as every move leads to a >>>position <= alpha. >>> >>>(3) you search one (or more) moves at this ply, and when you get the result >>>back, it is >= beta. There is no need to search further, you simply return >>>beta to the previous ply and quit at this ply. We call this a "fail-high" >>>ply. >>> >>>Now, in the context of hashing, let's handle all three cases above. (1) you >>>simply store "best_score" and a flag EXACT; (2) you store alpha, and UPPER >>>(we know that the score is <= alpha, but we aren't sure how much below. So >>>"alpha" represents the 'upper bound' for the score at this position, as it >>>could be much lower); (3) you store beta, and LOWER (we know the score is >>>>= beta, but it could be much greater, so beta is a lower bound on how good >>>the score is. >>> >>>At the front of search, we do a hash probe, and if we hit, we first look at >>>the draft of the table entry and compare it to the remaining depth we need to >>>search. Assume we are at ply=4, with a 7 ply search, so we need to search 3 >>>more plies. If our "draft" for this position is at _least_ 3, then we can use >>>this table entry to try and avoid further searching. Let's assume this is ok. >>> >>>Now we have three cases. If the flag is EXACT, we just return the score from >>>the hash table and search no further. If the flag is LOWER, we simply compare >>>the table bound to beta, and if it is >= beta, we return beta with no further >>>searching (we just failed high here with no searching). If the flag is UPPER, >>>we compare the table value to alpha, and if it is <= alpha, we return alpha >>>with no further searching (we just failed low here with no searching). >>> >>>that's a quick description. Feel free to ask questions... It is not hard to >>>write, but it can certainly play havoc when you get it wrong... >>> >>>more details can be found in crafty's source, module "hash.c" >>> >>>Bob >> >>Ok... that makes sense. Thanks for the great explanation. Now, the part I have >>difficulty with is the implementation. I understand the table of random 64 bit >>integers and how we xor them to end up with the hash key. What I don't >>understand is how we take a 64 bit hash key and search in a table with some >>portion of that key and then compare the whole key later. Also, the Zobrist >>algorithm; how does that work? Thanks for any more help you can give me! >> >>James > >Zobrist is what you described (the xor'ing of random integers). > >In a hash entry you generally store the following: > >type (EXACT, LOWER, UPPER, WORTHLESS) > >draft (depth in plies below this position that the search reached) > >best move > >lock (could be entire 64 bit hash signature or only a part of it) > >other things you might want to add later such as threat flags, an "age" >field so you don't have to clear the hash table, and so forth. > >If you make your table a power of two, you take the rightmost N bits of >the hash signature and that gives you a table index. Go to that position >and compare your hash signature to the "lock signature" stored there. If >they match, the position is a match. If they don't, throw up your hands and >search normally and consider this a "hash miss." You can do a two-level >table as many of us do, where you have two tables and probe into both at the >same time to see if either of the two positions match. > >Most any good data structure book covers this sort of idea, but remember to >not get carried away and to keep it quick... Er..... this makes sense, but I have yet to see if I can translate it into C++. How do programs who do not make their tables a power of 2 work? If the lock is only part of the 64 bit hash key, the remaining bits are the table index? I'll keep posting questions as I think of them!! Thanks! James
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.