Author: Robert Hyatt
Date: 18:03:03 04/06/04
Go up one level in this thread
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...
>>
>>>
>>>>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.