Author: James Robertson
Date: 18:54:13 01/03/99
Go up one level in this thread
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
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.