Author: Dave Gomboc
Date: 00:02:59 11/10/03
Go up one level in this thread
On November 10, 2003 at 03:01:27, Dave Gomboc wrote: >On November 09, 2003 at 20:36:08, Robert Hyatt wrote: > >>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... > >Appendix B of Aske Plaat's Ph.D. thesis contains specific details demonstrating >that SSS and mtd(oo) "evaluate the same leaf nodes in the same order when called >upon the same minimax tree". Reference #106 from that thesis is a technical >report that contains the formal proof. > >Dave The thesis is available here: http://www.cs.ualberta.ca/~jonathan/Grad/plaat.phd.ps Dave
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.