Author: Tony Werten
Date: 01:57:25 03/19/02
Go up one level in this thread
On March 19, 2002 at 04:23:15, Ulrich Tuerke wrote: >On March 19, 2002 at 02:52:12, Tony Werten wrote: > >>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. > >Hi Tony, Hi, >but I can't really see a problem with this. >In your example, the best move would mimic an exact value of 100 to the search. Yes,but it will return an upper bound on 100 ( wich gets returned to to previous ply as -100, wich is between -200 and 0 so there it will be an exact value.) In XiniX I don't store best move on upper bounds so I just lost the last 4 ply of my pv (I rebuild pv from HT). On the next iteration this will cost me nodes. Of course this is engine dependend, if I would use internal iterative deepening or would build pv's from a 2d array it would probably cost me less. >In case this move will become a part of the main variation, you'd even have the >chance to find a solution one iteration earlier thanks to the hash table. >I doubt that this behavior will raise any problems. Perhaps you'll have a few >nodes more in some cases, but the result of the search is qualitatively better >because you have looked to larger sub-trees (perhaps a similarity to >extensions. I don't think it will cause problems, but I don't think it will help either. (I probe in quiescence and there the score will be taken or searched deeper, I just don't want to do it in my main search) With my engine it's about equal (on longer searches), but then the ugly short pv's every now and then have the final say. Tony PS On short searches it saves about 5% > >c/u >Uli > > >> >>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.