Author: Peter Fendrich
Date: 08:12:50 04/06/04
Go up one level in this thread
On April 06, 2004 at 08:15:53, Tord Romstad wrote: >On April 06, 2004 at 07:24:56, Peter Fendrich wrote: > >>On April 06, 2004 at 05:18:00, Tord Romstad wrote: >> >>>On April 05, 2004 at 18:58:57, Andrew Wagner wrote: >>> >>>>On April 05, 2004 at 18:42:57, rasjid chan wrote: >>>> >>>>>On April 05, 2004 at 15:59:40, Dann Corbit wrote: >>>>> >>>>>What fruits! I can't yet digest the apple. >>>>> >>>>>On a more serious note, it seems there MAY BE much more in hashing >>>>>than what I know - UB, LB, EX. I need time to see what all these mean. >>>> >>>>UB = Upper bound, LB = Lower bound, EX = exact. >>>> >>>>When you store a value in the hash table, sometimes it will not be exact, so you >>>>store some flag along with it that says what kind of position it is. If you just >>>>failed high, all you know is that the score is at least X. If if failed low, all >>>>you know is the score is at most X. And if the score is between alpha and beta, >>>>it's exact. >>> >>>Another option is to store _two_ values in the hash table entries, an >>>upper bound and a lower bound. You will probably also need to store two >>>depths, one for each bound. >>> >>>This is of course more expensive in terms of space, but it will also give >>>you a bigger number of hash table cutoffs. Whether it is worth the price >>>probably depends on the engine. In my engine, two bounds work much better. >>> >>>Tord >> >>This must be some kind of MTD thing. In PVS I don't see how it would help where >>almost every window is a null window but maybe I'm missing something... > >You are almost certainly right that using two bounds is much more advantageous >in MTD than in PVS, but as far as I can see it should help in PVS, too. I >don't understand why it is relevant that almost every window is a null window >(in an MTD search, of course, *all* windows are null windows). Yes you're right. The window size has not much to do with anything here but I'm still sceptical to it's usefulness in PVS! >This is how the code for hash table cutoffs look in my engine: > >/* 'he' is a pointer to a hash table entry. */ > > if(he != NULL) { > if(he->lower_depth >= depth && he->lower_generation == HashGeneration) { > if(lower_bound(he) >= gamma) return lower_bound(he); > } > if(he->upper_depth >= depth && he->upper_generation == HashGeneration) { > if(upper_bound(he) < gamma) return upper_bound(he); > } > } > >If my understanding of PVS and other traditional alpha beta variants is >anywhere near correct, the code would be very similar in a PVS search >(except that the first occurence of gamma would be replaced by beta, >and the second by alpha). Having two bounds should increase the >probability of a hash table cutoff. Agree, but most interesting is how often. It must be much more often in MTD. I just have presentiment of that the increased entry size wont pay off in PVS with that much more cut offs. >Under the (unrealistic) assumption that the number of hash table entries >is the same in both cases, a search with a two-bound hash table should >always consume fewer nodes than the same search with a one-bound hash table. >In practice, of course, the number of hash table entries will be lower >with two bounds, and it is hard to say whether one or two bounds is >optimal without testing. Yes, testing is the only way to know but arguing is part of the fun! In this case however I don't have much more than a feeling to base my arguments on. When the speed is x Knodes per seconds it's hard to have a complete picture of what's going on during the search. Most variants are really weird and would never occur in a normal persons brain... /Peter >It is perfectly possible that you are right, and that my understanding of >the complexities of PVS is still too limited to enable me to understand the >problem. I've only been a PVSer for two days, and my engine still doesn't >have hash tables. >Tord
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.