Author: Dave Gomboc
Date: 01:28:13 11/12/03
Go up one level in this thread
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
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.