Author: Pat King
Date: 08:41:59 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? I haven't read Ernst's book, but as I see it, if H.Beta < Beta, then you've proved you CAN'T get a cutoff. If you're doing AB with greater than a min window, then perhaps it makes sense to "lower the bar" by adjusting Beta. If you're in a min window search, as in MTD or PVS outside the PV, then it seems you should stop the search and return H.Beta. That is how I handle things with Zotron (not that it should be held up as an example to anyone ;)). >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 You're Welcome. Pat King
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.