Author: Vincent Diepeveen
Date: 00:18:22 11/24/98
Go up one level in this thread
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.. This is both theoretical and practical not exactly the truth. You're searching 35 moves times 1/36 = 35/36 Your tree *at least grows 2 times. Your branching factor simply gets worse with 35/36. Which is WORSE than getting an overhead of 35/36. However i'm simply searching many many plies less deeply. Hard to get more than 10 ply with correct working S.E.
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.