Author: Robert Hyatt
Date: 08:08:41 11/08/03
Go up one level in this thread
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. > >Dave Sorry but that is _wrong_. It might be true for _one_ example. But the topic was the two classes of search, best-first and breadth-first. They do _not_ in general, search the trees in the same order. By their very definition. Otherwise there would be no breadth-first or depth-first discussions in search theory.
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.