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/
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: [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
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 > > >
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] Making Java much faster
On 30, Nov 2006, at 4:47 PM, Unknown wrote: On Thu, 2006-11-30 at 14:44 -0800, David Doshay wrote: 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. To me, this just seems like horizon-effect in disguise. Once you exhaust your ability to evaluate, you cannot see through the fog. The horizon is dictated by the inability to evaluate correctly. (try fuzzing up the evaluation results by 0.01-1 stone just by adding some noise, to get my point. You will see the horizon come closer) Using multiple instances of gnugo to do the evaluation for you, still sticks you to the (#1) minimax+evaluation model, even if you apply the slave-gnugo processes only for "local" problems (not mentioning interactions, or how to identify subproblems) Having slave processes to do your tsumego- or MC-evaluations for you, still keeps you dependent on their evaluation noise. Adding CPU's wont help to beat the noise, IMHO. It just pushes your horizon upto the point where the fog hits you. This is the point where I would like to introduce a paradigm shift. But I cannot invent one, presently. HTH, AvK (#1) by "minimax", I mean minimax-variants, including alpha-beta. They are all the same. Well, I suppose that you could call anything that happens "out there" in the lookahead a horizon effect, but I do not see it that way in this case. Our ability to do a static board evaluation is not a function of how deep the lookahead is, but always is the same poor function. It really does simply come down to how often the opponent evaluates the board in a completely different way than we expect, and thus plays differently than we had checked in any of our lookahead branches. Our data is clear that if we correctly predict the opponent's moves we have a high win rate. I do share your desire , and so far your inability, to invent a new paradigm for programming Go. Cheers, David ___ 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 Thu, 2006-11-30 at 14:44 -0800, David Doshay wrote: > 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. > > 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. > To me, this just seems like horizon-effect in disguise. Once you exhaust your ability to evaluate, you cannot see through the fog. The horizon is dictated by the inability to evaluate correctly. (try fuzzing up the evaluation results by 0.01-1 stone just by adding some noise, to get my point. You will see the horizon come closer) Using multiple instances of gnugo to do the evaluation for you, still sticks you to the (#1) minimax+evaluation model, even if you apply the slave-gnugo processes only for "local" problems (not mentioning interactions, or how to identify subproblems) Having slave processes to do your tsumego- or MC-evaluations for you, still keeps you dependent on their evaluation noise. Adding CPU's wont help to beat the noise, IMHO. It just pushes your horizon upto the point where the fog hits you. This is the point where I would like to introduce a paradigm shift. But I cannot invent one, presently. HTH, AvK (#1) by "minimax", I mean minimax-variants, including alpha-beta. They are all the same. ___ 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
Le Vendredi 01 Décembre 2006 00:20, Darren Cook a écrit : > >>> 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? There will be a technical report shortly (if everything works fine). There is no all the very recent ideas (yet to be written...), but the main ideas are there. Most of them are not specific to 19x19, some are. > I'd thought consensus opinion here was that monte carlo scaled to 19x19 > badly. Yes monte carlo scales badly, be the results are improving very quickly! 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. So well, we are still quite far from gnugo (and it is only 3.6, newest versions are certainly better). However, 2.5 months ago, MoGo in 19x19 were close to 0% against gnugo 3.6/level 8 in 19x19. So I think MC programs can fill the gap quite quickly. There is also an issue of time, because in 19x19, we are in the fast increasing part of the strength/time curve. I mean that in 9x9, we don't see so much improvement with more time, but in 19x19, with the time settings of next KGS tournament (28 minutes) (and the kgs games of MoGo are with this setting), MoGo can hardly do 70k sims/move at the beginning and has an average closer to 30k sims/move. With 30k sims/move, the winning rate against gnugo becomes only 16%! With games of 50 minutes, the level would be much closer to the one of gnugo. 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 :). 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 30, Nov 2006, at 3:46 PM, Eduardo Sabbatella wrote: David Doshay wrote: 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. Sorry for not adding nothing to usefull to the thread. But I found this comment very interesting and I would like emphasize it. Can you give us some details about it? This result happened when playing "less understood opponents," as opposed to play against GNU Go (SlugGo's base engine). I cannot be absolutely sure, but this is how we reasoned the result: In these cases, decisions made based upon the deeper lookahead were based upon boards of decreasing likelihood. A medium depth gave the best winning percentage. A plot of winning percentage against search depth clearly rose and then fell. Cheers, David ___ 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 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/
Re: [computer-go] Making Java much faster
> 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. Sorry for not adding nothing to usefull to the thread. But I found this comment very interesting and I would like emphasize it. Can you give us some details about it? __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ 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
Perhaps your comment is related to something i write before. I was not talking about the expressiveness of java language. In that sense, Ocaml, Lisp, SmallTalk are far, far away from Java. Java is a C (almost C++) with garbage collection, bound checking and variable initialisation. (its a lot more than that, but for our interest, that are the relevant things). That's all. It is not a pet, it just very handy not to have to take care about memory leaks, rebuild everything every time I change the "Board" class, and things like that. As stated before, the faster I can test new algos, the faster I will be able to find out something interesting. Later, I can implement it on C. > earlier - Java keeps > getting presented as some kind of high level > language than enables a > natural expression of ideas. This is total > garbage. Java is a low > level language and very much a C dialect. I don't > understand where > people are getting this - but I think it's because > it's their pet > language and they want to believe it's somehow extra > special.There > are no special languages. __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ 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
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] Making Java much faster
A few points about Java and speed etc. Java can rival C for speed, depending what you do with it. Unfortunately, really 'nicely' designed code can be significantly slower than code written specifically with efficiency in mind. I accept that in principle one should aim for clean and general code, but in practice this has to be sacrificed sometimes. For example, if you want speed then try to avoid any object creation in inner loops. You can test this using java -prof on your code. To put some figures on this, for some work we did evolving neural networks for Othello, the original generic version (where the Othello rules were a plug-in to a general board-game framework) achieved fewer than 10 games per second. After several refinements, sometimes to the code, sometimes at a much deeper algorithmic level, this was improved to around 1500 games per second. But the resulting code was specific to Othello. A C version achieved around 1,000 games per second (without one of the algorithmic tricks of the Java version; we probably could have made the C version about 30% faster than the Java version if we'd put the effort in). Best regards, Simon Lucas Ps. This is mentioned in a bit more detail in our CIG 2006 paper, available on-line here: http://cigames.org -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Jeffrey Greenberg Sent: 30 November 2006 21:50 To: 'computer-go' Subject: RE: [computer-go] Making Java much faster I think this is a no-brainer... After 18 years with C/C++, I'd say use Java (or some other interpreted language) so you can focus on interesting stuff, and later perhaps you can come back to optimize some portion using a static compiled language (ie C++)... Cavest: 2x slower than C++ might be a significant disadvantage for loop-based algorithms... Ie If your algorithms are about iterative search, then speed might make the difference in a competition... But heck, are there any algorithms that aren't of the iterative type? Jeffrey Greenberg http://www.inventivity.com http://www.jeffrey-greenberg.com -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Peter Drake Sent: Wednesday, November 29, 2006 9:01 AM To: computer-go Subject: Re: [computer-go] Making Java much faster This is something we hope to do once we have Orego multithreaded: give each version the same amount of time, so the time costs of adding a heuristic are automatically taken into account. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 29, 2006, at 7:30 AM, Eduardo Sabbatella wrote: > >> Games are additionally hard-real-time problems. E.g. >> in the Orego tests but >> versions got the same amount of nodes. For a realistic comparision >> one has to give both sides the same time and not the same >> node-budget. > > What do you think about giving the same program different player > times? > > Perhaps its found that ELOs/time grow log/lineal/exp. > > Also, same program but with one feature disabled, same time. Does make > any sense? > > > __ > Correo Yahoo! > Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí > tu cuenta ya! - http://correo.yahoo.com.ar > ___ > 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] 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. 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. Cheers, David ___ 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
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/
Re: [computer-go] Making Java much faster
On Thu, 2006-11-30 at 21:26 +0100, 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 In my opinion, it is currently the best way to move forward at all board sizes. What is really interesting about it is the best first search aspect of it - very directed and focused.It's easy to gripe about perceived shortcomings, but it's difficult to present an alternative that doesn't have those same shortcomings. So at least for now I feel it's the most plausible way to move forward rapidly. I don't have a problem with combining it with other techniques such as the use of patterns and outside knowledge. Apparently this is what Mogo is doing. - Don ___ 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
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/
RE: [computer-go] Making Java much faster
I think this is a no-brainer... After 18 years with C/C++, I'd say use Java (or some other interpreted language) so you can focus on interesting stuff, and later perhaps you can come back to optimize some portion using a static compiled language (ie C++)... Cavest: 2x slower than C++ might be a significant disadvantage for loop-based algorithms... Ie If your algorithms are about iterative search, then speed might make the difference in a competition... But heck, are there any algorithms that aren't of the iterative type? Jeffrey Greenberg http://www.inventivity.com http://www.jeffrey-greenberg.com -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Peter Drake Sent: Wednesday, November 29, 2006 9:01 AM To: computer-go Subject: Re: [computer-go] Making Java much faster This is something we hope to do once we have Orego multithreaded: give each version the same amount of time, so the time costs of adding a heuristic are automatically taken into account. Peter Drake Assistant Professor of Computer Science Lewis & Clark College http://www.lclark.edu/~drake/ On Nov 29, 2006, at 7:30 AM, Eduardo Sabbatella wrote: > >> Games are additionally hard-real-time problems. E.g. >> in the Orego tests but >> versions got the same amount of nodes. For a >> realistic comparision one has >> to give both sides the same time and not the same node-budget. > > What do you think about giving the same program > different player times? > > Perhaps its found that ELOs/time grow log/lineal/exp. > > Also, same program but with one feature disabled, same > time. Does make any sense? > > > __ > Correo Yahoo! > Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí > tu cuenta ya! - http://correo.yahoo.com.ar > ___ > 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] Making Java much faster
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/
Re: [computer-go] Making Java much faster
Hi Jim, I feel similarly to you. I have to take exception to what someone posted earlier - Java keeps getting presented as some kind of high level language than enables a natural expression of ideas. This is total garbage. Java is a low level language and very much a C dialect. I don't understand where people are getting this - but I think it's because it's their pet language and they want to believe it's somehow extra special.There are no special languages. If they wanted to make an argument for an expressive language, then they would be hyping scheme, ocaml, lisp or something more exciting than C like languages. I personally don't feel the language really gets in the way that much. Ok, now about experimentation. I believe in spending a significant time looking for the breakthroughs. Most breakthroughs are not orders of magnitude of advancement, but they are simply wonderful discoveries that are clearly better than minor incremental things. For instance in chess it was things like "check extensions", a simple idea that was quite valuable and not seriously considered previously. Hash tables, null move pruning etc. They came one after another over several years. The latest rage is move reductions (although often it turns out that certain techniques have been used for years but not advertised or known - such as reductions.) I'm not that familiar with the very early days of computer go, but I would assume that the intelligent usage of "patterns" was a big deal when it was first discovered. The only other real breakthrough I can think of is clever local searches - but I might be corrected on this. But that's why I'm currently interested in Monte/Carlo. Right now it's the most promising way forward. That might change next year - but I don't see any long term future in tweaking patterns and doing more local searches to make incremental progress. 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. Time could prove me wrong - I have learned that humans have a short horizon view - we cannot accurately see much ahead of us. - Don On Thu, 2006-11-30 at 13:07 -0600, Jim O'Flaherty, Jr. wrote: > Wodzu, > > There are roughly two types of approaches to bettering the skill of > computer go solutions; incremental and breakthrough. I think for > incremental solutions, ones where lots of work results in small shifts > in better go playing performance, you are correct. Any optimizations > around execution speed will result in better go playing performance per > time-unit. This is important if the measurement is winning current > computer_go competitions. > > However, what I hear quite a few people saying is they are looking for > "breakthrough" types of go skill improvement, and more at the > application level as opposed to the individual lines of code. And to do > that, their needs around adaptability are more influential on their > primary constraint (personal time, not eventual execution speed). Their > focus is on being able to complete more experiments per personal time > unit with the hope of stumbling into a new "domain" where the go playing > performance takes an order of magnitude leap ahead. Once in the new > domain, the priorities for the person may shift back to incremental as > they begin to see what kinds of limits the new technique might provide. > This is where I am at personally. I am far more interested in > probability based techniques as opposed to perfecting tactics/fighting > strategies. I am very happy others are more interested in those areas. > It's a good match. > > There are short-term benefits to the incremental approach. However, it > likely has a much closer threshold of diminishing returns if one follows > the standard constraint reduction techniques, largest first, etc.. At > which point, all the optimizations start fighting with any attempts to > "change" and/or "expand" newer ideas, techniques and experiments in an > effort to continue making progress. Once one has prioritized code > execution speed optimizations as a root value in moving a system > forward, almost always there is a large loss in adaptability with the > eventual result being the person abandons the bulk of the previous code > base to essentially start from scratch. In many, if not most, cases, > the error persists in the new approach as the fixation on maximizing > execution speed remains too high resulting in a rapid pruning of > possible exploration options. > > There is no short answer to the Go problem. It is going to takes lots > of investment by both the code speed optimizers (incremental) and the > new technique inventor/innovators (breakthr
Re: [computer-go] Making Java much faster
Wodzu, There are roughly two types of approaches to bettering the skill of computer go solutions; incremental and breakthrough. I think for incremental solutions, ones where lots of work results in small shifts in better go playing performance, you are correct. Any optimizations around execution speed will result in better go playing performance per time-unit. This is important if the measurement is winning current computer_go competitions. However, what I hear quite a few people saying is they are looking for "breakthrough" types of go skill improvement, and more at the application level as opposed to the individual lines of code. And to do that, their needs around adaptability are more influential on their primary constraint (personal time, not eventual execution speed). Their focus is on being able to complete more experiments per personal time unit with the hope of stumbling into a new "domain" where the go playing performance takes an order of magnitude leap ahead. Once in the new domain, the priorities for the person may shift back to incremental as they begin to see what kinds of limits the new technique might provide. This is where I am at personally. I am far more interested in probability based techniques as opposed to perfecting tactics/fighting strategies. I am very happy others are more interested in those areas. It's a good match. There are short-term benefits to the incremental approach. However, it likely has a much closer threshold of diminishing returns if one follows the standard constraint reduction techniques, largest first, etc.. At which point, all the optimizations start fighting with any attempts to "change" and/or "expand" newer ideas, techniques and experiments in an effort to continue making progress. Once one has prioritized code execution speed optimizations as a root value in moving a system forward, almost always there is a large loss in adaptability with the eventual result being the person abandons the bulk of the previous code base to essentially start from scratch. In many, if not most, cases, the error persists in the new approach as the fixation on maximizing execution speed remains too high resulting in a rapid pruning of possible exploration options. There is no short answer to the Go problem. It is going to takes lots of investment by both the code speed optimizers (incremental) and the new technique inventor/innovators (breakthrough) and an effective integration of both before we see result substantially superior to what we experiencing right now. Personally, I have been enjoying the discussions around the progress being made on the UTC/Monte Carlo techniques. I am eager to start playing in that domain. Jim Wodzu wrote: Huh, why not use Pascal? It has speed of C and simplicity of Java :) heck, you could use perl. plenty of packages available (it can even be made multithreaded!), shared memory packages, etc. i mean, if speed isn't your top concern... 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. ___ 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
Huh, why not use Pascal? It has speed of C and simplicity of Java :) heck, you could use perl. plenty of packages available (it can even be made multithreaded!), shared memory packages, etc. i mean, if speed isn't your top concern... 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. ___ 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
C++ should be good. But take it with double care. I would code a lot of unit tests. If test driven development is followed, I suppose it will be a good piece of software, and, at the end of the day, a pro product. Test Driven Development, regression tests, profilling, code coverage, I would apply all that techniques to make it stable and solid. Java is a good alternative for testing algorithms, fast development, etc. But, I'm not sure at all, but I feel that a pro engine will never ends as a Java application. Perhaps, if you find out the way, you can use Java as a test bench, then code the final version on C++. Find out the way, in the sense of not adding a lot of overhead to maintain it. My 2 cents. --- Oliver Lewis <[EMAIL PROTECTED]> escribió: > Please go back to Java! Part of your initial aims > were to make good, well > commented code available to others. I was dismayed > when you started to > transition to C++, which may be the right choice if > you're working on your > own and happy to trade clarity / portability for > speed, but really detracts > from your other aims. Given you've got interns and > others coming in and out > of the project, I would have thought this would end > up being less > efficient. We're so far from strong amateur play in > Computer Go that it > seems much more important (and interesting) to focus > on implementing and > testing new ideas. > > ___ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ __ Correo Yahoo! Espacio para todos tus mensajes, antivirus y antispam ¡gratis! ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar ___ 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
> Huh, why not use Pascal? It has speed of C and > simplicity of Java :) heck, you could use perl. plenty of packages available (it can even be made multithreaded!), shared memory packages, etc. i mean, if speed isn't your top concern... 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] Making Java much faster
Orego version 3.03, described in the paper and available at the Orego web site, is in C++. However, we are finding C++ an exceedingly frustrating language to work in. I won't go into the details here -- we don't need another language war -- but suffice it to say that it seems like we're spending a lot of time messing with details that aren't of interest for the research. Now that I've found that Java can have speed within a factor of 2 of C++, I'm thinking of going back to Java. Huh, why not use Pascal? It has speed of C and simplicity of Java :) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Igo Dojo (Nemesis).
I purchased this wonderful unit, the first handheld PC-based Go game, after it was introduced by Toyogo a number of years ago. Price was about $400. I used it for a few hours, then put it back in its box & stored it away for the future. I am now interested in selling it but can find no after-market information for this product on the Net. If anyone has any information or interest, polease contact me direct. Thanks! Jack - Everyone is raving about the all-new Yahoo! Mail beta.___ 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
Please go back to Java! Part of your initial aims were to make good, well commented code available to others. I was dismayed when you started to transition to C++, which may be the right choice if you're working on your own and happy to trade clarity / portability for speed, but really detracts from your other aims. Given you've got interns and others coming in and out of the project, I would have thought this would end up being less efficient. We're so far from strong amateur play in Computer Go that it seems much more important (and interesting) to focus on implementing and testing new ideas. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
