Author: Robert Hyatt
Date: 09:59:07 11/10/03
Go up one level in this thread
On November 10, 2003 at 11:39:07, Dave Gomboc wrote: >On November 10, 2003 at 11:35:58, Dave Gomboc wrote: > >>On November 08, 2003 at 11:08:41, Robert Hyatt 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. >>>> >>>>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. >> >>No, the topic was not about best-first and depth-first, it was about the >>specific search algorithms GCP mentioned. >> >>Dave > >http://www.talkchess.com/forums/1/message.html?325994 > >Hmm, looks like GCP made reference to specific algorithms, but also general ones > in parentheses. I was focussing on the specific ones, I guess you focused on >the general ones. :-) > >Dave That was my point. breadth-first and depth-first, _by definition_ don't search the same nodes in the same order, with the one exception of a tree where each side has exactly one move at any position. Of course, that is a trivial case for chess although such positions do exist. But, nonetheless, I still disagree with the idea that SSS* and mtd(f) search the same trees in the same order. They don't. At least no implementation of SSS* and mtd(f) that I know of. The re-searching is a problem, and you can't possibly do mtd(f) without the re-searching.
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.