> MC/UCT is provably scalable up to perfect play. Really? Could you send me a link to the paper? I think we must have a different definition for some word. Perfect play? Are you saying that we have proven that the 19x19 go board has a perfect path for black? I did not realize we knew so much about the problem.
If it is proven to be scalable up to perfect play... then that would imply that we have some notion of how far away we are from perfect play. Or at the very least.. that we know what the graph of perfect play looks like. Maybe I am way behind in the theory.. but this seems incredible to me. On Sun, Aug 10, 2008 at 1:14 PM, Robert Waite <[EMAIL PROTECTED]>wrote: > > >* > The MCTS technique appears to be extremely scalable. The theoretical > *> >* > papers about it claim that it scales up to perfect play in theory. > **** > *>* > We agree here that this is not true of course. > * > > No, I think we disagree this time my friend! > > Monte Carlo of course by itself is not scalable. But when combined with > > tree search such as UCT, it is equivalent to a mini-max search with a > > > high quality evaluation at leaf nodes. It's scalable because the > > longer it searches, the more it acts like a proper mini-max search. > > I am not really sure what you guys meant by the interchange above.. and I > will admit that I am not nearly as deep into the problem as probably anyone > on this list.. but it seems doubtful that they have proven some sort of > scalable algorithm that will continue to give moves closer and closer to > perfect play with higher and higher confidence. I could believe that they > have a proof that the algorithm is scalable in computing power... but not > necessarily that it is scalable against the problem of beating a human. > > Firstly.. I don't know if there is necessarily "perfect" play. If you mean > play good enough to beat all humans... I guess you could consider that > perfect in a sense. > > It just seems that given the ridiculously large number of possible games... > and the relative weakness our our computation machines... we will be taking > an extremely small sample size with our current models of computing. There > may be some breakthrough... but it seems that as long as Moore's law > holds... we will continue to be taking a very small sample. There are some > heuristics being used to help whittle down the bad.. like checking the 8 > spots around a stone... but is it really proven that this algorithm will > scale in a practical sense? As in... if we took Mogo in it's current form > and threw all the hardware that humanity can make in the next 20 years at > it... has that alone been shown to be enough to beat humans? Seems that we > don't understand all of the parameters of human play to answer a question > like that. > > I am playing the Devil's advocate here.. because I do have a feeling that > the human computer with regards to go is not mystical and that we have a > weakness that can be exploited by computers. But I just feel that there is > no rigorous proof yet about the power of scalability of computation... vs. > the ability to beat a human in go. > > > On Sat, Aug 9, 2008 at 2:54 PM, Robert Waite <[EMAIL PROTECTED]>wrote: > >> I'm curious what you guys think about the scalability of monte carlo with >> UCT. Let's say we took a cluster like that which was used for the Mogo vs. >> Kim game. Then lets say we made 128 of these clusters and connected them >> together efficiently. Putting aside implementation and latency issues... >> what kind of stones-strength increase would you imagine? >> >> Its a pretty arbitrary guess.. but do you think one stone improvement... >> or that this would alone be enough to beat a pro even? >> >> I am wondering because there could be a weakness or limit in MC w/ UCT. I >> am only now learning about the UCT addition... but there are vast numbers of >> possible games that are never visited during the monte carlo simulations. >> The random stone simulations are pretty random aren't they? I am reading >> some of the papers on the UCT addition... and that does seem to show certain >> branches to be "better" and worth more time. Pro players may have a >> counter-strategy that might come out as Mogo is tested at higher levels of >> play. Perhaps there will be a need to combine MCwUCT with heuristics or more >> knowledge based play. Going the route of heuristics seems unpleasant and the >> promise of using a more computational method would be great. However... if >> MC techniques alone have a diminishing return... the route of heuristics >> might come back (or perhaps a whole new paradigm for game algorithms). >> >> I am still secretly on the side of human go beating the machine.. but the >> recent match really changed my view on topic and really showed the value of >> statistical analysis. I am just wondering about what kind of roadblocks >> might show up for the monte carlo techniques. >> > >
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
