Author: Dave Gomboc
Date: 18:02:50 11/12/03
Go up one level in this thread
On November 12, 2003 at 13:43:06, Robert Hyatt wrote: >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? No, he isn't. MT-SSS* isn't mtd(f). mtd(f) is the new algorithm that is better than MT-SSS (a.k.a. mtd(-oo)). 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.