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