Author: Robert Hyatt
Date: 06:43:53 11/10/03
Go up one level in this thread
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. I suppose I am lost here in the discussion. Which, I thought, was about best-first (breadth-first) algorithms compared to depth-first algorithms. They _never_ search the same tree. In the case of mtd(f) it is more pronounced in that many nodes get searched at _least_ twice and in reality, more than that, as two searches at a specific depth is the theoretical min for mtd(f)... Did I miss something significant in the previous discussions here? As I have said repeatedly, breadth-first and depth-first are _not_ equivalent in any way other than for the (possibly) final result each produces. Appendix B is about the equivalence of SSS* and MT-SSS*, which is an algorithm change to eliminate a problem with parallel handling of a single "open" list.
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.