Author: Peter Fendrich
Date: 09:06:02 04/07/04
Go up one level in this thread
On April 06, 2004 at 21:03:03, Robert Hyatt wrote: >On April 06, 2004 at 17:53:43, Peter Fendrich wrote: > >>On April 06, 2004 at 14:33:58, Robert Hyatt wrote: >> >>>On April 06, 2004 at 11:12:50, Peter Fendrich wrote: >>> >>>>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! >>> >>> >>>What you should do is every time you do a hash probe and the bound is useless, >>>ask the question "if this is a lower bound of X and I cant use it, what if it >>>were an upper bound X-1, would it help? vice-versa as well" If the answer is >>>yes, increment a counter. If that happens a lot, then the second TT bound might >>>help. and it would be worth considering. >> >>I'm not sure this will help. >>If I understand you right X is the probed value from the hash table. >>If so X-1 would almost always help as an upper bound: >>. >>. >>if (bound == LOWER && X >= Beta) { >> Return_eval = X; >> return(FH); >>} else if (bound == UPPER && X <= Alfa) { >> Return_eval = x; >> return(FL); >>} else... >>. >>. >> >>Here if bound == LOWER and X < Beta, X-1 will quite certainly fulfil the second >>test pretending it's an UPPER. Based on the fact that null windows are in vast >>majority. >> >>/Peter >> > >All I suggested was _counting_ how many times the extra table bound might help, >if it were present. It turns out that even on collision errors, the depth >(draft) is often not good enough to be used and the collision doesn't hurt a >thing... > >But here, I was just suggesting a way to estimate how frequently a second bound >might help with a PVS search... Yes, that's what I thought but my point is that the counter will be very high due to the null window and that wont tell me very much will it? Maybe I missed something? /Peter > > >>> >>>> >>>>>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.