Author: Ulrich Tuerke
Date: 01:23:15 03/19/02
Go up one level in this thread
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, 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. 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. 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.