Author: Robert Hyatt
Date: 10:43:06 11/12/03
Go up one level in this thread
On November 12, 2003 at 04:28:13, Dave Gomboc wrote: >On November 10, 2003 at 12:55:20, Robert Hyatt wrote: > >>On November 10, 2003 at 11:35:17, Dave Gomboc wrote: >> >>>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 >> >> >>OK. My interpretation was correct. In this case, his basic asumption >>is wrong. Just look at an mtd(f) tree. To complete a depth=N search, >>you must do _two_ complete mtd(f) searches, one with the score at or >>below the true score, and one with the score at or above the true score. >> >>I don't see where SSS* searches tip positions twice. Which mtd(f) will >>do in many cases. I also disagree about the "order" as well. Because in >>the best case your first search fails high (searching with alpha,alpha+1) >>while the second search fails low searching with alpha+1 and alpha+2. You >>just learned that the true score is alpha+1, but look at what you searched >>and the order. Assuming a 3 ply search here, your first search examined >>every root move and for each root move it searched _every_ move at ply=2. >>At ply=3 one move is enough (assuming perfect ordering which is a bad >>assumption) you again search one move only. You therefore search the _first_ >>move at every ply=3 position only. >> >>Now you come back and research after bumping the scores by 1. Now for >>each root move, you only search one move at ply=2 (the move that refutes >>the ply=1 move and makes it fail low). For every ply=2 move you search, >>you search _all_ moves at ply=3. >> >>On the first search, you only search the first ply-3 move for each new >>position. On the second search, you search all ply-3 moves for each new >>position. You have searched one ply-3 move _twice_. >> >>None of this "same order" stuff makes any sense in that context. SSS doesn't >>come close to searching the tree in that order. It is a best-first. The >>point of best-first is that you don't search every move to the same depth, >>at least not to start with. >> >>There might be pathological cases where the two search the same tree, but I >>can't imagine what it would be, in the case of mtd() because of the re-searching >>necessary to get the actual score. Perhaps serendipity might help on occasion >>to let you do just one search and get the one best move, but proving that >>happened would be problematic without a second search to show that the best >>move will fail low with a slightly higher expectation, and that no other move >>will fail high with that same expectation. > >Two things: >- it's not an mtd(f) tree being compared, it's an mtd(-oo) tree. There's a huge >difference. >- the claim is about the order of leaf node expansion, not of internal tree >traversal. > >Dave Isn't he referring to MT-SSS* and saying it is equivalent to MTD(f) first? The problem is that mtd hits the leafe nodes multiple times in a normal search. The _same_ leaf nodes. I don't see how that meshes with SSS* at all which is a best-first search. MTD is going to hit the "left-most" leaf first. SSS* won't because of the best-first expansion. IMHO there are simply some assumptions being made in that appendix that are not necessarily sound when applied to _real_ game tree searches...
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.