Author: Robert Hyatt
Date: 05:10:02 11/24/98
Go up one level in this thread
On November 24, 1998 at 03:02:51, David Blackman wrote: >On November 23, 1998 at 09:20:43, Robert Hyatt wrote: > > >>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.. > >Are you sure about that? Given that you're still using alpha-beta i'd have >thought the cost of checking the extra moves was about >w * w^((D-2)/2) >compared to finding the initial fail high at >w^(D/2) Your math is correct (and is also given in the deep thought extension paper in the JICCA). I simplified it significantly by only discussing what happens at one node normally you would search 2*W^((D-1)/2) (for D even, of course, it changes for D odd) at a node where you fail high. now you would search those nodes *plus* (W-1)*2*W^((D-3)/2) "extra" nodes. (again that is wrong for D odd but it is close enough). IE the overhead here is still a fraction of the total tree size, which is not bad... What ever node count you search, you can count on roughly 1/W^2 extra nodes because you only do this on fail high nodes, not fail low... >ie, about the same. >Although i could be missing something due to failing high and failing low having >different costs. > >Certainly, when i attempted singular-move extensions a few years back i found >that detecting singular moves was often more expensive than doing the extension. > >However i only did a one-ply extension. I think Deep Blue does a 2 ply extension >in most cases. No... you can't do that and their paper is quite careful to mention that they can do up to 2 plies of extension (SE=1) for every two plies of search, so that they don't exceed an average of 1 extension per ply. > >I briefly considered always doing the extension, without checking if it was >singular, but then i decided that was silly. > >I guess you could reduce the cost of detecting singular moves a bit by cutting 3 >or more plies off the depth, instead of just 2. > >I think i tried that at one stage. It's nice for tactical problem sets, but not >clear if it actually helps in real games. The more you cut, the more errors you make. Because you don't see why the move "is or isn't" singular any more..
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.