Re: [computer-go] MCTS, 19x19, hitting a wall?
From: Don Dailey dailey@gmail.com My basic observation is that over the several year period I have been in this forum, I have detected a huge amount of resistance to the idea that hardware could have anything to do with computer go strength, despite the fact that it keeps proving to be so. The resistance is strong enough that we have to explain it way when it happens, by saying things like we have hit a wall and it won't happen any more thank goodness. You overrstate the resistance - it's not that anybody is saying hardware is irrelevant. In fact, did we not have a recent discussion over the merits of two different CPU variations? We've seen a fair number of multi-processor entrants at competitions, besides. The questions ishow much does hardware matter? So far, we have one data point to work with: David Fotland's excellent Many Faces of Go is about one stone stronger when it uses 32 cores instead of 2. That's nice to have, but if we extrapolate, a factor of 16 is 3 doublings or about 4.5 years, in terms of Moore's Law. It will only take 9*4.5, roughly 40 years, to reach pro-level play. We don't have data from Mogo yet, but I wonder if they are seeing 2-3 stones improvement for their 3200-node version? The less patient among us may wish to seek algorithmic improvements to bridge the gap a bit sooner. Got to be some reason for bright programmers and mathematicians to work on the problen, after all; otherwise we could just wait 40 years for Intel and AMD to deliver 32,768 cores on a single chip - or will it be a silicon wafer? In other fields, algorithmic improvements have led multiple orders of magnitude improvement in running time. Humans manage to complete 30-minute games on a 19x19 board, so we do have evidence that the game can be played well at such a speedy pace. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
Terry, I don't think the part of the argument looking at hardware is sound. You are assuming that computing power is going to continue to provide a linear strength increase with every doubling. I think the argument being made by a few of the previous posters is that the strength curve is showing asymptotic behaviour, and it is very possible that it will tail off somewhere soon with the current generation of algorithms. The 19x19 board, lest anybody forgets, is huge: http://homepages.cwi.nl/~tromp/go/legal.html. A few gazillion percent of added speed is not enough. Faster hardware *will* however help us execute algorithms that are infeasible now, and I think that is part of the argument Don is making. I have a lot of respect for Olivier and people like Magnus who put all this effort into experimenting with heavy playout patterns. Unfortunately, it's a bad sign that there is so much work now going into pattern tuning for MCTS on 19x19.. when we reach a tuning stage like that, I get a feeling of deja vu. That's what all the traditional programs started spending time on. Christian On 11/06/2009 07:04, terry mcintyre wrote: *From:* Don Dailey dailey@gmail.com ** My basic observation is that over the several year period I have been in this forum, I have detected a huge amount of resistance to the idea that hardware could have anything to do with computer go strength, despite the fact that it keeps proving to be so. The resistance is strong enough that we have to explain it way when it happens, by saying things like we have hit a wall and it won't happen any more thank goodness. You overrstate the resistance - it's not that anybody is saying hardware is irrelevant. In fact, did we not have a recent discussion over the merits of two different CPU variations? We've seen a fair number of multi-processor entrants at competitions, besides. The questions ishow much does hardware matter? So far, we have one data point to work with: David Fotland's excellent Many Faces of Go is about one stone stronger when it uses 32 cores instead of 2. That's nice to have, but if we extrapolate, a factor of 16 is 3 doublings or about 4.5 years, in terms of Moore's Law. It will only take 9*4.5, roughly 40 years, to reach pro-level play. We don't have data from Mogo yet, but I wonder if they are seeing 2-3 stones improvement for their 3200-node version? The less patient among us may wish to seek algorithmic improvements to bridge the gap a bit sooner. Got to be some reason for bright programmers and mathematicians to work on the problen, after all; otherwise we could just wait 40 years for Intel and AMD to deliver 32,768 cores on a single chip - or will it be a silicon wafer? In other fields, algorithmic improvements have led multiple orders of magnitude improvement in running time. Humans manage to complete 30-minute games on a 19x19 board, so we do have evidence that the game can be played well at such a speedy pace. ___ 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] MCTS, 19x19, hitting a wall?
Hardware has a huge effect on go strength, but mainly by enabling better algorithms. MCTS would have been impossible on the 640 KB, 24 MHz, 80286 I used to develop Many Faces of go. I think you would agree with me when I say that the stronger programs five years from now will gain that strength both from faster hardware and improved algorithms. I expect that five years from now, today's Mogo or today's Many Faces running on that hardware, will be rather weak compared to the top programs. David From: computer-go-boun...@computer-go.org [mailto:computer-go-boun...@computer-go.org] On Behalf Of Don Dailey Sent: Wednesday, June 10, 2009 9:27 PM To: computer-go Subject: Re: [computer-go] MCTS, 19x19, hitting a wall? My basic observation is that over the several year period I have been in this forum, I have detected a huge amount of resistance to the idea that hardware could have anything to do with computer go strength, despite the fact that it keeps proving to be so. The resistance is strong enough that we have to explain it way when it happens, by saying things like we have hit a wall and it won't happen any more thank goodness. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
In my humble opinion, we need a change in the algorithm. The numbers are misleading - 95% of win of MoGo on 32 nodes against MoGo on 1 node (this is a real number for 19x19) certainly means that the parallel version is stronger than the sequential version, but not much better, far less than what suggests this 95%. MCTS algorithms adapt the beginning of simulations only, and for many cases we have to deal with predictions on the end of simulations: something like if the opponent plays X, I'll reply Y. The bias on semeais is, in my humble opinion, equivalent to this fact that we learn only the beginning of the simulations (the tree part) and not the end. I don't know if the good word is to say that it's a wall or a mountain, but I think the idea is that we need something really different - perhaps heavy playouts that solve some tactical elements, or perhaps some statistical trick for modifying the playouts depending on the simulations - I'd like to solve this with supervised learning like when I reply X to move Y then I win with higher probability. It would be a nice solution, efficient beyond the game of Go. Well, as I've spent a lot of time on this idea without finding an implementation which works better than the baseline, perhaps my ideas are not very interesting :-) Regarding Moore's Law, I'd love to hear the Mogo team's perspective on this; they have probably had more opportunity to test their algorithms extensively on big-n-count computers than any of us. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
On Wednesday 10 June 2009 22:15:22 Ian Osgood wrote: We have evidence against going this low: Rybka and several other modern engines were ported to the dedicated computers Resurrection (203 MHz StrongArm) and Revelation (500 MHz XScale). Rybka's rating in the SSDF pool on these platforms are 2497 and 2634, respectively. 44 Resurrection Rybka 2.2 StrongARM 203 MHz 2497 That is for Rybka 2.2, which is 3 years old! I am talking about Rybka 3. In the CEGT list: Rybka 3 w32 1CPU 3052 Rybka 2.2n2 w32 1CPU 2944 Which is about 110 ELO stronger. Slightly less than 2 doublings of speed again. So we end up somewhere near 75Mhz. To conclude, it appears that 500 MHz (embedded: poor cache performance) with little memory for transposition tables is the lowest you can go, while still staying at grandmaster level. At 500Mhz, Rybka 3 would be about 2745 ELO. That's not grandmaster level. That puts you in the top 15 in the world. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
On Wednesday 10 June 2009 18:48:55 Martin Mueller wrote: Currently, we try to sidestep this fundamental problem by replacing local search with local knowledge, such as patterns. But that does not fully use the power of search. So, has anyone tried recursive UCT (using UCT again in the playouts), and what were the results? I saw some results for uninteresting games, but nothing about Go. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: June KGS bot tournament: full boards, fast
Auch, Japanese computer Go developers will have CGF Open computer Go tournament on June 20th and 21st. #CGF stands for Computer Go Forum (Japan). #http://www.computer-go.jp/index.html Announcement: http://hp.vector.co.jp/authors/VA012620/cgf2009/cgf2009.html (in Japanese) Entrants: http://hp.vector.co.jp/authors/VA012620/cgf2009/list2009.html (in Japanese) Fourteen programs including Katsunari, Aya and FudoGo are listed. CGF Open lets all participants be with their computers and will finish 16:00 JST (07:00 UCT) on Sunday. So, it's very hard for them to attend the KGS tournament. :- I didn't post here because it's a domestic tournament but I should... Hideki Nick Wedd: gm4+oroxuamkf...@maproom.demon.co.uk: The June 2009 KGS computer Go tournament will be on Sunday June 21st, in the Asian evening, European morning and American night, starting at 08:00 UTC/GMT (09:00 BST) and ending at 14:00 UTC/GMT (15:00 BST). There will be only one division. It will be a 9-round Swiss with 19x19 boards and 18 minutes each of main time. It will use Chinese rules with 7.5 points komi, and a very fast Canadian Overtime, of 25 moves in 20 seconds. There are details at http://www.gokgs.com/tournInfo.jsp?id=467. Registration is now open. To enter, please read and follow the instructions at http://www.weddslist.com/kgs/how/index.html. The rules are given at http://www.weddslist.com/kgs/rules.html. Please send your registration email (with the words KGS Tournament Registration in the title) to me at maproom at gmail dot com (converted to a valid address in the obvious way). Nick -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: US Go Congress
Another 2 cents from me: what about inviting good old Bruce Wilcox for a show event against computer(s)? With him you would get all in one: * strong amateur * author of (old) go program * author of one of the best go books ever Ingo. -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
Would this be a simple way of using many cores effectively? Otherwise I cannot see how recursive UCT would be anything else than an ineffective implementation of UCT. Unless it provides some information that could be used more effectively than with normal search. In order to do so the playouts need to communicate what moves are good perhaps something like the historyheuristic used in chess. Magnus Quoting Gian-Carlo Pascutto g...@sjeng.org: On Wednesday 10 June 2009 18:48:55 Martin Mueller wrote: Currently, we try to sidestep this fundamental problem by replacing local search with local knowledge, such as patterns. But that does not fully use the power of search. So, has anyone tried recursive UCT (using UCT again in the playouts), and what were the results? I saw some results for uninteresting games, but nothing about Go. -- GCP ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- Magnus Persson Berlin, Germany ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
I very strongly suspsect that Many Faces, Mogo, Crazy Stone and others are heavily optimized to play well on exactly the hardware we have at the moment. There is the huge problem that you cannot easily test scalability because you cannot produce the thousands of game needed to get accurate numbers except at very fast games.And you cannot get reliable results against humans without waiting weeks. I think after a very rapid development period where we saw incredible and amazing results, anything less is discouraging and we are ready to throw in the towel. - Don 2009/6/11 Olivier Teytaud teyt...@lri.fr In my humble opinion, we need a change in the algorithm. The numbers are misleading - 95% of win of MoGo on 32 nodes against MoGo on 1 node (this is a real number for 19x19) certainly means that the parallel version is stronger than the sequential version, but not much better, far less than what suggests this 95%. MCTS algorithms adapt the beginning of simulations only, and for many cases we have to deal with predictions on the end of simulations: something like if the opponent plays X, I'll reply Y. The bias on semeais is, in my humble opinion, equivalent to this fact that we learn only the beginning of the simulations (the tree part) and not the end. I don't know if the good word is to say that it's a wall or a mountain, but I think the idea is that we need something really different - perhaps heavy playouts that solve some tactical elements, or perhaps some statistical trick for modifying the playouts depending on the simulations - I'd like to solve this with supervised learning like when I reply X to move Y then I win with higher probability. It would be a nice solution, efficient beyond the game of Go. Well, as I've spent a lot of time on this idea without finding an implementation which works better than the baseline, perhaps my ideas are not very interesting :-) Regarding Moore's Law, I'd love to hear the Mogo team's perspective on this; they have probably had more opportunity to test their algorithms extensively on big-n-count computers than any of us. ___ 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] MCTS, 19x19, hitting a wall? moore's law limits
I know what Moore actually said and what is perceived as Moore's law are two different things. But it's pretty much the case that performance has doubled every couple of years. Nobody really believes that Moore's law will continue although it's pretty amazing that its demise keeps getting predicted and keeps getting extended.Like everything else the prediction is that it will happens sooner rather than later, and it keeps getting extended to later. That's only because the road far ahead is unclear, but the road immediately in front of you is the only part that is very clearly visible. However, the laws of physics is proof that it has to happen. I have noticed that even now chips are getting faster at a slower rate and that they are moving towards more and more cores on a single chip instead. This is bad because not all algorithms can be scaled in parallel fashion. And some algorithms can be somewhat scaled but with limits and they take a hit for this.So we probably are finally entering a period of slower growth. - Don 2009/6/11 David Fotland fotl...@smart-games.com First, Moore said that density would double every 18 months or so. He did not say performance would double. Second, lately it’s harder to double so it is more like two years per doubling. Third, Moore’s law won’t continue for 40 more years. Trust me, I’m CTO at a semiconductor company J Vertical scaling limits were hit a few years ago, which is why peak frequency stopped going up so fast. Once oxide thickness is down to about a dozen atoms there is no room to make it thinner without too much process variation and too much tunneling current. Voltage scaling limits were hit around the same time, around 1 volt, since the supply voltage has to be higher than the transistor threshold voltage. Without scaling voltage down, power becomes a limiter to performance. We have about 2 to 4 more doublings before planar transistors stop working. There are alternatives (google finfet), but they are much more difficult to fabricate, and in any case fets won’t work with gates of only a few nanometers. Lithography also becomes a big issue soon. There is no inexpensive alternative to deep UV despite hundreds of millions of dollars spent on research on x-ray and scanning electron beams. No one has found a good lens for x-rays, and electron beams are too slow. Maximum die size grew in the early days, but has been constant for more than 10 years, so we can’t grow the chip area. Die can be stacked, but this doesn’t work well because silicon is not a great conductor of heat and the inner layers will overheat (and hot silicon is slow silicon). Someone will mention alternatives to silicon like carbon nanotubes, but these are just speculation. It took silicon technology 40 years of active development by the whole industry to get where it is now. Nothing else is even close to being feasible. I think we will get another 64x to 256 x density then it will stop, for single chips. We should eventually get desktop machines with thousands of cores, but probably never with millions of cores. There really are limits built into physics L David *From:* computer-go-boun...@computer-go.org [mailto: computer-go-boun...@computer-go.org] *On Behalf Of *terry mcintyre *Sent:* Wednesday, June 10, 2009 11:04 PM *To:* computer-go *Subject:* Re: [computer-go] MCTS, 19x19, hitting a wall? -- *From:* Don Dailey dailey@gmail.com My basic observation is that over the several year period I have been in this forum, I have detected a huge amount of resistance to the idea that hardware could have anything to do with computer go strength, despite the fact that it keeps proving to be so. The resistance is strong enough that we have to explain it way when it happens, by saying things like we have hit a wall and it won't happen any more thank goodness. You overrstate the resistance - it's not that anybody is saying hardware is irrelevant. In fact, did we not have a recent discussion over the merits of two different CPU variations? We've seen a fair number of multi-processor entrants at competitions, besides. The questions ishow much does hardware matter? So far, we have one data point to work with: David Fotland's excellent Many Faces of Go is about one stone stronger when it uses 32 cores instead of 2. That's nice to have, but if we extrapolate, a factor of 16 is 3 doublings or about 4.5 years, in terms of Moore's Law. It will only take 9*4.5, roughly 40 years, to reach pro-level play. We don't have data from Mogo yet, but I wonder if they are seeing 2-3 stones improvement for their 3200-node version? The less patient among us may wish to seek algorithmic improvements to bridge the gap a bit sooner. Got to be some reason for bright programmers and mathematicians to work on the problen, after all; otherwise we could just
Re: [computer-go] Re: June KGS bot tournament: full boards, fast
In message 4a30d1df.9656%hideki_ka...@ybb.ne.jp, Hideki Kato hideki_ka...@ybb.ne.jp writes Auch, You know German as well as English? Japanese computer Go developers will have CGF Open computer Go tournament on June 20th and 21st. #CGF stands for Computer Go Forum (Japan). #http://www.computer-go.jp/index.html Announcement: http://hp.vector.co.jp/authors/VA012620/cgf2009/cgf2009.html (in Japanese) Entrants: http://hp.vector.co.jp/authors/VA012620/cgf2009/list2009.html (in Japanese) Fourteen programs including Katsunari, Aya and FudoGo are listed. CGF Open lets all participants be with their computers and will finish 16:00 JST (07:00 UCT) on Sunday. So, it's very hard for them to attend the KGS tournament. :- I didn't post here because it's a domestic tournament but I should... Thank you for letting me know, I have added it to the list at http://www.computer-go.info/events/future.html I always appreciate information about computer Go events, for adding to that list. It is unfortunate that I have chosen the same date for my KGS computer Go event, particularly as I will be holding this one at a time intended to suit East Asian programmers. But I do not plan to change the date or time now that I have announced them. It would be better if I chose dates for my events further in advance, I shall try to do so in future. Nick -- Nick Weddn...@maproom.co.uk ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
