RE: [computer-go] Monte-Carlo is the future of 19x19
Hi David, Since I made my last post to you, several people have responded. They have made my point and I agree with your point. It's foolish not to take advantage of domain specific information and nothing prevents a monte carlo program from doing that as you can see. Having said that, I have pretty much a pure Monte Carlo program (not pure but pure in the sense that it has no go knowledge) and although it does pretty well on CGOS, it has fallen far behind Mogo and others which use domain specific knowledge. Mogo of course uses a lot some pattern knowledge. If you read their paper, you will see that they are applying this to 19x19 GO and this program seems to be relatively strong although perhaps not the best. - Don On Thu, 2006-11-30 at 22:18 -0800, David Fotland wrote: I agree with you that knowledge engineering is diminishing returns. I don’t think that adding more knowledge to existing programs will make them strong any time soon. But there is a lot of simple basic useful knowledge, like counting liberties, and it seems to me that the monte-carlo enthusiasts are ignoring this. My point with the file I attached is not that it's a difficult position. These fights are incredibly easy if you just add a few dozen lines of code to count liberties correctly. To me it's as if a weak chess player says, my program doesn’t need to understand basic pawn structure evaluation. It looks really complicated. I'll just search faster than you. There is some basic knowledge that is not complex and is very useful. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [spam probable] Re: [computer-go] Monte-Carlo is the future of 19x19
Hello, On 11/30/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: To give an idea of the scale (at least for MoGo), 70k simulations/move (with the best parameters) against gnugo 3.6/level 8 gives 89% in 9x9, 68% in 13x13, 32% in 19x19. This is still not assessment of scalability. Each of those 70k simulations takes longer for larger board sizes. Yes of course. But also gnugo takes more time in larger board size. Futhermore in 19x19 games you have more time to play. Anyway gnugo always takes far less time that MoGo, but when allowing more time to gnugo it does not improve so well. We are not talking about blitz are we? Of course in blitz games, gnugo is unbeatable. I think what is important is the level you reach with a reasonable game time. Do you have these numbers for x seconds per move? At the very beginning we were experimenting using seconds/move. They are some issues doing that. First it depends on the speed of your computer, so difficult to compare when doing experiments in different computers. Second it depends on the optimisation. It is far simpler to come up with an idea, implement it badly (without optimisation), see if it improves with the same nb of simulations, and then think about optimisation (if possible). Of course this holds only if after optimisation the evaluation takes a time comparable without the idea. On a P4 3.0Ghz mono processor, the number of evaluations per seconds is in the order of 4500/s in 9x9, 2500 in 13x13 and 1100 in 19x19. Or mirroring Gnu-Go's thinking time? No, gnugo plays far faster. I already discuss that above. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Monte-Carlo is the future of 19x19
It is not what we said. At least it is not what I meant, and I think it is true for the others. I was reacting to the two statements below. I didn't realize that this opinion was not generally shared by the people developing monte carlo programs. I believe that MC will be the only way to write a GO program in the near future leaving the other stuff in the dust I predict that in one year or two, classical programs will be far behind MC programs on 19x19. Maybe it will take less than one year. I think there is sometimes a misunderstanding of what Monte-Carlo is. Monte-Carlo is a method to approximate an expectation using a finite sample of randomly drawn points. No more, no less. It does not talk about stupidity, especially it does not specify the distribution against which you are computing your expectation. If the distribution is pro players playing against themselves, MC with 3 simulations per move and one ply search will crush the best human player by far. I understand the definition of Monte Carlo. But when people talk about Monte Carlo go, they mean programs that evalutate random games, not professional games. You are making the same point I made. What I meant to say is that using random games and an evaluation that only understands final scores will not make a strong go program. There needs to be some knowledge in the evaluation making the games examined non-random. There are fights in 19x19 games that need a little knowledge to evaluate. Random game monte carlo isn't enough. David Sylvain ___ 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] Monte-Carlo is the future of 19x19
I understand the definition of Monte Carlo. But when people talk about Monte Carlo go, they mean programs that evalutate random games, not professional games. To be completely precise, professional games are also random games (if it was not, all games between two players would always be the same). random does not mean uniformly. Even deterministic players are random (P=1 for one move, and 0 for all the others). I know that you know that, it is only to be precise on the terms used. You are making the same point I made. What I meant to say is that using random games and an evaluation that only understands final scores will not make a strong go program. There needs to be some knowledge in the evaluation making the games examined non-random. There are fights in 19x19 games that need a little knowledge to evaluate. Random game monte carlo isn't enough. Here, I am not sure about the meaning of random for you. I think I disagree with the statement an evaluation that only understands final scores will not make a strong go program depending on what you mean by random. Perhaps we are making the same points, perhaps not :). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [spam probable] Re: [computer-go] Monte-Carlo is the future of 19x19
Quoting [EMAIL PROTECTED]: Also, there are a lot to improvements to do in MC in a quite short term, so I share the point of view of Rémi, Don and some others when saying that MC programs will fill the gap with classical programs in 19x19. And this can be soon. Now, it is the work of the classical approach developers to make us wrong :). I can just add that I just started to add pattern matching to Valkyria. It is too early to make any promises but I am certain that I will improve Valkyria a lot on 19x19. Depending on what you use patterns for it is ortogonal to MC itself, that is any benefits classic approach programs have thanks to pattern matching should also apply to MC programs. And there are perhaps aspects of MC programs that can be improved with patterns that are unique to MC search as well. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo is the future of 19x19
I think I disagree with the statement an evaluation that only understands final scores will not make a strong go program depending on what you mean by random. here i will interject by agreeing with the statement that an evaluation that only understands final scores will not make a strong go program. if (and perhaps no such go programs exist) one were to construct a go program that simply evaluated moves based upon the percentage of completely-played-out randomly chosen games attached to the given next move (or two, or whatever) that ended in a win for himself, then that would not be a strategy that one could expect to beat professional go players, or even to seriously challenge good existing software with equivalent hardware and time constraints within the stated, one year. s. Do you Yahoo!? Everyone is raving about the all-new Yahoo! Mail beta. http://new.mail.yahoo.com ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Monte-Carlo is the future of 19x19
Quoting David Fotland [EMAIL PROTECTED]: My point with the file I attached is not that it's a difficult position. These fights are incredibly easy if you just add a few dozen lines of code to count liberties correctly. To me it's as if a weak chess player says, my program doesn#8217;t need to understand basic pawn structure evaluation. It looks really complicated. I'll just search faster than you. There is some basic knowledge that is not complex and is very useful. I think we are having a confusion of what a MC-program can do or not do here. The strongest MC-programs does a lot of things of the type a few dozen lines of code, and without them they would be weak even on small boards. Valkyria does some tactical things that has improved its tactics considerably and there are much more to be done. On your position it insisted on resigning or passing depending on who played first so I have to look at that more carefully. In real games on small boards though it often handle semeais and ko fights surprisingly well. But it is probably true that in an artificial position with multiple sekis and semeais a search based strategy may fail becuase all local fight multiply many minor difficulties unless there is dedicated code which removes the need for search. Right now Valkyria has no code whatsoever that detects seki, so it is extremely vulnerable to such positions if it cannot be saved by shallow UCT-search. MC-programs are thus not necessarily void of hardcoded go knowledge. The trick is to find which knowledge should be added dependent on the tradeoff with speed. Almost everytime I add something slightly complex to Valkyria it becomes 5 percent slower and because of the scaling properties of MC-search such slowdowns have a large impact on the playing strength when they add up. So from my point of view I think I have found some easy ways to improve the playing strength a lot, but I reached the point where I cannot longer in advance predict that a new feature will actually make the program stronger, so it has become a process of many trials and many errors. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [spam probable] Re: [computer-go] Monte-Carlo is the future of 19x19
I think I disagree with the statement an evaluation that only understands final scores will not make a strong go program depending on what you mean by random. here i will interject by agreeing with the statement that an evaluation that only understands final scores will not make a strong go program. if (and perhaps no such go programs exist) one were to construct a go program that simply evaluated moves based upon the percentage of completely-played-out randomly chosen games In fact, I think we say the same thing, simply using different meaning for the same word. By random you mean uniformly random, and I don't mean that, I simply mean random (in the sense of random variable). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [spam probable] Re: [spam probable] Re: [computer-go] Monte-Carlo is the future of 19x19
Le Vendredi 01 Décembre 2006 21:26, steve uurtamo a écrit : In fact, I think we say the same thing, simply using different meaning for the same word. By random you mean uniformly random, and I don't mean that, I simply mean random (in the sense of random variable). what distribution is currently being used? In MoGo the distribution is clearly not uniform. I will send details to the list shortly for those who may be interested. In others I don't know. In the future, I believe in a very strongly non uniform distribution. I may even say that it is my strongest belief for the future of MC. Of course, I can be proved to be wrong very soon... Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo is the future of 19x19
No, you can't test it that way. The thing with monte carlo is the discovery and then very rapid progress of it. Even 2 years ago they were not very good compared to what they are now.I haven't seen that in My statement was about a way forward - I'm not saying they are currently much better although this may already be the case with 9x9. - Don On Thu, 2006-11-30 at 16:58 -0500, Chris Fant wrote: Can't you test that today by giving an MC go program twice as much thinking time as the classical program? On 11/30/06, Rémi Coulom [EMAIL PROTECTED] wrote: Chrilly wrote: I believe that MC will be the only way to write a GO program in the near future leaving the other stuff in the dust (like Mogo has with 9x9 Monte Carlo Go.)This happened in computer chess several times, someone came up with some breakthrough idea, proved it with actual results and everyone else had to play follow the leader to catch up. Do you think its also the future of 19x19 or only of 9x9 (maybe 13x13)? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ I am certain it is for 19x19. Just look at the KGS games of Mogo on 19x19. I played one game against it, and won. I got the feeling it was slightly easier to beat than GNU Go, but that may be because I am used to the way Monte-Carlo programs play. I predict that in one year or two, classical programs will be far behind MC programs on 19x19. Maybe it will take less than one year. Rémi ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo is the future of 19x19
I believe that MC will be the only way to write a GO program in the near future leaving the other stuff in the dust ... ... I am certain it is for 19x19. Just look at the KGS games of Mogo on 19x19. I played one game against it, and won. I got the feeling it was slightly easier to beat than GNU Go, but that may be because I am used to the way Monte-Carlo programs play. I predict that in one year or two, classical programs will be far behind MC programs on 19x19. Maybe it will take less than one year. Are there any details, or publications, on what Mogo is doing at 19x19? I'd thought consensus opinion here was that monte carlo scaled to 19x19 badly. Darren ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Monte-Carlo is the future of 19x19
How does monte carlo go do with fights that are trivial to evaluate, but hard to search? The attached position (I think from Martin Mueller), has many such fights. If your program can count liberties correctly, it is easy to evaluate and choose the best move with 1 ply lookahead. If you try to do a full board search for the best move it will take 50 ply or more. This position has a large number of big fights where the side to move wins the local fight. I think smart evaluation beats dumb search, monte carlo or otherwise. David -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Doshay Sent: Thursday, November 30, 2006 3:49 PM To: computer-go Subject: Re: [computer-go] Monte-Carlo is the future of 19x19 I think that MC will be useful on 19x19 if a clever way to restrict it to sub-game searches can be implemented. Cheers, David On 30, Nov 2006, at 1:51 PM, Rémi Coulom wrote: Chrilly wrote: I believe that MC will be the only way to write a GO program in the near future leaving the other stuff in the dust (like Mogo has with 9x9 Monte Carlo Go.)This happened in computer chess several times, someone came up with some breakthrough idea, proved it with actual results and everyone else had to play follow the leader to catch up. Do you think its also the future of 19x19 or only of 9x9 (maybe 13x13)? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ I am certain it is for 19x19. Just look at the KGS games of Mogo on 19x19. I played one game against it, and won. I got the feeling it was slightly easier to beat than GNU Go, but that may be because I am used to the way Monte-Carlo programs play. I predict that in one year or two, classical programs will be far behind MC programs on 19x19. Maybe it will take less than one year. Rémi ___ 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/ semeai1.sgf Description: Binary data ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Monte-Carlo is the future of 19x19
On Thu, 2006-11-30 at 18:40 -0800, David Fotland wrote: How does monte carlo go do with fights that are trivial to evaluate, but hard to search? It's easy to construct problems that any program cannot handle including yours. You have to understand that Monte Carlo is not great at tactics, it's search is a kind of meta-search designed to understand the general course of the game. It's ok at basic tactics but that is not it's forte. (Although I believe programs like Mogo have gone a long way towards correcting this type of weakness.) I've watched a lot of games between my own weak monte carlo program and gnugo - and sometimes it loses to tactics. But other times it makes gnugo look stupid, as if it just layed down and died. And it's because my program actually understood the position better. If it gets into a fight that requires careful accurate calculation, gnugo is better because it does more searching. The attached position (I think from Martin Mueller), has many such fights. If your program can count liberties correctly, it is easy to evaluate and choose the best move with 1 ply lookahead. If you try to do a full board search for the best move it will take 50 ply or more. This position has a large number of big fights where the side to move wins the local fight. I think smart evaluation beats dumb search, monte carlo or otherwise. I believe this is a meaningless statement because evaluation is the only important thing - that part is well understood. Search is just a way to gain knowledge and knowledge is what we are lacking and we all agree on this. In fact search IS evaluation. I can't understand why people think a program has to either search or evaluate. The only thing any program does is evaluate and that's all there is.I used to call my search routine eval() because that's all it is. I know you understand this too - I think you are just trying to pick a fight. Your program has a global search and local searches presumably because it helps your program evaluate positions right? My position is that knowledge engineering is at a steep point of diminishing returns. How much improvement do you think you will gain with a few more years of adding more patterns?Are you expecting major breakthroughs which will allow you to reduce the searching that you do now? Intuitively it's easy to criticize how stupid the programs are and come to the simple conclusion that they need to understand a lot more - and rightly conclude that this will make them much better - but apparently this is incredibly difficult. There is no breakthrough that promises to substantially improve this situation with static evaluation. I don't think a few more patterns is going to cut it either. The answer will have to be more sophisticated evaluation and that means you will have to slow your evaluation down substantially by using recursion - a search.There is no law against trying to apply knowledge to the search either and is what has been happening in computer chess for years. Almost all the breakthroughs have been about being smarter and most of them have been about being smarter about what you search. At some point you won't be able to pack much more static knowledge into your program if you refuse to think about what the opponent can do, how you might respond, etc.There is nothing dumb about this. - Don David -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Doshay Sent: Thursday, November 30, 2006 3:49 PM To: computer-go Subject: Re: [computer-go] Monte-Carlo is the future of 19x19 I think that MC will be useful on 19x19 if a clever way to restrict it to sub-game searches can be implemented. Cheers, David On 30, Nov 2006, at 1:51 PM, Rémi Coulom wrote: Chrilly wrote: I believe that MC will be the only way to write a GO program in the near future leaving the other stuff in the dust (like Mogo has with 9x9 Monte Carlo Go.)This happened in computer chess several times, someone came up with some breakthrough idea, proved it with actual results and everyone else had to play follow the leader to catch up. Do you think its also the future of 19x19 or only of 9x9 (maybe 13x13)? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ I am certain it is for 19x19. Just look at the KGS games of Mogo on 19x19. I played one game against it, and won. I got the feeling it was slightly easier to beat than GNU Go, but that may be because I am used to the way Monte-Carlo programs play. I predict that in one year or two, classical programs will be far behind MC programs on 19x19. Maybe it will take less than one year. Rémi
Re: [spam probable] Re: [computer-go] Monte-Carlo is the future of 19x19
On 11/30/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: To give an idea of the scale (at least for MoGo), 70k simulations/move (with the best parameters) against gnugo 3.6/level 8 gives 89% in 9x9, 68% in 13x13, 32% in 19x19. This is still not assessment of scalability. Each of those 70k simulations takes longer for larger board sizes. Do you have these numbers for x seconds per move? Or mirroring Gnu-Go's thinking time? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] Monte-Carlo is the future of 19x19
It's easy to construct problems that any program cannot handle including yours. Of course, but understanding fights like the attached ones is essential to strong play on 19x19. You have to understand that Monte Carlo is not great at tactics, I do understand this. That's my point :) I can't understand why people think a program has to either search or evaluate. The only thing any program does is evaluate and that's all there is.I used to call my search routine eval() because that's all it is. I agree with you. Strong programs have to search, and they also need knowledge in the evaluation. All knowledge and no search is just as bad as no knowledge and deep search. I know you understand this too - I think you are just trying to pick a fight. I'm not trying to pick a fight. I was responding to a bunch of people who think that really fast random search with a stupid evaluation will crush traditional programs next year. Monte carlo has a place in go programs, and is a very useful technique, but I dont think it can make a strong program all by itself. My position is that knowledge engineering is at a steep point of diminishing returns. How much improvement do you think you will gain with a few more years of adding more patterns?Are you expecting major breakthroughs which will allow you to reduce the searching that you do now? I agree with you that knowledge engineering is diminishing returns. I dont think that adding more knowledge to existing programs will make them strong any time soon. But there is a lot of simple basic useful knowledge, like counting liberties, and it seems to me that the monte-carlo enthusiasts are ignoring this. My point with the file I attached is not that it's a difficult position. These fights are incredibly easy if you just add a few dozen lines of code to count liberties correctly. To me it's as if a weak chess player says, my program doesnt need to understand basic pawn structure evaluation. It looks really complicated. I'll just search faster than you. There is some basic knowledge that is not complex and is very useful. -David - Don David -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of David Doshay Sent: Thursday, November 30, 2006 3:49 PM To: computer-go Subject: Re: [computer-go] Monte-Carlo is the future of 19x19 I think that MC will be useful on 19x19 if a clever way to restrict it to sub-game searches can be implemented. Cheers, David On 30, Nov 2006, at 1:51 PM, Rémi Coulom wrote: Chrilly wrote: I believe that MC will be the only way to write a GO program in the near future leaving the other stuff in the dust (like Mogo has with 9x9 Monte Carlo Go.)This happened in computer chess several times, someone came up with some breakthrough idea, proved it with actual results and everyone else had to play follow the leader to catch up. Do you think its also the future of 19x19 or only of 9x9 (maybe 13x13)? Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ I am certain it is for 19x19. Just look at the KGS games of Mogo on 19x19. I played one game against it, and won. I got the feeling it was slightly easier to beat than GNU Go, but that may be because I am used to the way Monte-Carlo programs play. I predict that in one year or two, classical programs will be far behind MC programs on 19x19. Maybe it will take less than one year. Rémi ___ 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/ ___ 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/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo is the future of 19x19
Are there any details, or publications, on what Mogo is doing at 19x19? I'd thought consensus opinion here was that monte carlo scaled to 19x19 badly. Darren A very stupid question: What is Mogo, who has it written? Chrilly ___ 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/
