Author: Peter Fendrich
Date: 14:53:43 04/06/04
Go up one level in this thread
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
>
>>
>>>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.