Author: Robert Hyatt
Date: 17:38:25 11/09/03
Go up one level in this thread
On November 09, 2003 at 12:01:59, Dave Gomboc wrote: >On November 08, 2003 at 12:43:29, Robert Hyatt wrote: > >>On November 07, 2003 at 14:16:16, Dave Gomboc wrote: >> >>>On November 06, 2003 at 22:42:14, Robert Hyatt wrote: >>> >>>>On November 06, 2003 at 22:33:04, Robert Hyatt wrote: >>>> >>>>>On November 06, 2003 at 20:45:57, Dave Gomboc wrote: >>>>> >>>>>>On November 06, 2003 at 19:50:09, Robert Hyatt wrote: >>>>>> >>>>>>>On November 06, 2003 at 11:23:36, Dave Gomboc wrote: >>>>>>> >>>>>>>>On November 06, 2003 at 09:49:33, Robert Hyatt wrote: >>>>>>>> >>>>>>>>>On November 06, 2003 at 09:33:28, Renze Steenhuisen 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. >>>>>>>>>> >>>>>>>>>>Done that already, but as Aske stated: they search the same nodes, but in a >>>>>>>>>>different order. >>>>>>>>>> >>>>>>>>>>MTD(f) and the others are still DF algorithms, the second list works differently >>>>>>>>>>(i.e., the order in which the nodes are expanded is different). >>>>>>>>>> >>>>>>>>>>Or am I talking rubish? >>>>>>>>>> >>>>>>>>>>Renze >>>>>>>>>> >>>>>>>>>>PS: Am I missing algorithms (either important or not)? >>>>>>>>>>PS2: Are Scout and NegaScout equal? >>>>>>>>> >>>>>>>>> >>>>>>>>>They are just variations on the same idea. All fall under the umbrella >>>>>>>>>of alpha/beta depth-first search... (this is in response to your question >>>>>>>>>PS2). >>>>>>>>> >>>>>>>>>depth-first and breadth-first (best-first is one example of the latter) >>>>>>>>>are totally unrelated other than the fact they both search a tree. >>>>>>>> >>>>>>>>Well, no. Read Plaat's thesis. >>>>>>>> >>>>>>>>Dave >>>>>>> >>>>>>> >>>>>>>I have read it. It does _not_ say the two are equivalent in any shape >>>>>>>or form, except for the actual tree searched in certain circumstances. >>>>>>>Depth-first and breadth-first are completely different approaches to >>>>>>>growing a tree, even if on some occasions they grow the _same_ tree. >>>>>> >>>>>>In this particular case, the algorithms search the same tree. Therefore, I >>>>>>think it's reasonable to claim they are they are equivalent in some shape or >>>>>>form -- not in all shapes and all forms, but at list with respect to the nodes >>>>>>searched and the order in which they are searched. :-) >>>>>> >>>>>>Dave >>>>> >>>>> >>>>>I don't believe that last is correct. IE with respect to order. Particularly >>>>>comparing members of the breadth-first family to the depth-first family and >>>>>not just picking one specific algorithm from each. >>>> >>>> >>>>BTW, I hope you don't try to convince me all sort algorithms are >>>>equivalent, just because they take the same list and produce the >>>>same final result. :) >>> >>>Well, what is correct is that the node expansions are done in the same order. >>> >>>Dave >> >> >>Again, what two algorithms specifically are you comparing? Best first >>and depth-first _never_ expand the nodes in the same order, except for >>trees where each side has only one legal move at every position... > >Replied in other thread. > >Dave I'll go back and re-read this stuff. One thing is crystal clear. Best first is a breadth-first algorithm. mtd(f) is clearly a depth-first algorithm based on alpha/beta. I don't see how the two can ever be comparable in the tree size searched, nor in the order the nodes are expanded. The two search strategies (depth-first vs breadth-first) are simply too different... At least in any book I own.
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.