Author: Robert Hyatt
Date: 09:55:20 11/10/03
Go up one level in this thread
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.
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.