Author: Robert Hyatt
Date: 16:55:42 11/23/98
Go up one level in this thread
On November 23, 1998 at 17:33:28, jonathan Baxter wrote: >On November 23, 1998 at 09:20:43, Robert Hyatt wrote: > >>On November 22, 1998 at 20:02:22, jonathan Baxter wrote: >> >>>On November 22, 1998 at 19:36:30, Robert Hyatt wrote: >>> >>>>On November 22, 1998 at 18:04:04, jonathan Baxter wrote: >>>> >>>>>Can anyone send me an electronic version of the ICCA article by Hsu on >>>>>Singular Extensions used in DB? >>>>> >>>>>Failing that, can someone give me a quick explanation? I understand >>>>>that they extend moves that look substantially better than all other moves >>>>>at a node. What I don't understand is that given the nature of alpha-beta >>>>>search, often you don't know anything about the value of alternative moves.... >>>>> >>>>>Thanks, >>>>> >>>>>Jon >>>> >>>> >>>>briefly: >>>> >>>>pv-singular move: you search the first move at a node with the normal >>>>window, and the remainder of the moves at that depty with a lowered (offset) >>>>window (alpha-w, beta-w) where w is the singular margin. If all those moves >>>>fail low, the first move is "singular" since it is clearly better. If any >>>>one move fails high, you have to do the original test on the first move to >>>>see if this new best is singular or not... messy but understandable. >>>> >>>>fh-singular move: you search the first move at a node with the normal >>>>window and get a fail high. You first search the *remainder* of the moves >>>>with the offset window, but to reduced depth (say D-2) to see if all of them >>>>still fail low with the offset window. If so, extend. If not, do the same >>>>check as in pv-singular. >>>> >>>>The idea is that at a PV or fail-high node, you try to prove that the best >>>>move is better than all other moves at that ply, by a significant margin. No >>>>"fail-low" node test has been formulated... >>>> >>>>If that isn't clear, feel free to ask more... >>>> >>> >>>It is clear enough, thanks. But doesn't this cost hugely? Searching all >>>remaining nodes at a fail-high node??? >>> >>>Jon >>>>Bob >> >> >>It's not as bad as it sounds, because remember that I said to search the *other* >>moves to D-2. If the fail high search costs you X nodes, then the extra tests >>on the moves you would normally look at will only cost you w/w^(D=2) nodes >>which lets you constrain the cost quite a bit. It certainly isn't free, but >>it doesn't double the size of the tree or anything close to that... >> >>ie if your normal branching factor (W) is 36, then the tree will grow by a >>factor of about 1/36... not too bad.. > > >So now the obvious question: If its so cheap and seems to work so well (at least >in the case of DB) , why aren't we all doing it? > >Jon It's not as cheap as it sounds... Don't forget that when it "triggers" it takes you one ply deeper. It's just another extension. My experience with it was bad in the days when I was doing 100-200K nodes per second with Cray Blitz. In 1993 I added this because we were going significantly faster and thought that our "10 ply" search was deep enough and we thought that we (Gower, Nelson and myself) would rather look down "interesting" lines deeper. It will lower your overall search depth by a ply or so. IE if you normally search to depth=11, you can count on depth=10. But in theory, you look down more interesting lines deeper. It particularly helps with "horizon" moves where you spite-check to push something away...
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.