Author: Robert Hyatt
Date: 07:20:51 01/04/99
Go up one level in this thread
On January 04, 1999 at 00:49:05, James Robertson wrote: >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 is easy. If you use a size=power_of_two, then you simply compute a mask with log2(hash_size) bits set and do "index=HashSignature&probe_mask; if you use a non-power-of-two hash size, just do "index=HashSignature%hash_size;" the modulus function will divide by hash_size and return the _remainder_ which is guaranteed to be an integer between 0 and hash_size-1, which is exactly what you want for a probe index. This is an integer divide operation that is slower than the simple boolean AND operation in the first case, but on newer micro- processors, it isn't necessarily terribly slow.
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.