On Sun, 2008-08-10 at 13:14 -0400, Robert Waite 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.
I think the proof is in the paper. And it makes sense. I have no doubt the program is scalable which means even GOD cannot beat it given enough computing power. It certainly means that given enough computing power it can beat the best human players. This is not a stretch. Of course the magic phrase "enough computing power" is where there is plenty of room for argumentation, but not in the scalability issue. > > 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. It doesn't matter WHO you play, if it's scalable it can eventually play perfect, easily enough to be humans and draw with GOD. The scalability is somewhat theoretical in the sense that there is some question about whether these programs are technically correct. For instance they all use some eye termination rule that is not 100% admissible. Unless that is fixed, then even on an "infinite" computer they will play at least slightly weaker than perfect. But I don't believe that has a huge amount of relevance when talking about beating humans. - Don > > 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/ _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
