Author: Tony Werten
Date: 23:52:12 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. > > 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? My impression based on my program was that it saves in short searches, but costs nodes in longer searches. Suppose we are searching with a window (0,200). Hash table suggests score >=100. Raise alfa and searching with (100,200) will save you nodes. Now imagine you are doing a very long search. It now happens more often that the hashtable entry is fe with a remaining depth of 5, but there is only 4 ply left. You raise alfa again, but the bestmove that gives a score of >=100 with 5 ply left, might return a 50 score when only searched with 4 ply. This means your bestmove will "fail low", and not get recorded as bestmove. This will cost nodes because your move ordering got worse, or it might even cutoff your pv after 1 or 2 ply (specially when you rebuild it from hashtable). Tony > >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.