Author: Tom Likens
Date: 10:58:17 04/19/04
Go up one level in this thread
On April 19, 2004 at 13:11:59, Andrew Wagner wrote: >Some have suggested this could possibly be a problem with how I store and >retrieve the bounds in my hash table, so let me explain what I do and see if the >logic is right. Much of it comes from Bruce Moreland's web site. > >My Search function calls a function called ProbeHash(). Probehash looks in the >Transposition table to see if the position has an entry stored there already. If >so, and the leaf distance of the hash entry is >= the current leaf distance, it >looks at the score and at what type of entry it is. If it's a beta entry (stored >when the move fails high), and the score is >=beta, Probehash returns beta. if >it's an alpha entry (stored after a fail high), and the score is <=alpha, alpha >is returned. If it's an exact score (the first time it was searched, the score >was between alpha and beta), the score itself is returned. If none of this is >true, it passes back a best move as a parameter. Once we arrive back at >Search(), if any of the above three cases with scores (alpha, beta, or the hash >entry score) were returned, Search immediately returns that score. Otherwise, it >continues on. > >I hope this makes sense. Does this sound correct to the rest of you? Dan, is >this similar to the logic of how you do it? Thanks! Andrew Andrew, In Djinn I do the following with the bounds (also note, Djinn uses a fail-soft search so it returns scores outside of alpha and beta during the search): 1. EXACT- If *all* the moves at a node are searched and the resultant score is between alpha and beta then the move, along with its draft (which is the depth of the search *below* this node), is saved and the bound set to EXACT. As you said, if we encounter this position again and the draft saved is greater than or equal to the current search draft then Djinn simply returns the score. If the draft is insufficient the hashed move is used for move ordering. 2. LOWER- If a move fails high the move (along with the draft) is stored in the table, along with a LOWER bound flag. This indicates that the true score for the position is at least this good, but it *may* be better. If we reach this position again and the stored score >= beta and the stored draft is large enough then simply fail high at this node and return (Djinn returns the hash score). As with an EXACT bound the move stored can be used for move ordering if the draft doesn't allow a cutoff. 3. UPPER- Here *all* moves get searched and the resultant score is less than or equal to alpha (i.e. the search fails low), which means that every move tried failed high at the next level down in the tree. In this case there is no move to store in the hash table (well, there are tricks but generally there is no move). If we encounter this position later in the search with a hashed score <= alpha (and sufficient draft) then simply return the score since we know it is an UPPER bound on the true score (i.e. the true score for the position can be equal but no larger than the value stored in the hash table). This sounds similiar to what you originally posted so we may be doing the same thing. Do you hash moves in the qsearch or only in the main search (Djinn does both)? Also are you using the stored hash move for move ordering? It's also important to ensure that the draft is being handled properly. Anyway, hopefully I haven't messed anything up or confused the issue even more. regards, --tom
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.