Author: Robert Hyatt
Date: 17:36:08 11/09/03
Go up one level in this thread
On November 09, 2003 at 12:01:25, Dave Gomboc wrote: >On November 08, 2003 at 11:09:35, Robert Hyatt wrote: > >>On November 07, 2003 at 14:14:58, Dave Gomboc wrote: >> >>>On November 07, 2003 at 14:14:08, Dave Gomboc wrote: >>> >>>>On November 06, 2003 at 22:31:49, Robert Hyatt wrote: >>>> >>>>>On November 06, 2003 at 20:43:58, Dave Gomboc wrote: >>>>> >>>>>>On November 06, 2003 at 19:46:29, Robert Hyatt wrote: >>>>>> >>>>>>>On November 06, 2003 at 11:22:54, Dave Gomboc wrote: >>>>>>> >>>>>>>>On November 06, 2003 at 09:47:32, Robert Hyatt wrote: >>>>>>>> >>>>>>>>>On November 06, 2003 at 08:33:49, Gian-Carlo Pascutto wrote: >>>>>>>>> >>>>>>>>>>On November 06, 2003 at 05:45:53, Renze Steenhuisen wrote: >>>>>>>>>> >>>>>>>>>>>Depth-First Algorithms: >>>>>>>>>>> AlphaBeta (Fail-hard, Fail-Soft) >>>>>>>>>>> MTD(f) >>>>>>>>>>> >>>>>>>>>>>Best-First Algorithms: >>>>>>>>>>> SSS* >>>>>>>>>> >>>>>>>>>>The distinction between the three (and best-first and depth-first) >>>>>>>>>>is very hazy, read "Research re: search and research" by Aske Plaat. >>>>>>>>>> >>>>>>>>>>-- >>>>>>>>>>GCP >>>>>>>>> >>>>>>>>> >>>>>>>>>Eh? The distinction is _huge_. >>>>>>>>> >>>>>>>>>One searches the tree in one direction and requires very little memory. The >>>>>>>>>other searches the tree in another direction and requires huge memory. >>>>>>>>> >>>>>>>>>I'm not sure how you could say that the distinction is very hazy. They >>>>>>>>>are as different as night and day... >>>>>>>> >>>>>>>>However, MTD(infinity) is equivalent to (searches exactly the same tree as) SSS. >>>>>>> >>>>>>> >>>>>>>That's fine. A best-first (breadth-first) search can search _exactly_ >>>>>>>the same tree as a minimax (depth-first) search also. Doesn't mean a >>>>>>>thing about how similar the two approaches are, however... >>>>>>> >>>>>>>However, the trees are grown differently. I don't think any book I >>>>>>>know of uses the actual search space as a way to define a search >>>>>>>strategy... >>>>>>> >>>>>>> >>>>>>>> >>>>>>>>http://www.cs.ualberta.ca/~jonathan/Grad/plaat.phd.ps >>>>>>>> >>>>>>>>Dave >>>>>> >>>>>>Fine, but the point is that in this particular case, they are not as different >>>>>>as night and day. :-) >>>>>> >>>>>>Dave >>>>> >>>>>They are different in the base algorithm. They are different in their >>>>>memory requirements. They are different in the order in which they search >>>>>the tree. They are different in how hashing may (or may not) work. >>>> >>>>They are *NOT* different in the order in which they search the tree. The >>>>traversal order is identical. >>> >>>More accurately, the node expansion order is identical. >>> >>>DAve >> >> >>Which specific depth-first vs breadth-first algorithms are you comparing >>when you make that statement? > >The ones GCP mentioned: mtd(oo) and SSS. mtd(-oo) and DUAL also have identical >node expansion order. > >Dave Yes, but _only_ in bizarre cases. mtd(f) searches the same basic tree multiple times to hone in on the score. At least two searches are required, at an absolute minimum. Generally it requires more. Also it beats me how _any_ best-first algorithm could search the same tree as any depth-first algorithm, except for pathological cases...
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.