Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
> You mentioned three proofs relating to go... could you post the links to the > papers? the first two statements are consequences of the following: all two-person, finite, zero-sum games have solutions. * for a more precise statement, see john von neumann's 1928 paper: Von Neumann, J: Zur theorie der gesellschaftsspiele Math. Annalen. 100 (1928) 295-320 and the definitions of the terms used in the statement (*). or perhaps more helpfully, a modern treatment on the subject of game theory. the third statement is true simply because the minimax algorithm exists. i am not claiming that any of this has anything to do with the actual problem of beating a human. i am not making this claim because i also make the claim that beating humans at go is pretty much unrelated to the mathematics in these proofs. > I didn't ask for a mathematical proof saying if a computer can beat a human. > I asked in a roundabout way if this algorithm (or any known algorithm) has a > proven complexity that is somehow tractable or useful to beat humans. Just > by throwing human in does not mean you are out of the realms of math. What > about statistics? The object of many statistical models is a group of > people. So please don't say it makes no sense to ask about mathematical > proofs of anything related to humans. A mathematical proof can have a result > that affects humans. If it was proven tomorrow that there is a set of > algorithms that can solve the game in poly time.. we could draw relevant > conclusions with regards to beating a human being. Relating humans to math > does not destroy the accuracy of the relation. algorithms do not have complexities, problems do. algorithms may have asymptotic runtimes, but even this isn't always true. poly time doesn't mean tractable. just like exptime doesn't mean intractable. there's a coefficient in front of the polynomial (or exponential function) that can radically affect the real-world tractability of the problem. another thing is that complexity classes are used to describe problems like, "find me an algorithm that can solve the game of go for *any* sized board". in this sense, go is quite difficult. however, nobody on this list is seriously hoping to write a program to solve go for any sized board and hoping that it will succeed on a 19x19 board. what they are doing is trying to engineer very good programs to beat humans on a 19x19 board. > whether or not computers can beat humans at go on a > 19x19 board in a reasonable amount of time is unrelated > to mathematics. > > Why? Let's say you can prove that the game is solvable so that black wins. > Let's say that you can prove that it is solvable in linear time. You can > then infer that we could build a machine to play the solved game and beat a > human unconditionally. Why can't you use the math here to make a statement > about beating humans? what if the linear function is this one: time = 10^10^10^10^10^10^10 * (size of board) that doesn't imply tractability, but it is still linear. the problem that i mentioned earlier: "how much effort is required to completely solve the game of go for _any_ given boardsize" is known not to be linear. it's known not to be polynomial. the problem of "solve the game of go for a 19x19 board" is known to be a *constant*. since there are only a finite number of legal board situations, there are only a finite number of legal games. enumerating all of these takes a constant amount of time. storing these takes a constant amount of space. this is not useful to make good programs for playing go, however. the thing is, all of the talk of asymptotics that you seem to be referring to are perfectly useful to prove things about arbitrary games on arbitrary sized boards, but when you have a fixed-size board, what matters is much more an issue of engineering a fixed problem. s. > > ___ > 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: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
Robert Waite wrote: whether or not computers can beat humans at go on a >> 19x19 board in a reasonable amount of time is unrelated to mathematics. Why? Let's say you can prove that the game is solvable so that black wins. Let's say that you can prove that it is solvable in linear time. You can then infer that we could build a machine to play the solved game and beat a human unconditionally. Why can't you use the math here to make a statement about beating humans? Because solving the game is not a prerequesite for beating the humans. There are very obvious examples(chess) -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
erm. you guys seem to be arguing for the sake of arguing, without a clear or precise definition of what you're even arguing about. there is a mathematical proof that go, for any fixed sized board, can be completely solved. there is a mathematical proof that given a fixed komi and fixed number of handicap stones, every game is either a forcible win or loss or draw for a particular one of the two players. we don't know this function yet, so we don't know if there's advantage for white or black or not, but it's guaranteed to exist. is proven to exist. there is a mathematical proof that current algorithms can solve go. it makes no sense to ask if there is a mathematical proof of anything related to humans. the two are simply incommensurate. the mathematical proofs are simply about whether a computer with a lot of memory and a lot of free time can win or force draws in every game of go against any player. and it turns out that this is true. whether or not computers can beat humans at go on a 19x19 board in a reasonable amount of time is unrelated to mathematics. * computers are getting better and better at go. most people on this mailing list are mainly interested in helping (*) to happen. s. On Sun, Aug 10, 2008 at 11:46 PM, Denis fidaali <[EMAIL PROTECTED]> wrote: > > Hi there. > > I do agree with your point Robert Waite. > I have yet seen no such paper as one that would prove that there is such > thing as scalability based on any mathematical proofs. > So all your points at criticizing the "mathematical certainty" of the > scalability, is probably 100% right. There is no such things as mathematical > certainty there. > > It can be modelized easily, as you already did : what if the the "evaluation > function" is giving "on purpose" wrong data. How would one mathematically > prove that it doesn't ? You would at a minimum have to know WHAT the > "evaluation function" ACTUALLY exactly is ... In fact all the evidences that > we have gathered about the scalability may rather been surprising to some > persons : why in hell does all that works so well ? > > But, it's a "proven" fact that it does indeed works well so far. So that it > seems perfectly natural to speak such phrases as "there are evidences that > given the hardware we got in twenty years, human will be beaten by current > algorithms". I don't see how those evidences can be qualified with the term > "mathematical", but they are here (hiding among us !). Now if someone has > the feeling that maybe there is a roadblock, it has to be considered for > what it is : a personal intuition. What is this intuitions precisely based > on ? Why are you trying to share it with us in the first place. For myself, > i believe that what you are trying to do, is to begin to analyses all the > data the community has gathered so far, trying to understand why indeed it > worked so well that it even beaten out a pro with a 9 stones handicap and > with as few as 1.7 million evaluations/second (running on some 800 hundreds > cores). To the point that the pro felt he had no chances of wining at all > with that much of a handicap. Your are trying to understand this, and are > probably right on track for that goal. The term "mathematical" is very > valuable to you, and you'll find it that it has a much wider use (on this > list) than what you would like it to. But now, "mathematics" as proven to be > of little use in the context of go programming lately. It's more of a > "physician" world. You make up a (mathematical) model. You test it again > "reality" via experimentations. You then get "empirical" certitudes that the > model is indeed correct. > > There is no way of mathematically proving that light speed would still be > constant if i chose to dance naked on the champs-Elysée some day. You'll > definitely find no paper on that. Yet to speak of it as mathematically > certain, is probably not as wrong as it sound. > > > But as it is, i'm playing the devil advocates here. I'm totally agreeing > with you. I found your way to fight irrationnality very interesting indeed. > It's been very refreshing. > > > - > Robert Waite has wrote : > > I would really like to see what paper you are referring to. Do you mean > "Bandit based Monte-Carlo Planning"? Please post the name of the paper which > you are referring to. I do not think that the empirical evidence is > overwhelming that it is scalable in a practical way for the problem of > beating a human. > > Now the topic has moved to scalable to beat a human and I disagree with the > interpretation of the data. We are both interpreting data. Your data doesn't > count as a theory.. where you reduced my theory to one that has no data. We > are both interpreting the same data. Diminishing returns was just an example > of something that could be a roadblock. I was questioning how this > necessarily scales to humans. It seems more data is needed from MC-prog
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
On Aug 10, 2008, at 1:46 PM, Robert Waite wrote: Exhaustive search is scalable in that I could give it all the memory and time it wanted. And it would approach a finite amount of memory and a finite amount of time. Yes, but "exhausitve search" does not improve your player by 63% (eg.) for a doubling in CPU time. This part was done in an empirical scalability study. Please check the archives of the list. In the (inifinite) limit minimax+evaluation-function would find the perfect move too, but UCT/MC already find "good" moves before the limit. Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
On Sun, 2008-08-10 at 19:32 -0400, Robert Waite wrote: > Well... I think I have hunches just as you do. And I think we both > express our hunches on here. > > Diminishing returns is not really my theory.. I am just looking at > alternative ways of viewing the datapoints. Let's say you have two > computers and both of them focus only on solving local situations. At > first they both play around the same level. Then you scale one of them > in some way and mark the trend. We now know that one of them scales a > certain way when solving local solutions. If you then take that > computer and put it against a person.. the person is no longer just > thinking about the local solution. They are thinking about strategy, > they might make certain moves that test the computer's goals.. you > have a whole different situation. > > The little green men reference looks like a dangerous use of Occam's > Razor. In this case... someone says there are little green men under > his house and shows me a bunch of datapoints to suggest it. I don't > have any datapoints against it so my point is automatically > invalidated? It seems there is a little more detail to Occam's Razor. The little green men was more about burden of proof, not Occam's Razor. As far as Occam's Razor is concerned it does not deal with proof or disproof. It's a general principle and sometimes it doesn't work because things sometimes really do have complicated explanations. It's another way to say, if it looks like a duck, walks like a duck, quacks like a duck, don't keep insisting that it's a dog. Have you seen the contortions that the flat-earthers go to in order to explain away the facts? They continue to produce a stream of datapoints to suggest they are right and that doesn't prove they are wrong, but I'm not going to waste my time trying to refute them. > > When I saw "proven to be scalable", my first thought was that it was > proven to be somehow practically scalable in order to beat a human or > perhaps to solve the game. You even mentioned that God would draw with > the computer. That kind of scalability seems related to solving the > game, not to beating a human. I saw no evidence that it has a > practical scalability to solve the game. And this seems like the kind > of problem that could be intractable. Practicality is an issue. Are you seriously trying to make an issue out of whether a mini-max search or MCTS can "solve" 19x19 go in any practical sense? If that's what you've been talking about, then I think we both wasted our time. Let me set your mind at ease, I agree with you. I don't know what that has to do with the price of tea in China and I didn't know you were hung up on that point. Anyway, that has nothing to do with anything I was talking about. I thought we were talking about whether we had reasonable hope that a go program could be equal to the best players withing a very few decades. > Now the topic has moved to scalable to beat a human and I disagree > with the interpretation of the data. We are both interpreting data. > Your data doesn't count as a theory.. where you reduced my theory to > one that has no data. We are both interpreting the same data. What are you talking about? The only thing I see going on here is that you are playing devils advocate and throwing out stuff without much basis. We are both doing some conjecture and that's ok with me but you seem to be going out on a much farther limb than I am. You are the guy that says the duck is a dog. I agree that there is a chance you could be right, there is a slight chance that it could be a highly deformed dog with a vocal abnormality. > Diminishing returns was just an example of something that could be a > roadblock. I was questioning how this necessarily scales to humans. It > seems more data is needed from MC-programs vs. humans to make a > rigorous theory of scalability. So far.. the only scalability that > seems proven is a case for solving the game... not beating humans. You cannot solve the game without beating humans along the way. > There is some point between that would most likely in my opinion lead > to humans being beaten.. some amount of calculation before you solved > it.. but the shape of this curve is something I am unsure of. It's shaped like a duck. It starts out with a gentle slope, then it violently turns upward (forming the head) where it flattens out near the top, then begin the gradual downward slope to the beak. Then it doubles back on itself to form the lower beak before it begins forming the breast, moving forward once again.That's my theory anyway. Can you prove me wrong? Occam is wrong about this one! > It doesn't seem that unreasonable to question if there is a practical > scalability. It does seem unreasonable to me. But it's certainly ok to have some questions. I'm pretty confident that it will work the same as in every other game - extra CPU power makes the programs stronger
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
Robert, Do you know what Occam's razor is? Einstein originally believed that the universe was static. When this didn't fit his observations he invented the "cosmological constant", which he considered one of his biggest blunders. If we are going to continue to discuss this, then if you have a theory that has no yet existing evidence (such as sudden diminishing returns) then YOU present evidence. This is called the burden of proof. If you accuse someone of some crime, it isn't up to them to prove you wrong, it is up to you to prove your assertion. You might believe that it's up to me to prove that there isn't a sudden diminishing returns affect, but you have it backwards. It would be pretty unreasonable to continue to throw assertions at me that I have to prove - YOU are the one that needs to prove your assertions. I think there are little green men living about 20 miles down below the surface of the earth. Prove me wrong! See, you can't so there! The facts are that Mogo is strong, it's CLEARLY stronger on big Iron and they went to a lot of trouble getting big Iron based on that fact. We also observe that the good programs do better against both humans and other programs. Do you have something we don't know about that is more than a hunch? - Don On Sun, 2008-08-10 at 16:46 -0400, Robert Waite wrote: > > I don't know how you can say that. The empirical evidence is > > overwhelming that this is scalable in a practical way but more > > importantly it's been PROVEN to be scalable. If you throw the word > > > "practical" in there then you are no longer talking the language of > > mathematics, theory and proofs so please don't ask for a "proof" of > > "practical" scalability, it makes no sense. > > I would really like to see what paper you are referring to. Do you > mean "Bandit based Monte-Carlo Planning"? Please post the name of the > paper which you are referring to. I do not think that the empirical > evidence is overwhelming that it is scalable in a practical way for > the problem of beating a human. > > "PROVEN to be scalable"? Big deal... isn't an algorithm that does an > exhaustive search provable to be scalable in the same sense? The fact > that it is proven to be scalable as the sample size increases to > infinity does not help the cause. The only thing that helps is the > rate at which it approaches "perfect play". How is this different from > exhaustive search with regards to being proven to be scalable? > Exhaustive search is scalable in that I could give it all the memory > and time it wanted. And it would approach a finite amount of memory > and a finite amount of time. > > Complexity theory is based on math and it does address "practicality". > By using the word practical.. I am not jumping into mysticism. I feel > that the proof that you offer does not help us in a practical sense, > at least in a rigorous mathematically proven way. > > > We are of > > course talking about the issue of scalability in a practical game > > improving sense. > > Okay.. so where is the paper that correlates the speed at which MCwUCT > approaches perfect play with the ability to play a human? They seem > unrelated as of yet. > > I think it's very likely that the > diminishing returns curve will be very very gradual for a long time to > come, well beyond the point of achieving the top human levels. > This is conjecture... and it does not relate with MC methods being > proven to be scalable. It's a gut feeling.. just like many feelings I > have about go. > > > When our realities don't match > > our belief systems, we balk. > > If you take them off the > > pedestal, you can think more rationally about it. > > I don't think that represents my feelings on the subject. My gut > feeling before the match was the learning machines and further > advanced in AI would be needed to solve the problem. This was from a > sense of the potential intractability of go. I could very well be > wrong. > > It's obvious that you could recreate a brain since it is made of a > finite amount of matter. So I have no mystical attachments to the game > of go. I just think we have not proven yet that number crunching > methods are viable alone. A more heuristic approach could still be > needed. Mogo does use MC methods to play.. but it does have a few > heuristics to help judge important trees. Will number crunching > methods be enough alone... or will there be a need for much stronger > heuristics to trim the tree? I don't think we know yet. > > > > > > > ___ > 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: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
On Sun, Aug 10, 2008 at 3:46 PM, Robert Waite <[EMAIL PROTECTED]>wrote: > Okay.. so where is the paper that correlates the speed at which MCwUCT > approaches perfect play with the ability to play a human? They seem > unrelated as of yet. > The closest I've seen are these two studies Don made: http://cgos.boardspace.net/study/ http://cgos.boardspace.net/study/13/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
On Sun, 2008-08-10 at 15:19 -0400, Robert Waite wrote: > > Hmm.. I dunno.. I think there are a lot of ideas floating around but > some miscommunications. > > So the aim is to devise a computer that will beat the strongest human > players of go. > > I hear that "Monte-Carlo with UCT is proven to be scalable to perfect > play". It seems that this is essentially saying... that as the sample > size for this technique grows to infinity.. you will approach the > accuracy an algorithm that has solved go (in the sense that 5x5 was > solved)... kind of like creating the entire game tree. That this curve > approaches perfect play as you increase the samples to infinity. Same > goes for drawing out the entire game tree. It just seems that MCwUCT > is a lot easier. > > This however speaks nothing about the rate at which it approaches > perfect play as you increase the sample size. I didn't see anything in > the papers I have read about this. Which brings us to what our aim > is.. and that is to beat human players at go. Nothing has been proven > yet about practical scalability... which is what we would like. I don't know how you can say that. The empirical evidence is overwhelming that this is scalable in a practical way but more importantly it's been PROVEN to be scalable. If you throw the word "practical" in there then you are no longer talking the language of mathematics, theory and proofs so please don't ask for a "proof" of "practical" scalability, it makes no sense. > Scalable in the sense of approaching infinity alone does not prove > that it is not intractable. MC will never "solve" the big board in a "practical sense." We are of course talking about the issue of scalability in a practical game improving sense. You can't have it both ways - the tool we use to predict performance is an understanding of it's scalability properties. That has been proven but you want to say it's not relevant and that we have no way to estimate it's chances against humans. But we DO have a way to get a rough estimate. I think many just don't want to believe that it's possible to beat a human - their brains cannot get used to the idea that it will probably happen within their lifetime. > And it was said that the Mogo devs said that a double-strength version > beats the other one with 63%. As they mentioned... ideally... this > would mean about 30 years. But there could be a point of diminishing > returns as it relates to beating a human. There clearly is diminishing returns, even at very weak levels but you probably cannot measure it.I think it's very likely that the diminishing returns curve will be very very gradual for a long time to come, well beyond the point of achieving the top human levels. I believe for many this is a matter of credulity. It was like this in chess, we could not accept the possibility that computers could really get that good. And in GO we are so far away still that our brains have to make up reasons why it can't happen. When our realities don't match our belief systems, we balk. But you can look at it another way - humans are not that good at the game. Compared to you and I, they may seem like god's, but they are fallible and weak in the perfect game sense. Grandmasters in chess, in many ways fell from grace when it became necessary to play odds matches with computers in order for them to have a chance. When I was a boy reading chess books I practically worshiped these immortal masters of chess. The computers now expose their errors all the time, they are just humans and are no different from you and I, they just play a few hundred ELO stronger.If you take them off the pedestal, you can think more rationally about it. - Don > > When you say that is it proven scalable to perfect play... it is like > saying that we know that if you create every possible game... and have > a database that can access it well... you can get to perfect play. > This does not help us actually do it. > > ___ > 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: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
It's the tree search part where everything is happening. Eventually, enough of the tree is explored to find a win or prove a loss. - Don On Sun, 2008-08-10 at 20:11 +0100, Raymond Wold wrote: > Dan Andersson wrote: > > No more incredible than that Mini-Max and Alpha-Beta will generate > > perfect play given enough resources. In the worst case MC/UCT will build > > a Mini-Max tree solving the game. > > I've not looked very well at how UCT works, but surely this depends on > the randomness of the MC? What if by some bizarre coincidence the source > of random bits gives all 1's? What if it's pseudo-random, and interferes > with itself so some paths are never investigated? > > Or are you stipulating not just a good random source, but one which > sooner or later enumerates all possibilities? > ___ > 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: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
Dan Andersson wrote: No more incredible than that Mini-Max and Alpha-Beta will generate perfect play given enough resources. In the worst case MC/UCT will build a Mini-Max tree solving the game. I've not looked very well at how UCT works, but surely this depends on the randomness of the MC? What if by some bizarre coincidence the source of random bits gives all 1's? What if it's pseudo-random, and interferes with itself so some paths are never investigated? Or are you stipulating not just a good random source, but one which sooner or later enumerates all possibilities? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
Robert Waite skrev: 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. No more incredible than that Mini-Max and Alpha-Beta will generate perfect play given enough resources. In the worst case MC/UCT will build a Mini-Max tree solving the game. /Dan Andersson ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
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 usin
Re: [computer-go] Re: Strength of Monte-Carlo w/ UCT...
Robert Waite skrev: * > 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. MC/UCT is provably scalable up to perfect play. /Dan Andersson 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 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/
