[computer-go] Technical Report on MoGo
Hello all, as perhaps some of you may be interested, I give here a link to a technical report about MoGo. You can find there a lot of details about the ideas around MoGo. While we tried to be as clear as possible, some details may lack. There is still no "number" on this report, but this will come in a few days. http://hal.inria.fr/inria-00117266 I would like to thank of course all the authors, but also Rémi Coulom who shared a lot of details about CrazyStone and his ideas. I also would like to thank all the contributors in this list for interesting discussions. Now my feeling is that the "improving random simulations" part of this work is promising. We have only done very few steps in this direction, and it gives quite convincing results. It was what I meant in the "random distribution" discussions we have in this list. I am pretty sure that making improvements in this direction would increase a lot the level of MC players even (or especially) in 19x19. And this can be done very soon (well, perhaps not before sunday :)). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Making Java much faster
On 1, Dec 2006, at 6:15 AM, Wodzu wrote: - Original Message - From: "David Doshay" <[EMAIL PROTECTED]> Also, my data shows that if I doubled the time allowed for playing, thus "using" the time gained from faster execution for doing deeper lookahead, the results did not improve, but actually got worse. I've also noticed that when i run my engine to play itself on different depth level. The "deeper" player sometimes was defeated by his opponent with lesser depth analysis. I guess he wasn't able to fidna good move because of the horizon effect. In self-play, I find deeper always has a greater win rate. I only look at statistics over many games. Of course, individual games go both ways. Although I think when you run your engine with some more depth it will vipe out its opponent from board;) Nope, the effect is clear. If the lookahead is too deep against a different engine (Many Faces of Go) then there is a lower win rate than a less deep lookahead. It just does not help to base evaluation upon boards that never occur. I have checked lookaheads of 0, 2, 4, 6, 8, and 16 against GNU Go (same engine and thus a very high hit rate on the lookaheads), and 0, 2, 3, 4, 6, 8, and 16 against Many Faces, where the game usually branches from the paths that SlugGo checks by the 4th move. Cheers, David ___ 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: [spam probable] Re: [computer-go] Monte-Carlo is the future of 19x19
> 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? s. Want to start your own business? Learn how on Yahoo! Small Business. http://smallbusiness.yahoo.com/r-index ___ 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: [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’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 of19x19
On Fri, 2006-12-01 at 08:39 -0800, David Fotland wrote: > What's included in an evaluation? Is each evaluation one random game, or a > set of random games that gives good enough statistics about the value of a > position? When you say "random" it conjures up images of aimless wandering - but the monte carlo programs are not really random in that sense - they are directed. The statistical terminology is that that are not "uniformly random" as with a good random number generator for instance. But they do start off that way - as they gain information they apply that information to bias the randomness towards good moves in a purposeful directed way. And the process continues to feed back on itself.The method is powerful enough that it produces perfect play eventually. A full width global search also produces perfect play but it's not concerned with the quality of the moves it searches - it searches everything no matter how awful it is (subject of course to alpha/beta cutoffs.) There is no reason whatsoever to avoid other techniques to improve the process. The judicious application of patterns could focus the search even more.Any time you can insert knowledge effectively it should be done because as you yourself have hinted at, a little knowledge can save a lot of searching and it would be stupid not to take advantage of that fact. But it's equally stupid to ignore search completely. - Don > David > > > 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. > > > 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 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: [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 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 of19x19
Each evaluation is one random game. Sylvain > What's included in an evaluation? Is each evaluation one random game, or a > set of random games that gives good enough statistics about the value of a > position? > > David > > > 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. > > > > 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 of19x19
What's included in an evaluation? Is each evaluation one random game, or a set of random games that gives good enough statistics about the value of a position? David > 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. > 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] Making Java much faster
- Original Message - From: "David Doshay" <[EMAIL PROTECTED]> To: "computer-go" Sent: Thursday, November 30, 2006 11:44 PM Subject: Re: [computer-go] Making Java much faster I have been *so* tempted to either ignore this thread or rename it ... On 30, Nov 2006, at 10:36 AM, Wodzu wrote: i think speed is one of most important things beacuse it affects strength of the program ;) (if the time for move is restricted) anyway, chosing a proper (fastest) algorithm has crucial meaning and other things like language, used data structures and so on, have less meaning in improving speed. thats my opinion, regards. This is not my experience at all. SlugGo was first written by a graduate student with data structures that made sense to them, but not to me. I rewrote it to use completely different data structures but with exactly the same algorithm. It took less than half the time to run, and play was at exactly the same level because it was move for move identical. Data structures can have tremendous effect upon speed. If you think about linked-lists, hash tables, priority queues as a data structures than you ofourse have right. However those strutures are realized by certain algorithms on their implementation level. I shoul dbe more precise because I meant data typers or primitive data structures like arrays. Also, my data shows that if I doubled the time allowed for playing, thus "using" the time gained from faster execution for doing deeper lookahead, the results did not improve, but actually got worse. I've also noticed that when i run my engine to play itself on different depth level. The "deeper" player sometimes was defeated by his opponent with lesser depth analysis. I guess he wasn't able to fidna good move because of the horizon effect. Although I think when you run your engine with some more depth it will vipe out its opponent from board;) Regards, Wodzu ___ 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 of19x19
Le Vendredi 01 Décembre 2006 11:57, Chrilly a écrit : > > 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. > > If one assumes 300 moves/Plies on 19x19 it would be about 330 KNodes/sec? No, that just mean 1100 Nodes/sec in 19x19. When I meant 1 evaluation, I meant 1 random simulation. For me, 1 position=1node=1random simulation. Sorry I don't see exactly why you are multiplying by 300, but I think now we understand each other :). 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 of19x19
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. If one assumes 300 moves/Plies on 19x19 it would be about 330 KNodes/sec? Chrilly ___ 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
Le vendredi 1 décembre 2006 06:24, Don Dailey a écrit : > > 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. > http://trac.gnugo.org/gnugo/ticket/10 This is a terrible real game, and the end become rather complicate (due to GNU Go kindness, of not killing something earlier ;) 9 groups involved in a semeai, but w resist with local seki, so a good order is needed for a kill cascade. Move 354 is probably the last losing move for B (i dont rememebr precisely) w can win even if he loses part of his stones, only one sequence of kill gives victory for B. (the easiest one started on top left, but gg wasted it) As order of moves is important, i guess MC programs would have hard time with this. result : B all dead with 9 handi on 19x19 board ! Alain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Monte-Carlo is the future of 19x19
Le Vendredi 01 Décembre 2006 08:48, Chrilly a écrit : > > 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? Hello, if you are interested you can find some information there: - http://senseis.xmp.net/?MoGo - http://www.lri.fr/~gelly/MoGo.htm In the second link there are the names of the contributors, while the developpers are the two first. 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
Hello, > 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. It is not what we said. At least it is not what I meant, and I think it is true for the others. > 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. 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. 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
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/
