Author: Robert Hyatt
Date: 06:20:43 11/23/98
Go up one level in this thread
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 page took 0.01 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.