2011/6/1 Bojun Huang <[email protected]> > Hi Don, > > my replies are inlline. Thanks. > > Bojun > > >Date: Wed, 1 Jun 2011 10:59:31 -0400 > >From: Don Dailey <[email protected]> > >To: [email protected] > > >Subject: Re: [Computer-go] Direct DX11 and graphics > cards for cheaper > > simulation hardware? > >Message-ID: <[email protected]> > >Content-Type: text/plain; charset="iso-8859-1" > > > > I <[email protected]%3E%3E+I> don't think there is a widely accepted > > standard benchmark, but I think > >there are MCTS bots that do light playouts and we could probably "pick" one > >to consider a reference implementation. Some programs may provide the > >option for light playouts, or perhaps could make this an option. What > >do you mean by "light playouts?" One definition is any legal move is > >played with equal probability and another > definition is "less heavy." > > I refer to the latter one. Actually my question is just for defining what > "light playout" is, or, how much "less" heavy is acceptable to keep the > program showing state-of-art performance, and to make the tradoff between > speed and selectivity still within the meaningful range. Clearly, random > selection on all legal moves from uniform distribution is less valuable for > building really strong programs. But on the other hand, how "light" the > playouts in a "strong" program could be? Is there strong program (not > nessarily the top programs) that is well known to use light playouts? > > > > >> > >> Another question ... does more playouts really provide a *consistent* > >> improvement on the ELO score, especially for those strongest programs? I > >> remember that some programs running on laptop rank very high in the > >> Olympaids, that seems imply that speed simply doesn' > t matter here ... > >> > > > >More playouts always consistently improves a program. Like in computer > >chess, it takes a fair increase to be easily measurable so don't listen to > >anecdotal evidence that this is not so. You might hear someone say, "I > >doubled the number of playouts and it did not seem to play any better - or > >it lost a 10 game match despite the doubling." Doubling the number of > >playouts is not going to increase the strength enough that it will guarantee > >a win in a 10 or 20 game match so when that happens some people will > >conclude that increasing the number of playouts has no effect on the > >strength, but that is nonsense. > > > >Don > > > > Yeah, it's intuitive that more playouts would improve the program, but it may > also intuitive that this improvement would become more and more marginal as > the playing capability of the program increases. > > This is a huge myth that for some reason is hard to shake, but it's just not the case. Yes, there probably is a fall-off but it's so gradual I doubt it can be detected in Go and there is no sudden point you can identify where extra playouts suddenly stop helping.
> I heard that doubling the number of playouts gives 50 ELO scores, but this > kind of linear improvement seems cannot hold on in my program when the score > is beyond 2400. Seems the additional playouts is more good at turning weak > programs into average programs than turning average programs into strong > programs. > > The lesson learned from other games, especially chess, is that the fall-off is very gradual. To this day, we STILL get a very nice rating improvement from a doubling of speed but it's true that it's not what it was 20 years ago. But the fact that we still get substantial improvement for doubling the speed in chess even though computers are well beyond human skill levels means we still have a long way to go and that in games like GO we are just barely getting started on this curve. (Also, in chess at this incredible level a lot of games are draws, so getting about 30 ELO or more for a doubling is quite impressive.) Everyone's intuition that there "should be" a sudden fall-off is nonsense and it's based on our poor perception of time - we place WAY TOO MUCH weight on the present and hardly any on the past and future. Thus, it was once believed that NOBODY would ever run the 4 minute mile (because at that exact moment in time it seemed impossible) and it seems that all progress in computer go has stopped (because programs are not much better than they were 2 months ago.) But you have to look at how much progress we made in 2 years, not 2 months. There is another perception problem too because a doubling does not make so much difference it immediately obvious or noticeable as I have already stated. So you could run 200 games and not see an improvement (or see only a very small improvement) and thus conclude that you have suddenly hit the wall! But I doubt you are going to run the thousands of games needed with a doubling of playouts because it would take more time than we are comfortable with (again, a human perception factor here.) So I think it's likely that you don't fully understand what you are looking at. There is one possibility however, which Magnus touched on. It is possible that some MCTS programs have something missing that negatively affects scalability. It could be an outright coding bug, or something else. In theory (and in practice), you should asymptotically approach perfect play as you increase the number of playouts. If you could do infinite playouts and still not get perfect play then something is broken. It might not affect the strength very much when you are doing a few thousand playouts but it might have a huge impact when you are doing a million and thus you will experience a (more) rapid decline in benefit for extra playouts at some point. This could even be an issue with computer chess with respect to null move pruning and Graph History Interaction issues, because there are some positions that may not be solvable no matter how many nodes you look at. Don > > > > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
