Re: [computer-go] GNU Go taking a very long time
Hello, my point was not to report this very long time thinking, which is very rare (a few over thousands of games) in level 16. It was more that GnuGo is already very strong in level 8, and incredibly fast. And putting it at a better level (like 16) does not improve its strength so much, so testing with level 8 is totally relevant. Cheers, Sylvain 2007/1/11, David Doshay [EMAIL PROTECTED]: We generally use level 10 or 12. We have found that very rarely on level 15 GG will run off into the weeds, never (longer than 24 hours) to make a move. This has also been reported by others at level 18. We have never seen this happen at level 10 or 12. Cheers, David On 10, Jan 2007, at 12:27 PM, Sylvain Gelly wrote: I did not measure the thinking time of GnuGo level 16, but it seems quite long, and some games (at least 1, I don't remember) never finish after a lot of hours. Perhaps it is just a bug :). ___ 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] Gnugo vs commercial programs
2007/1/11, Don Dailey [EMAIL PROTECTED]: 50 X speedup sound rather impressive but it's not that much. It's probably made go programs about 2 or 3 stones stronger over the few years that it took to get hardward 50X faster about what you would expect. But it is hardly that much. Current programs are hardly 2-3 stones stronger ythat those in erly nineties. And if you comapare back them I used Goliath on my 286 20 MHz computer and today I use GnuGo on my 2GHz Athlon. So in bit over decade decade computers got about 100 times faster maybe 2-3 times more effetc/cycle so almost 300 times faster. And gain in strength is about 2-3 stones. So 50 times faster is lot faster. It will take more than few years to come. It may not help that much. Obviously any speed gain will help MC type program but I doubt not too much. MC probably will not dominate computer go in next decade. I am pretty sure we need some new ideas still to make progress. And By Go I mean a game that is played on 19x19 board. I find playing on 9x9 boring and not really a same game. Petri Pitkänen -- Petri Pitkänen e-mail: [EMAIL PROTECTED] Phone: +358 50 486 0292 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
I still don't understand your point. Are you just trying to say computers have a long way to go to beat really strong humans? nope -- i'm saying that until extra time makes a measurable difference in the strength of a program, worrying about how much time a program spends on any particular activity (like winning or losing a game) is less important than worrying about the activity itself. s. Yahoo! Music Unlimited Access over 1 million songs. http://music.yahoo.com/unlimited ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
On Thu, 2007-01-11 at 09:30 +0100, Sylvain Gelly wrote: So GnuGo and commercial programs have been optimized to play strong in very few time. For them, long thinking time is simply not relevant. It is not the same goal. Hi Sylvain, What I'm saying is that the programmers don't realize their real goal is to make it play better with less time. They THINK their goal is to make it play pretty good in about 10 seconds or whatever their goal is. But the 2 things are conceptually the same due to Moores law. You know this is true because just take a commercial program written 10 years ago. It makes it's moves quickly playing on an ancient piece of hardware with hardly any memory. So those guys kept expanding their program to use more time. It's only semantics whether you say they were trying to make it play better faster, or better in the same amount of time. But they stumbled around a lot because they were not thinking in a scientifically logical way. They only thought in absolute terms - I have 10 seconds per move, what can I do?Obviously, they wanted to play as strong as they could in those 10 seconds. The goal of scalability is the same thing that has always been done, it's just a more intelligent and methodical way to think about the problem. What makes me laugh is that some programmers imagine it has never been about time - just strength as though it is a totally unrelated concept. You scalability experiments with Mogo shows what should be painfully obvious - it's all about what you can do in a given amount of time and it should be no surprise that you can do more with more time. I agree that Gnugo was written in an absolute non-scalable style. Why Gnugo does is continually upgrade from year to year.They are making their program scale in a painfully manual way. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
On Thu, 2007-01-11 at 04:18 -0800, steve uurtamo wrote: I still don't understand your point. Are you just trying to say computers have a long way to go to beat really strong humans? nope -- i'm saying that until extra time makes a measurable difference in the strength of a program, worrying about how much time a program spends on any particular activity (like winning or losing a game) is less important than worrying about the activity itself. Well then the time is now. Look at the Sylvain's post on the scalability of Mogo. - Don s. Yahoo! Music Unlimited Access over 1 million songs. http://music.yahoo.com/unlimited ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
Well then the time is now. Look at the Sylvain's post on the scalability of Mogo. if the improvement continues to hold with more doublings, that's great. i am perhaps under the misguided opinion that there are all kinds of structural reasons why the best 'scalable' programs can't arbitrarily be doubled (i.e. that memory and not time was a bottleneck). 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] Gnugo vs commercial programs - scalability
Since we can no longer count on doubling single-processor speed every 18 months, go programs will need to scale across multiple processors. Dual-core systems are common; a pair of duos can be had for $5K or so. IBM sells four dual-core processors in a single rackmount chassis, and can be expected to make four quad-cores available by the end of the year. Both Intel and AMD have announced multicore roadmaps. Less well-known processors, such as Sun's UltraSparc T1, have 8 cores and up to 32 simultaneous threads. Terry McIntyre - Original Message From: steve uurtamo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Cc: computer-go computer-go@computer-go.org Sent: Thursday, January 11, 2007 4:18:01 AM Subject: Re: [computer-go] Gnugo vs commercial programs I still don't understand your point. Are you just trying to say computers have a long way to go to beat really strong humans? nope -- i'm saying that until extra time makes a measurable difference in the strength of a program, worrying about how much time a program spends on any particular activity (like winning or losing a game) is less important than worrying about the activity itself. s. Yahoo! Music Unlimited Access over 1 million songs. http://music.yahoo.com/unlimited ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ 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] Gnugo vs commercial programs
On Thu, 2007-01-11 at 07:40 -0500, Don Dailey wrote: Of course there is some questions about how long Moore's law will hold. If you are referring to CPU speed doubling (as opposed to transistor count), then that has been over for at least 5 years. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software http://www.gotw.ca/publications/concurrency-ddj.htm The problem is that concurrency doesn't scale well. -Jeff ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
I am currently working with different pruning methods for 19x19 go. What worked for Valkyria on 9x9 become much to slow on 19x19 where full board evaluation of several 100 moves simply does not work. During christmas I was able to prune the number of candiate moves to perhaps a factor 4-20 depending on the stage of the game. It now starts to play much better with a minute per move, but I did an experiment where I let have 10 minutes per move (it took several days to play that game) and for some moves I let it think for an hour. It was 9 handicap game and when it resigned it was only losing with 4.5 points. One game does not prove anything, but it showed that my MC implementation has the potential as long as it become more efficient. That is by better move pruning methods and faster hardware. And improvements to the main algorithms of the progam should of course also make a difference. I have said this before but I repeat my point here that is that MC programs cannot just be moved from 9x9 to 19x19 right away. It will take a lot of new ideas, but eventually I think really strong programs are possible even on present hardware, and these programs will of course scale very wll on 19x19. It is my impression that scalability might even be better on 19x19 than for 9x9. Quoting Sylvain Gelly [EMAIL PROTECTED]: 2007/1/11, steve uurtamo [EMAIL PROTECTED]: Well then the time is now. Look at the Sylvain's post on the scalability of Mogo. if the improvement continues to hold with more doublings, that's great. I did not do further experiments as 35k simulations per move already takes 30s per move, so about 1h15min per game. As I never consider making less than 200 or 400 or even 800 games to have precise statistics, you can imagine the amount of computer time it asks. I have precise statistics only with 35k and 70k, and unprecises with 2 minutes per move. Yet, for scalability issues I could consider making much less games. If my lab's cluster becomes available again, I will certainly try and post the results. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs - scalability
On Thu, 2007-01-11 at 05:25 -0800, terry mcintyre wrote: Since we can no longer count on doubling single-processor speed every 18 months, go programs will need to scale across multiple processors. Dual-core systems are common; a pair of duos can be had for $5K or so. IBM sells four dual-core processors in a single rackmount chassis, and can be expected to make four quad-cores available by the end of the year. Both Intel and AMD have announced multicore roadmaps. Less well-known processors, such as Sun's UltraSparc T1, have 8 cores and up to 32 simultaneous threads. It will be interesting to see what happens. They have predicted this fall-off every year but it hasn't happened yet - invariably it will unless someone can exploit the laws of physics in a way we don't understand yet. I suspect we can still get many more doublings even on a single core - but it may involve significantly different technologies than silicon. - Don Terry McIntyre - Original Message From: steve uurtamo [EMAIL PROTECTED] To: [EMAIL PROTECTED] Cc: computer-go computer-go@computer-go.org Sent: Thursday, January 11, 2007 4:18:01 AM Subject: Re: [computer-go] Gnugo vs commercial programs I still don't understand your point. Are you just trying to say computers have a long way to go to beat really strong humans? nope -- i'm saying that until extra time makes a measurable difference in the strength of a program, worrying about how much time a program spends on any particular activity (like winning or losing a game) is less important than worrying about the activity itself. s. Yahoo! Music Unlimited Access over 1 million songs. http://music.yahoo.com/unlimited ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Access over 1 million songs - Yahoo! Music Unlimited. ___ 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] Gnugo vs commercial programs
On Thu, 2007-01-11 at 07:52 -0500, Don Dailey wrote: I agree that Gnugo was written in an absolute non-scalable style. What Gnugo does is continually upgrade from year to year.They are making their program scale in a painfully manual way. I want to clarify what I said about Gnugo. I'm not being critical of this style - it's perfectly feasible to just upgrade often and keep up in this way. For instance if level 16 is now considered fairly optimal but just too slow, it might become the default level in a future release of gnugo in just a year or two - perhaps with algorithmic optimizations to speed this up further. But that's my point - by then and along with other improvements someone might say level 24 is best - and no doubt there would be other improvements to go along with this that makes it do more work. One could imagine a very clever engineer taking Gnugo 3.7.10 at level 16 and finding a way to make it run at 10 seconds per move.Whether this is possible or not - you get the point - it all comes down to making it do more in a given amount of time. Scalability is either explicit or implicit. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
Hello Magnus, I am glad to hear your experiment in 19x19. Your pruning is based on expert go knowledge or another statistic? Do have some statistics of the level of your pruning method against another program (let's say gnugo :)) in 19x19? Sylvain 2007/1/11, Magnus Persson [EMAIL PROTECTED]: I am currently working with different pruning methods for 19x19 go. What worked for Valkyria on 9x9 become much to slow on 19x19 where full board evaluation of several 100 moves simply does not work. During christmas I was able to prune the number of candiate moves to perhaps a factor 4-20 depending on the stage of the game. It now starts to play much better with a minute per move, but I did an experiment where I let have 10 minutes per move (it took several days to play that game) and for some moves I let it think for an hour. It was 9 handicap game and when it resigned it was only losing with 4.5 points. One game does not prove anything, but it showed that my MC implementation has the potential as long as it become more efficient. That is by better move pruning methods and faster hardware. And improvements to the main algorithms of the progam should of course also make a difference. I have said this before but I repeat my point here that is that MC programs cannot just be moved from 9x9 to 19x19 right away. It will take a lot of new ideas, but eventually I think really strong programs are possible even on present hardware, and these programs will of course scale very wll on 19x19. It is my impression that scalability might even be better on 19x19 than for 9x9. Quoting Sylvain Gelly [EMAIL PROTECTED]: 2007/1/11, steve uurtamo [EMAIL PROTECTED]: Well then the time is now. Look at the Sylvain's post on the scalability of Mogo. if the improvement continues to hold with more doublings, that's great. I did not do further experiments as 35k simulations per move already takes 30s per move, so about 1h15min per game. As I never consider making less than 200 or 400 or even 800 games to have precise statistics, you can imagine the amount of computer time it asks. I have precise statistics only with 35k and 70k, and unprecises with 2 minutes per move. Yet, for scalability issues I could consider making much less games. If my lab's cluster becomes available again, I will certainly try and post the results. ___ 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] Gnugo vs commercial programs
- Original Message - From: Jeff Nowakowski [EMAIL PROTECTED] To: computer-go computer-go@computer-go.org Sent: Thursday, January 11, 2007 3:37 PM Subject: Re: [computer-go] Gnugo vs commercial programs On Thu, 2007-01-11 at 07:40 -0500, Don Dailey wrote: Of course there is some questions about how long Moore's law will hold. If you are referring to CPU speed doubling (as opposed to transistor count), then that has been over for at least 5 years. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software http://www.gotw.ca/publications/concurrency-ddj.htm The problem is that concurrency doesn't scale well. -Jeff Yes, the INTEL engineers have long solved the problems of the programmers. But now the programmers have to solve the problems of the engineers. They do not know what to do with additional gates. The simplest way is to add another core. And if you have still too much gates left, make a quad core. The problem is that concurrency doesn't scale well. I think it depends on the application. In the simplest case, a server with many processes, it scales well. There are other applications like graphics were scaling is up to a certain limit relative straightforward. And there are still other applications like Alpha-Beta search which scale badly. Although up to 4 processors even Alpha-Beta scales well. In the Hydra FPGA there are also enough gates for a 2nd chess-core. But until now I have not succeeded to get a speedup with the second core. One very nasty limiting factor is the slow PCI bus. The Software side can not feed this cores fast enough (the CPU speed is sufficient, but bringing it over the bus is the problem). Another problem is Alpha-Beta itself. The FPGAs search with a fixed depth 4. If at Depth 4 nothing is to distribute, because the first move creates already a cutoff, the second core sits idle. The bus problem is a general one. E.g. modern graphic cards have a very powerfull GPU. One could use this e.g. for the computation of neural networks. The theoretic speedup is impressive, but the practical is low or it even slows down things. The neural-network-computation must - in comparision to the data - very large. Otherwise the transfer of data eats up all the speedup. Chrilly ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
Hi Magnus, I don't understand who the players were in the 9 handicap game. Who received the handicap and who was Valkyria's opponent? Was the opponent the un-pruned version of Valkyria? more comments below ... On Thu, 2007-01-11 at 15:38 +0100, Magnus Persson wrote: I am currently working with different pruning methods for 19x19 go. What worked for Valkyria on 9x9 become much to slow on 19x19 where full board evaluation of several 100 moves simply does not work. During christmas I was able to prune the number of candiate moves to perhaps a factor 4-20 depending on the stage of the game. It now starts to play much better with a minute per move, but I did an experiment where I let have 10 minutes per move (it took several days to play that game) and for some moves I let it think for an hour. It was 9 handicap game and when it resigned it was only losing with 4.5 points. One game does not prove anything, but it showed that my MC implementation has the potential as long as it become more efficient. That is by better move pruning methods and faster hardware. And improvements to the main algorithms of the progam should of course also make a difference. I have said this before but I repeat my point here that is that MC programs cannot just be moved from 9x9 to 19x19 right away. It will take a lot of new ideas, but eventually I think really strong programs are possible even on present hardware, and these programs will of course scale very wll on 19x19. It is my impression that scalability might even be better on 19x19 than for 9x9. This is clearly true - but probably because the games are much longer. With some 19x19 experiments I did using my old-fashioned MC program (which has limited scaling) the improvements were enormous with a doubling of the number of play-outs. With 9x9 the improvements were also significant, but not nearly so much. - Don Quoting Sylvain Gelly [EMAIL PROTECTED]: 2007/1/11, steve uurtamo [EMAIL PROTECTED]: Well then the time is now. Look at the Sylvain's post on the scalability of Mogo. if the improvement continues to hold with more doublings, that's great. I did not do further experiments as 35k simulations per move already takes 30s per move, so about 1h15min per game. As I never consider making less than 200 or 400 or even 800 games to have precise statistics, you can imagine the amount of computer time it asks. I have precise statistics only with 35k and 70k, and unprecises with 2 minutes per move. Yet, for scalability issues I could consider making much less games. If my lab's cluster becomes available again, I will certainly try and post the results. ___ 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] Gnugo vs commercial programs
The bus problem is a general one. E.g. modern graphic cards have a very powerfull GPU. One could use this e.g. for the computation of neural networks. The theoretic speedup is impressive, but the practical is low or it even slows down things. The neural-network-computation must - in comparision to the data - very large. Otherwise the transfer of data eats up all the speedup. this reminds me of two 'graduate student' hacks i got to see in the early 90's. the SGI machines at that time had special-purpose hardware to do point rotations and translations, and a giant bank of high-speed RAM that would otherwise go unused if you weren't doing graphics. the thinking was, hey, why not break down this NxN matrix multiplications into little 4x4 pieces, and use the graphics ram as if it were freely available for any particular purpose. feed the data array in as if it were a group of points describing an object that you needed to rotate, hit it against the 4x4 chip with parameters representing little 4x4 chunks of the larger NxN transformation, and read your data out of the graphics RAM as it became available. another cute trick that i still laugh about was a solution to the 'there are no machines available for you to use' problem. the affected student rewrote his code in postscript and sent it to the printer. sure, it tied up the cheap processor in the printer overnight, but then it printed out the results. :) 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] Gnugo vs commercial programs
But often it also suddenly pick a really bad move and play it so the descrioption above is a little idealized. Did you try picking the move with the highest number of simulations rather than the higher average? This only modification gave MoGo a +10% against gnugo in 19x19 (from 40% to 50% with 70k sim/move). And you can't say that it is a difficult modification to do :). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
On Thu, 2007-01-11 at 17:13 +0100, Magnus Persson wrote: When I watch Valkyria analyze a 19x19 position it often goees like this: For the first 30 seconds or so it almost random, it does not have the statistical power to pick out good moves. Then it starts jump around between some moves that at least make sense. After 2-10 minutes it might actually pick out one or more really good moves which one would expect a 10 kyu player to play. But often it also suddenly pick a really bad move and play it so the descrioption above is a little idealized. Some critical move it actually finds after a few seconds so I really have to use some more flexible time control. Yes, it's fun watching this process. Here is how I think of Mogo and Gnugo by analogy: I use to know a expert level chess player and I considered him non-scalable. He loved speed-chess, always made his decisions very quickly and they were usually pretty good ones.He had no use for extra time because he knew right away what move he wanted to play. In tournaments I would be still in the opening and see him walking around - his game was already over and he would have a big grin on his face whether he won or lost. He laughed about it no matter what happened. Gnugo reminds me of this. It plays a pretty good move very quickly and to a certain extent it's decision is not reversible. But your description of Mogo shows the opposite approach. Mogo NEVER knows for sure what to play and like to keep refining it's decision making process. It starts out rather ignorant and indecisive, but always remains objective, willing to admit it was wrong and that some other move might possibly be better. Give it more time and it is happy to continue checking if it can improve. A very humble and thorough approach. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
Magnus, I applied my analogy to Mogo, but I really meant any good UCT program such as yours - I just forgot who I was responding to in my last email. - Don On Thu, 2007-01-11 at 17:13 +0100, Magnus Persson wrote: Quoting Don Dailey [EMAIL PROTECTED]: I don't understand who the players were in the 9 handicap game. Who received the handicap and who was Valkyria's opponent? Was the opponent the un-pruned version of Valkyria? No, the opponent was myself, european 2 Dan as white taking a 9 handicap on 19x19. If a program can give me trouble with 9 stones then I consider it as strong for a program. I might also be playing a little nice when I test my programs, since I want to see how it reacts to proper moves not to really aggressive tricky ones. more comments below ... This is clearly true - but probably because the games are much longer. With some 19x19 experiments I did using my old-fashioned MC program (which has limited scaling) the improvements were enormous with a doubling of the number of play-outs. With 9x9 the improvements were also significant, but not nearly so much. When I watch Valkyria analyze a 19x19 position it often goees like this: For the first 30 seconds or so it almost random, it does not have the statistical power to pick out good moves. Then it starts jump around between some moves that at least make sense. After 2-10 minutes it might actually pick out one or more really good moves which one would expect a 10 kyu player to play. But often it also suddenly pick a really bad move and play it so the descrioption above is a little idealized. Some critical move it actually finds after a few seconds so I really have to use some more flexible time control. ___ 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] Gnugo vs commercial programs
Quoting Sylvain Gelly [EMAIL PROTECTED]: Hello Magnus, I am glad to hear your experiment in 19x19. Your pruning is based on expert go knowledge or another statistic? Do have some statistics of the level of your pruning method against another program (let's say gnugo :)) in 19x19? There are several ways it prunes. The Valkyria code itself refuses to play some really bad moves in the simulations such as destroying its own eyeshape. These moves are also pruned at the root. In the opening a lot of moves can be pruned by pattern matching and these I can make by hand (go knowledge - but not really at expert level). Finally I use a pruning method I have been using with non-MC programs where moves evaluated bad at ply n is pruned when they are evaluate again at ply n + 2 and their local neighborhood has not been changed. This method is a little crude and perhaps a little risky, but the gains clearly outweighs the disadvantages. I have not made any test yet, since it is all in development. None of the methods above changes the UCT-search itself. It is just some crude means to generate fewer moves. But I have been thinking about the UCT-search and think it has a problem that maybe some mathematical guy like you can fix in sound way. The thing is that on 19x19 there can be several 100 candidate moves. Given inifinite time the search will find the best move. But when it is very little time *left* to search I think it is a waste of time to spend effort on the moves that are the worst since they seem very unlikely to become the best move before we run out of time (at some point in time it is even impossible). I think the ideal algorithm should be sensitive to the time left and start to prune moves accordingly. UCT already does this to some extent, but I believe it does so only with very long thinking times. The only idea I had in this direction is that is probably never bad to prune the worst candidate in every position after some effort has been made. But how many moves with bad evaluations canbe pruned and under what conditions? -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
On Thu, 2007-01-11 at 17:19 +0100, Sylvain Gelly wrote: But often it also suddenly pick a really bad move and play it so the descrioption above is a little idealized. Did you try picking the move with the highest number of simulations rather than the higher average? This only modification gave MoGo a +10% against gnugo in 19x19 (from 40% to 50% with 70k sim/move). And you can't say that it is a difficult modification to do :). This is an important improvement and I discovered it myself long ago. Another way is to go into overtime if the best move isn't the most simulated move. It's not clear to me whether you should go to this extra trouble and my current program does the simple thing - exactly as you describe it, just play the most simulated move. I used to extent the thinking time until both the best and most simulated matched - but you have to put some kind of cap on it.I'm really not sure it helps over simply choosing the most simulated move. In problem testing, you will see that when the right move becomes the BEST move, it still takes a few moments before it becomes the most simulated move, but it happens relatively quickly. - Don 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] Gnugo vs commercial programs
Quoting Sylvain Gelly [EMAIL PROTECTED]: But often it also suddenly pick a really bad move and play it so the descrioption above is a little idealized. Did you try picking the move with the highest number of simulations rather than the higher average? This only modification gave MoGo a +10% against gnugo in 19x19 (from 40% to 50% with 70k sim/move). And you can't say that it is a difficult modification to do :). No I have not tried that yet. I think I have been planning to modify time control, so that it will try to stop thinking when the highest winrate has been searched significantly more than the second highest winrate. -Magnus ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
Did you try picking the move with the highest number of simulations rather than the higher average? This only modification gave MoGo a +10% against gnugo in 19x19 (from 40% to 50% with 70k sim/move). And you can't say that it is a difficult modification to do :). This is an important improvement and I discovered it myself long ago. Yes I remember, and we already discused that on this list. However the improvement on 9x9 was very small whereas it is huge in 19x19. It is why I recall this. Another way is to go into overtime if the best move isn't the most simulated move. Yes; It's not clear to me whether you should go to this extra trouble and my current program does the simple thing - exactly as you describe it, just play the most simulated move. I used to extent the thinking time until both the best and most simulated matched - but you have to put some kind of cap on it.I'm really not sure it helps over simply choosing the most simulated move. I am pretty sure that intelligent time control in 19x19 would be great. But it is not so obvious, and a lot of test has to be done (I never did any). Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
No I have not tried that yet. I think I have been planning to modify time control, so that it will try to stop thinking when the highest winrate has been searched significantly more than the second highest winrate. Perhaps a more elaborate time control should be useful. Maybe it is better to consider also the speed of change. A quick change would mean that something is not stable about the position, so you have to think more. I would be happy to hear about precise experiments. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Gnugo vs commercial programs
Finally I use a pruning method I have been using with non-MC programs where moves evaluated bad at ply n is pruned when they are evaluate again at ply n + 2 and their local neighborhood has not been changed. This method is a little crude and perhaps a little risky, but the gains clearly outweighs the disadvantages. I tried something similar while not totally pruning the move. Simply takes the statistics of one parent to initialize the UCT statistics. It was of little help in 9x9. I did not try in 19x19. But when it is very little time *left* to search I think it is a waste of time to spend effort on the moves that are the worst since they seem very unlikely to become the best move before we run out of time (at some point in time it is even impossible). I think the ideal algorithm should be sensitive to the time left and start to prune moves accordingly. UCT already does this to some extent, but I believe it does so only with very long thinking times. I think it should be easy, given a UCT tree and the time left, to compute if one move has a chance to become best before the end or not. However, I think it should be more usefull to build an adaptative time control, rather than trying to improve UCT with hard time control. Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] concurrency scalability?
Terry: Several on this list have experimented with concurrent processing - can you share any overall summary of your results? How well does the problem scale? Any advice? Sylvain: The results I have so far are very simple. I have a very (very) simple concurrent implementation of UCT. With 4 processors, the lost time is about 10% (the speed is * 3.6 with 4 processors). Comparing with the same number of simulations per move, the strength is the same (no [loss] by the fact that it is no more a real UCT as several threads can take the same path). That level of concurrency is excellent! So it should be possible to do about 3.6 times as many simulations per move in the same time, memory permitting? From previous discussion, it seems that doubling from 35,000 to 70,000 simulations was quite beneficial, so 3.6 times 35,000 should perhaps be even stronger. 4 processors is very few, so this can be different with 32 processors for example. My guess is that with a very little work, it should work well even with 32 processors. So I don't see any problem to benefit from the future multiple cores :). Within the year, quad-core and eight-core systems should be readily available. One might even try the Sun Ultrasparc T2000, currently available with 8 cores, each capable of running 4 concurrent threads, designed to make maximum use of memory bandwidth by firing up a new thread whenever another thread is stalled waiting for memory. Today's exotic multiprocessor system is tomorrow's commodity chip. Cheap talk? Check out Yahoo! Messenger's low PC-to-Phone call rates. http://voice.yahoo.com___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] concurrency scalability?
That level of concurrency is excellent! So it should be possible to do about 3.6 times as many simulations per move in the same time, memory permitting? From previous discussion, it seems that doubling from 35,000 to 70,000 simulations was quite beneficial, so 3.6 times 35,000 should perhaps be even stronger. This 3.6 could be improved a lot. I think the implementation of Remi Coulom is much better. MoGo already plays on a 4 processors on KGS. In a 30 minutes game in 19x19, it uses only 20 s per move at the begin, then much less. So with 20s it hardly do 70k simulations and less that 10k simulations at the end of the game (no more time). It is why I think that playing 19x19 in 30 minutes is a blitz :-). Within the year, quad-core and eight-core systems should be readily available. One might even try the Sun Ultrasparc T2000, currently available with 8 cores, each capable of running 4 concurrent threads, designed to make maximum use of memory bandwidth by firing up a new thread whenever another thread is stalled waiting for memory. Today's exotic multiprocessor system is tomorrow's commodity chip. I am looking forward to seeing these machines! Sylvain ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
