Author: Robert Hyatt
Date: 18:33:12 10/07/99
Go up one level in this thread
On October 07, 1999 at 18:42:35, William Bryant wrote: >Bob has said on may occasions that he puts the pv into the hash table before >each search to improve move ordering and efficiency. > >Trial and error has gotten me close to succeeding in this but a few questions. > >1. I stuff the PV at the start of each iteration. > Now, do you restuff it if a search fails high with a new root move? what to stuff? the PV from the previous iteration? You have no PV for the fail high. I wouldn't stuff anything, and hope that the hash table has good move ordering information already. The old PV is not any good, because the current iteration failed high, meaning that a new move (or moves) appears somewhere in the PV. The hash ought to have it already. > If it fails high with the original root move? See above. I mixed both cases. In the first case you have a new PV move, but no PV to stuff. IE your first move failed high because all the moves at ply=2 failed low. No move ordering information to go on. > If it fails low and you are going to research every move all over again? I have handled this two ways: (1) on a fail low I tried searching all the root moves with the same window to see if another one will pull the score back up into the window. If not, I relaxed alpha and tried them all again. (2) I now notice that the first root move was searched and the score is still alpha, so I immediately stop and lower the bound and search it again. This lets me quickly see how bad the fail low really is, so I know how much extra time I can allocate to find a better move. On a fail low, the hash ought to be your guide for the re-search already.. no stuffing needed. The only time I stuff the hash is at the end of an iteration, before starting the next, as it is very probable that part of the PV was overwritten by the searches that followed the PV move. > > By the time it has failed high or low, the hash table has been rearranged > a bit. > > >2. What values do you use for the hash table entry. > I have been placing each move in as follows: > flag == exact I check to see if there is already a hash entry in the table. If so, I just add in the PV move. If there isn't a matching entry, I fake one up but set the flag to WORTHLESS. > depth == 0 > score == pv score following the last iteration > bestmove == pv move. > > Note: we want the best move, but not to generate a premature cutoff so > I set depth to 0. This means, that the rest of the entry except the > bestmove will be not be used. > > Should I be using alpha instead? > >3. In the root search, I don't probe the hash table, so there is no bestmove. > I use the pv move in this case. > same here. I just force the root move list to have the previous PV move ordered first. >4. In the QSearch, where I don't probe the hash table, do you still check to see > if any of the captures are part of the pv, or simply sort them all in the > standard way? > I don't touch the hash in the q-search. but you ought to test with and without q-search hashing and make up your own mind. Initially (in crafty) I was hashing and I believe Bruce wasn't. Later He started hashing in the q-search and I stopped. :) It is basically a 'wash'. I don't do it because it helps the search when the hash table is not really large... since most of the nodes searched are at depth==0 and beyond, those don't cause overwriting when the table is too small. >I am concerned that I may have a few bugs, because I am not getting the >performance that I had by searching the pv move and then the hash table move. > >Thanks in advance. > >William >wbryant@ix.netcom.com
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.