Author: Robert Hyatt
Date: 21:01:05 01/03/99
Go up one level in this thread
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...
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.