Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Search algorithms

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.