Author: Robert Hyatt
Date: 15:50:22 01/22/98
Go up one level in this thread
On January 22, 1998 at 16:17:35, Stuart Cracraft wrote: >On January 22, 1998 at 15:29:39, Robert Hyatt wrote: > >>On January 22, 1998 at 13:50:10, Stuart Cracraft wrote: >> >>>On January 22, 1998 at 05:03:38, Ernst A. Heinz wrote: >>> >>>>On January 21, 1998 at 21:56:27, Robert Hyatt wrote: >>>> >>>>>On January 21, 1998 at 18:52:44, Heiko Mikala wrote: >>>>> >>>>>> >>>>>>On January 19, 1998 at 04:21:26, Ernst A. Heinz wrote: >>>>>> >>>>>>>On January 18, 1998 at 18:53:15, Bruce Moreland wrote: >>>>>>>>On January 18, 1998 at 10:37:59, Robert Hyatt wrote: >>>>>>>> >>>>>>>>>(...) The idea was to shift the null-move window downward, and >>>>>>>>>then notice whether the null-move search fails high or low. If it fails low, >>>>>>>>>(...) you extend by 1 ply. >>>> >>>>No, Bob, the idea as mentioned in Donninger's paper is different. Here >>>>is >>>>the reference for all who do not know the article. >>>> >>>>Donninger, C. (1993). >>>>Null move and deep search: Selective search heuristics for obtuse chess >>>>programs. ICCA Journal, Vol. 16, No. 3, pp. 137--143. >>>> >>>>Donninger's idea is to extend the search one ply if a null move near the >>>>horizon (e.g. at depths <= 3) does not fail high and the null move score >>>>plus a constant margin (e.g. minor piece value) is <= alpha while the >>>>static evaluation at the node is >= beta (i.e. fails high). In order to >>>>get meaningful results for the null move score, you need to do it with a >>>>full alpha-beta window instead of a zero window (this is a known error >>>>in >>>>Donninger's original article). >>>> >>>>Citing from my article about how "DarkThought" plays chess: >>>> >>>>In order to avoid possibly explosive growth of the search tree as caused >>>>by excessive deep search extensions in the case of repeated mutual >>>>mating threats, "DarkThought" restricts them to null moves at depth = 2 >>>>in the >>>>first "2 * iteration-number" plies on all paths. >>>> >>>>>>I tried Bruce's mate threat extension (everyone did, I guess...), and it >>>>>>works fine. >>>> >>>>I just gave it a quick shot but then put it on my to-do list because the >>>>quick implementation made our search trees *explode* ... :-( >>>> >>>>=Ernst= >>> >>>It made my search tree explode too. I will try putting in the Dark >>>Thought >>>limitations of depth = 2 and the first 2 * iteration-number plies. >>>Thanks >>>for the tip! >> >> >>the 2*iteration number won't be enough by itself for sure. You can find >>this limit in early versions of crafty sources when I was doing the >>threat >>extension. It helped, but not enough. however I didn't limit it to >>near >>the tips either, because it was also useful nearer to the root where it >>is just as profitable to extend when there is a threat. But it is also >>expensive... > >How did you get a score to use for this extension? The original article >advocates using the evaluation function at the interior tree nodes! > >I think this is far more expensive than the extension. > >--Stuart If you think about it, it isn't. Searching any kind of tree, even a very small one is going to be *far* more expensive, because any sub-tree you search is going to have endpoints that need evaluation as well. That will drown out the overhead of calling the evaluator at the internal nodes. Note that I only did the test *if* a move is being backed up as best, rather than if a node had all branches searched with no good score. This was rare enough to not make it expensive. But doing the threat-detection null move search had a cost, and then researching this single move with a deeper depth had a bigger cost.
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.