Author: Dave Gomboc
Date: 08:35:17 11/10/03
Go up one level in this thread
On November 10, 2003 at 09:43:53, Robert Hyatt wrote: >On November 10, 2003 at 03:02:59, Dave Gomboc wrote: > >>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 > >OK... Here is the quote everyone is misinterpreting: > >"MT-SSS* and SSS* are equivalent in the sense that they evaluate the same >leaf nodes in the same order, when called on the same minimax tree." > >No quibbles with that. But what does that have to do with the >mtd(f) algorithm? SSS* is _clearly_ a best-first algorithm. >mtd(f) is _not_. They do not under any circumstances search the >same tree except for the case where each side has only one move >when on move, until the game ends. mtd(oo) (what he called MT-SSS*) is a depth-first algorithm. SSS* is a best-first algorithm. These two algorithms "evaluate the same leaf nodes in the same order, when called on the same minimax tree". This is the whole point that is interesting -- that these two search methods which would at first seem unrelated are actually highly related. Dave
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.