Author: Steve Maughan
Date: 06:09:07 03/18/02
I've been pondering this for a while and would be interested in people's
opinions.
In Ernst Heinz's excellent book on Computer Chess Search he discusses the use of
hash tables. One point is that hash hits do not always result in a cut-off even
if the hash entry has a sufficient depth since the bound score may not be
sufficient. In this case it is suggested (page 21 of the book) to potentially
use the hash table values to raise the value of Alpha or lower the value of Beta
based upon the bound e.g.
if (HashRecord.Depth>=Depth) then
begin
if HashRecord.Bound=hbLower then
begin
if HashRecord.Value>=Beta then
begin
result:=HashRecord.Value;
exit;
end
else if HashRecord.Value>alpha then
begin
alpha:=HashRecord.Value;
end;
end
else if HashRecord.Bound=hbUpper then
begin
if HashRecord.Value<=Alpha then
begin
result:=HashRecord.Value;
exit;
end
else if HashRecord.Value<Beta then
begin
beta:=HashRecord.value;
end
else
begin
result:=HashRecord.Value;
exit;
end;
end;
The reasoning to adjust alpha or beta is that you should trust the scores from a
deeper search. Now I can see that this is true of alpha i.e. a deeper search
has proven that this prosition is worth a value greater than the current value
of alpha hence increase the value of alpha. However for Beta I don't follow
the logic, which I see as - a deeper seearch has proven that this position is
worth no more than Beta-x (e.g. may be *very* bad) so cut-off if a shallow
search thinks it OK (i.e. better than beta) - this doen't make sense!! Am I
missing something? Ernst Heinz is clearly do something else in addition - in
the book he says (page 22),
"Upon lowering beta, our implementation keeps track of the largest upper bound
(denoted by UPPER) that the search is allowed to return. It does so in the same
way as it keeps track of the best score. Eventual fail-high cuttoffs later
respect this upper bound by returning the minimum of UPPER and the best score so
far as their result. This works because the assertion "BETA<=UPPER" always
holds".
Hmmm, a little hard to follow but he seems to be tracking the maximum that is
below the original beta and returning the minimum of these?!?! Does anyone else
do this? I currently only increase Alpha in Monarch. Has anyone else got a
clearer explanation of what is going on?
Thanks,
Steve Maughan
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.