Author: Robert Hyatt
Date: 08:32:35 03/18/02
Go up one level in this thread
On March 18, 2002 at 09:09:07, Steve Maughan wrote: >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. This is normal. It was mentioned by Greenblatt and then by Slate/Atkin in their chapter of Chess Skill in Man and Machine. It works just fine although using PVS this really doesn't happen very much since you can't raise alpha or lower beta _without_ getting a cutoff... > > 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 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.