Re: [computer-go] Is MC-UCT really scalable ... is a troll
Le mercredi 23 janvier 2008, ivan dubois a écrit : Hi Alain, Sorry for being so insistant : You should browse the archive of the list, nearly the same discussion about infinite and scalability happenned in 2007. No i just said that, unless i really understood nothing, i read here from well known competent persons that MC+UCT scales infinitely , and would reach perfect play with infinite computational resources, and this is theoretically proven (which is not the case for classical program like our beloved GNU Go). This is absolutely true. Now this can also be said for a mini-max solver (my point). Don Dailey answered better than i could do, yes minimax also scales. So MC+UCT scales. (even against humans, martians, trolls, computers, gods ... :) The conclusion does not follow. Ah ? Why not ? what is wrong in the reasonning ? Should i think : It scales in theory so it does NOT scale in practice ? The fact that it eventualy reaches perfect play with enough computing power does NOT mean that it scales well. Proof : A mini-max solver does reach perfect play with enough computing power BUT does not scale. we dont have the same informations. For Minimax scales too, maybe the improvement curve has a smaller slope than MC+UCT curve, but Actualy, this theoritical property is a NESCESSARY condition for UCT to scale, but it is not a SUFFICIANT condition. The scalability of UCT has been proven by its outstanding results From a pure logical point of vue - Positive experiment are never a valid proof. They are only examples that makes one feel his theory is right. - Only counter example are proof that the theory is wrong. and Don's experiments, not by mathematics. Are you a troll ? Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is MC-UCT really scalable ... is a troll
On Tue, Jan 22, 2008 at 05:17:48PM -0500, [EMAIL PROTECTED] wrote: Don't make too much of it. A 2-Dan program will play 2-Dan games, not just occasionally generate a 2-Dan move. :) True. Most weak beginners start the game with a move that is often seen in professional play. Usually 3-3, 3-4, or 4-4. -H -- Heikki Levanto In Murphy We Turst heikki (at) lsd (dot) dk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Is MC-UCT really scalable ... is a troll
Duhhh ! When I say a minimax solver, I mean a program witch returns a random move UNTIL it has completed its search, as I explained in a previous post. You all agreed this program didnt scale, so why are you saying, all of a sudden, that it DOES scale now !? Anyway I'm fed up with this discussion now, this is so too much pain and way too frustrating. - Message d'origine De : Alain Baeckeroot [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 9h15mn 41s Objet : Re: [computer-go] Is MC-UCT really scalable ... is a troll Le mercredi 23 janvier 2008, ivan dubois a écrit : Hi Alain, Sorry for being so insistant : You should browse the archive of the list, nearly the same discussion about infinite and scalability happenned in 2007. No i just said that, unless i really understood nothing, i read here from well known competent persons that MC+UCT scales infinitely , and would reach perfect play with infinite computational resources, and this is theoretically proven (which is not the case for classical program like our beloved GNU Go). This is absolutely true. Now this can also be said for a mini-max solver (my point). Don Dailey answered better than i could do, yes minimax also scales. So MC+UCT scales. (even against humans, martians, trolls, computers, gods ... :) The conclusion does not follow. Ah ? Why not ? what is wrong in the reasonning ? Should i think : It scales in theory so it does NOT scale in practice ? The fact that it eventualy reaches perfect play with enough computing power does NOT mean that it scales well. Proof : A mini-max solver does reach perfect play with enough computing power BUT does not scale. we dont have the same informations. For Minimax scales too, maybe the improvement curve has a smaller slope than MC+UCT curve, but Actualy, this theoritical property is a NESCESSARY condition for UCT to scale, but it is not a SUFFICIANT condition. The scalability of UCT has been proven by its outstanding results From a pure logical point of vue - Positive experiment are never a valid proof. They are only examples that makes one feel his theory is right. - Only counter example are proof that the theory is wrong. and Don's experiments, not by mathematics. Are you a 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/
Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll
On Jan 23, 2008 2:45 PM, ivan dubois [EMAIL PROTECTED] wrote: When I say a minimax solver, I mean a program witch returns a random move UNTIL it has completed its search, as I explained in a previous post. A plain minimax solver (without enhancements like iterative deepening) doesn't return anything until it has completed its search. E. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Ok, this is a special minimax solver. Call it the Ivan Dubois stupid minimax solver if you like. Anyway, its only purpose is to show that : Returns the best move when given enough time does NOT implie Is scalable in practice. I am very sad that this simple logic has no appeal to most people on this list. - Message d'origine De : Erik van der Werf [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 15h21mn 37s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll On Jan 23, 2008 2:45 PM, ivan dubois [EMAIL PROTECTED] wrote: When I say a minimax solver, I mean a program witch returns a random move UNTIL it has completed its search, as I explained in a previous post. A plain minimax solver (without enhancements like iterative deepening) doesn't return anything until it has completed its search. E. ___ 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/
Re: Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
On Jan 23, 2008 3:44 AM, Don Dailey [EMAIL PROTECTED] wrote: This is still nonsense. UCT in actual real world PRACTICE responds dramatically to more hardware, how can you say it's not clear whether it's scalable in practice? In fairness, he didn't say that. What he said was that our belief regarding whether or not UCT scales in practice, should be based on tests on real hardware (which appear to give an answer in the affirmative), rather than on a mathematical proof of what happens in the limit as computer time tends to infinity (because what happens in the limit as time tends to infinity, doesn't necessarily have much bearing on what happens on real hardware; so tests are more informative). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : [computer-go] Is MC-UCT really scalable ... is a troll
Thanks. - Message d'origine De : Russell Wallace [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 18h07mn 27s Objet : Re: Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll On Jan 23, 2008 3:44 AM, Don Dailey [EMAIL PROTECTED] wrote: This is still nonsense. UCT in actual real world PRACTICE responds dramatically to more hardware, how can you say it's not clear whether it's scalable in practice? In fairness, he didn't say that. What he said was that our belief regarding whether or not UCT scales in practice, should be based on tests on real hardware (which appear to give an answer in the affirmative), rather than on a mathematical proof of what happens in the limit as computer time tends to infinity (because what happens in the limit as time tends to infinity, doesn't necessarily have much bearing on what happens on real hardware; so tests are more informative). ___ 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/
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/
Re : [computer-go] Is MC-UCT really scalable ... is a troll
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/
Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll
On Tue, 22 Jan 2008, ivan dubois wrote: 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 have to disagree. The above algorithm is not scalable in a sense that more time leads to better moves. Ie. It returns a random move given 1 minute, 1 hour or 1 day of (current) CPU time, while a scalable algorithm should return a better move the longer it runs. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Is MC-UCT really scalable ... is a troll
I think Remi posted a game of CrazyStone on 19x19 commented by one pro who said this move is 2 dan level. Don't make too much of it. A 2-Dan program will play 2-Dan games, not just occasionally generate a 2-Dan move. :) Infinite scalability is a theoricaly proved property, so please don't feed the troll :-) Are you saying that the scalability is linear between number of playouts and ranking? DL ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ More new features than ever. Check out the new AOL Mail ! - http://webmail.aol.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll
ivan dubois wrote: I think there is some missconception about this infinite scalability of MC stuff. There is no misconception. This is clearly a PRACTICAL concept. Theory is only usefull when the model it is based on shares important aspects with reality. Which it does clearly. 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. This is not a scalable algorithm, it only solves the game and it takes too long for that.Put an evaluation function and iterative deepening and it's an example of an algorithm that scales, but very poorly. (Unless it's really implemented well with alpha/beta, progressive selectivity, excellent evaluation, etc.) I support the idea that MC is infinitely scalable (in the reality) ONLY if the play-out part does not have severe misconceptions. That's not the definition of infinite scalability.You seem to believe that infinite scalability is suppose to mean that it plays perfectly with a few seconds of thinking time. Infinite scalability simply means you can add a modest amount of time and expect to see a tangible (we are talking reality here) improvement. Nobody seriously expects perfect play with a few minutes of thinking and you are way off base if you thought that. So i think that currently, only MC based on uniform playouts is infinitely scalable. I don't know what you mean by that, but heavy play-outs will ALWAYS outperform uniform random play-outs and any number of play-outs. Unless the heavy play-outs are actually horrible wrong, but I'm talking about anything proven to be superior at low levels such as the heavy play-outs of every MC program today. 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/
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Hello Christoph, I agree with you that this algorithm is not scalable if you use this definition, but : When people say that MC infinite scalability is mathematicaly proven, they do not refer to the definition you give, they refer to the definition I used. If you want to do a theoretical analysis of MC scalability with your definition, you will first have to define exactly what you call a better move. This might be tough. Even if you managed to do that, you would see that MC is not scalable with this definition, because obviously, more computing power can, in some occasions, provide a worse move (what ever you call a worse move). Ivan - Message d'origine De : Christoph Birk [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mardi, 22 Janvier 2008, 22h50mn 29s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll On Tue, 22 Jan 2008, ivan dubois wrote: 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 have to disagree. The above algorithm is not scalable in a sense that more time leads to better moves. Ie. It returns a random move given 1 minute, 1 hour or 1 day of (current) CPU time, while a scalable algorithm should return a better move the longer it runs. Christoph ___ 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/
Re: Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
On Tue, 22 Jan 2008, ivan dubois wrote: When people say that MC infinite scalability is mathematicaly proven, they do not refer to the definition you give, they refer to the definition I used. No, they don't. At least not most people on this list. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re : Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Could you please tell me what definition they use ? Dont forget, i am talking about a theoritical definition, wich can support mathematical analysis. Ivan - Message d'origine De : Christoph Birk [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mardi, 22 Janvier 2008, 23h38mn 30s Objet : Re: Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll On Tue, 22 Jan 2008, ivan dubois wrote: When people say that MC infinite scalability is mathematicaly proven, they do not refer to the definition you give, they refer to the definition I used. No, they don't. At least not most people on this list. Christoph ___ 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/
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Don, I was referring to this exact sentence from Alain : Infinite scalability is a theoricaly proved property, so please don't feed the troll :-) Do you agree with me that such a claim requires a mathematical definition of what A scalable algorithm is ? If this definition is not the one I used, could you please tell me what it is ? Now about the PRACTICAL scalability of MC, this is a completetly different matter : Thats my point. Ivan - Message d'origine De : Don Dailey [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mardi, 22 Janvier 2008, 23h28mn 09s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll ivan dubois wrote: I think there is some missconception about this infinite scalability of MC stuff. There is no misconception. This is clearly a PRACTICAL concept. Theory is only usefull when the model it is based on shares important aspects with reality. Which it does clearly. 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. This is not a scalable algorithm, it only solves the game and it takes too long for that.Put an evaluation function and iterative deepening and it's an example of an algorithm that scales, but very poorly. (Unless it's really implemented well with alpha/beta, progressive selectivity, excellent evaluation, etc.) I support the idea that MC is infinitely scalable (in the reality) ONLY if the play-out part does not have severe misconceptions. That's not the definition of infinite scalability.You seem to believe that infinite scalability is suppose to mean that it plays perfectly with a few seconds of thinking time.Infinite scalability simply means you can add a modest amount of time and expect to see a tangible (we are talking reality here) improvement.Nobody seriously expects perfect play with a few minutes of thinking and you are way off base if you thought that. So i think that currently, only MC based on uniform playouts is infinitely scalable. I don't know what you mean by that, but heavy play-outs will ALWAYS outperform uniform random play-outs and any number of play-outs. Unless the heavy play-outs are actually horrible wrong, but I'm talking about anything proven to be superior at low levels such as the heavy play-outs of every MC program today. 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/ _ Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail http://mail.yahoo.fr
Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll
(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
Re: [computer-go] Is MC-UCT really scalable ... is a troll
Le mardi 22 janvier 2008, [EMAIL PROTECTED] a écrit : Infinite scalability is a theoricaly proved property, so please don't feed the troll :-) Are you saying that the scalability is linear between number of playouts and ranking? No i just said that, unless i really understood nothing, i read here from well known competent persons that MC+UCT scales infinitely , and would reach perfect play with infinite computational resources, and this is theoretically proven (which is not the case for classical program like our beloved GNU Go). So MC+UCT scales. (even against humans, martians, trolls, computers, gods ... :) Alain. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll
Exactly! Well said. Weston Markham wrote: (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
Re : Re : [computer-go] Is MC-UCT really scalable ... is a troll
Thanks ! I think I agree with everything you said. After some reasoning, I changed my opinion about the practical scalability of Mogo. It does have some missconceptions about eyes, but as you said, it can be corrected by the UCT part. I tried to find a situation where the UCT part does not help until the situation comes to a conclusion, with no success. So you are probably right, maybe I will give some more thought about it, or not :) But I stay on my position that the theoritical infinite scalability of UCT doesnt give any hint about whether or not it is scalable in practice. I think you made my point clear : From a pure theoritical point of view, it has no advantage over a simple mini-max solver. Given that a mini-max solver is NOT considered scalable in practice, I see no reason why people would see this property of UCT as an indication of its scalability. Ivan - Message d'origine De : Weston Markham [EMAIL PROTECTED] À : computer-go computer-go@computer-go.org Envoyé le : Mercredi, 23 Janvier 2008, 0h41mn 08s Objet : Re: Re : [computer-go] Is MC-UCT really scalable ... is a troll (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
Re : [computer-go] Is MC-UCT really scalable ... is a troll
Hi Alain, Sorry for being so insistant : No i just said that, unless i really understood nothing, i read here from well known competent persons that MC+UCT scales infinitely , and would reach perfect play with infinite computational resources, and this is theoretically proven (which is not the case for classical program like our beloved GNU Go). This is absolutely true. Now this can also be said for a mini-max solver (my point). So MC+UCT scales. (even against humans, martians, trolls, computers, gods ... :) The conclusion does not follow. The fact that it eventualy reaches perfect play with enough computing power does NOT mean that it scales well. Proof : A mini-max solver does reach perfect play with enough computing power BUT does not scale. Actualy, this theoritical property is a NESCESSARY condition for UCT to scale, but it is not a SUFFICIANT condition. The scalability of UCT has been proven by its outstanding results and Don's experiments, not by mathematics. Ivan ___ 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/
