(I typed the following up earlier today, before other people cast some doubts about what "infinite scalability" means. Perhaps it is helpful.)
I think that Alain was specifically referring to a property of UCT, whereby given that a winning line of play exists, the probability that the algorithm has discovered one such line & settled upon it approaches 1 as time approaches infinity. I believe that this has been proven. And no, this theoretical result does not represent any intrinsic advantage over a calculation of the minimax value. (Someone should feel free to correct me if there is a stronger theoretical result that I am not aware of, though.) I think it is important to understand that unless you restrict UCT from exploring some correct lines of play, this "infinite scalability" will still be true. And, it is true regardless of what moves have been preferred/pruned/whatever within the MC playouts. (Or whatever one does at the leaf nodes; it need not be MC at all, as long as the UCT tree eventually gets expanded as the node is revisited.) This is not to say that this particular property of UCT is sufficient in order for us to claim that UCT is scalable in practice. My point is rather that noone is claiming "infinite scalability of MC", but rather scalability of UCT. When you combine that with the fact that UCT has been very successful at 9x9 go, (and scalable across a wide range of time limits) it seems to be reasonable to expect more of the same in 19x19. (Which is what concerned the original poster.) Also, one should expect that the UCT portion of MC-UCT will tend to eventually "fix up" any systematic errors that are made by the MC playouts. I have one other point I'd like to make, in regard to "light" versus "heavy" playouts: Even "light" playouts do not actually use a uniform distribution, due to the quasi-eye rule that is generally used. I think that there is every reason to expect that other "nonuniform" playout policies further outperform "light" playouts in every practical way. Granted, it is possible to introduce "severe misconceptions" when one incorporates knowledge into one's playouts. But even in that case, one can still fall back on the fact that UCT is cleaning up after one's mistakes: the eventual behavior, given enough time, is still perfect play. (And of course it is not as if people blindly adjust the monte carlo policies without checking the revised versions for "severe misconceptions".) Weston On 1/22/08, ivan dubois <[EMAIL PROTECTED]> wrote: > I think there is some missconception about this "infinite scalability of MC" > stuff. > Theory is only usefull when the model it is based on shares important aspects > with reality. > In theory, 19*19 Go is a finite game, wich can be analysed in a finite amount > of time. So ANY algorithm that solves the game at some point is, in theory, > infinitely scalable. For example, the folowing algorithm is infinitely > scalable : > Analyse the complete mini-max tree of the game. If enough time to finish, > returns the correct move, if not, return a random move. > > Now, is this algorithm really scalable, in practive ? Of course not. > > I support the idea that MC is infinitely scalable (in the reality) ONLY if > the play-out part does not have severe misconceptions. So i think that > currently, only MC based on uniform playouts is infinitely scalable. > It is well know that even Mogo has troubles with big eyes (he thinks a big > eye gives life, wich is false). This problem can not be solved with more > computing power (excep absurdly big, of course you can always mini-max to the > end). > > ----- Message d'origine ---- > De : Alain Baeckeroot <[EMAIL PROTECTED]> > À : computer-go <computer-go@computer-go.org> > Envoyé le : Mardi, 22 Janvier 2008, 22h13mn 26s > Objet : Re: [computer-go] Is MC-UCT really scalable ... is a troll > > Le mardi 22 janvier 2008, David Fotland a écrit : > > > > The UCT-MC programs do particularly well against traditional programs > > because they expose the brittleness inherent in the pattern databases they > > use. Strong humans are not so easily beaten by playing unconventional and > > somewhat inferior moves. > > > I think Remi posted a game of CrazyStone on 19x19 commented by one pro > who said "this move is 2 dan level". > So far no go program got such analyse, and the also the huge novelty > provided by MC/UCT programs is they have a _real_ strenght with their > own style, like humans: > play solid when winning, and play hamete (tricky moves) when losing. > > On kgs MC programs played hundreds (if not thousands) games against humans, > and no doubt they fully merit their rank, and no doubt they are improving. > > Infinite scalability is a theoricaly proved property, so please > don't feed the troll :-) > > Alain > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > _____________________________________________________________________________ > Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail > http://mail.yahoo.fr > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ > _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
