Author: Tord Romstad
Date: 05:15:53 04/06/04
Go up one level in this thread
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).
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.
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.
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.01 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.