[Computer-go] Thoughts about bugs and scalability

Don Dailey dailey.don at gmail.com
Mon Jun 20 11:24:25 PDT 2011


I have been careful to condition my statements with phrases like "properly
written program" and so on.    It may indeed be difficult to produce a
program that behaves nicely at any time control you set,  such as 1 move per
day,  etc.

And it may be the case that any particular program scales poorly against
humans.    I don't think that has been demonstrated with any kind
of reasonable accuracy,  but nevertheless I don't doubt it.    But even in
this case I think it would only require some minor changes to fix that
behavior (not a total rewrite) and it would just be an indication that the
program is overzealously tuned to get a good result at a very narrow range
of levels.

And of course it is probably the case that the best settings for play on
current machines is too exploitative or not exploratory enough for longer
thinking times,  however that seems to me to be an implementation issue -
something easily corrected when properly understood.     It should not have
to be the case that every year you "re-tune" the program for a new level.

And finally there is no doubt in my mind that massive improvements in
dealing with the difficult problem will help the scalability.    This is not
primarily a computer vs human thing however,  if you get those major
improvements your computer vs computer results is going to also
improve significantly.     That is unless you believe these issues are not
relevant to playing against computers,  which seems rather silly to me.
 Are these real problems or not?     The idea that it is only a problem when
playing against humans is ridiculous.

Don





On Mon, Jun 20, 2011 at 1:53 PM, Álvaro Begué <alvaro.begue at gmail.com>wrote:

> I don't have any quantitative data to show, but at some point I tried
> to see what dimwit would do if I let it think for an hour on an
> early-game 9x9 position. The result was that the search was
> ridiculously narrow, with exceedingly long lines whose moves weren't
> particularly good, and it would just never change its mind about what
> move to play, just keep digging deeper (to first order, of course). I
> played around with the exploration/exploitation balance, and I got to
> the conclusion that it was hard to get UCT to do a reasonable job at
> all timescales. This was probably a large obstacle for scalability.
>
> I think when you have explored a node enough times, there is no point
> in considering the score of the node to be the average of all the
> tries, but it should really be just the score of the best child (i.e.,
> the minimax rule). UCT does converge to that value, but it does so by
> reducing exploration of inferior moves, which results in the
> long-lines behavior I just described.
>
> Perhaps there is a role for alpha-beta near the root of the tree when
> we have enough CPU, and that might scale better.
>
> Anyway, I am with Don here. Perhaps the current crop of programs
> doesn't make good use of huge CPU resources for which they were not
> designed, but as those CPU resources become commonplace, we'll see
> programs taking advantage of them. I would be extremely surprised if
> we hit a wall before getting to world-champion level. It will probably
> be just a very very long hill.
>
> Álvaro.
>
>
> On Mon, Jun 20, 2011 at 1:35 PM, Don Dailey <dailey.don at gmail.com> wrote:
> > First of all,  I never purchase papers of unknown quality.   If I know a
> > paper is great or that it comes highly recommended by someone I trust I
> will
> > purchase it although the idea of purchasing papers in general is
> distasteful
> > to me.
> > The scalability issue as you summarize has to do with the number of cores
> -
> > I am not surprised that more cores bring less improvement and that is
> true
> > in ALL games.    That's not the issue I am talking about here although
> it's
> > certain a legitimate practical issue.
> > To better understand the issue,  forget about the specific machine it's
> on
> > and substitute the phrase "scale with time."
> > There is no scaling issue with reasonably written programs that can be
> > tested with current hardware.    Showing that it's difficult to
> parallelize
> > an algorithm that is basically serial does not prove anything here.
> > I have explained why people believe MCTS may have limits and why they are
> > wrong.   All such "evidence" that we have hit some wall is anecdotal.
> > Unless of course you know of someone who has run a few thousands games at
> 1
> > day per move on a single core machine (or equivalent.)
> > Don
> >
> >
> > On Mon, Jun 20, 2011 at 1:12 PM, René van de Veerdonk
> > <rene.vandeveerdonk at gmail.com> wrote:
> >>
> >> On Mon, Jun 20, 2011 at 8:27 AM, Don Dailey <dailey.don at gmail.com>
> wrote:
> >>>
> >>> On Mon, Jun 20, 2011 at 10:09 AM, terry mcintyre
> >>> <terrymcintyre at yahoo.com> wrote:
> >>>>
> >>>> Any particular instance of a program will probably fail to scale -
> >>>> especially against humans who share the lessons of experience.
> >>>
> >>> That is complete nonsense.   How are you backing this up?   What proof
> do
> >>> you have that computers don't play better on better hardware?   Why are
> the
> >>> top programs being run on clusters and multi-core computers?   Are the
> >>> authors just complete idiots?
> >>> Every bit of evidence we have says they are scaling very well against
> >>> humans.     That has also been our experience in game after game,  not
> just
> >>> in Go.
> >>> I apologize for being so harsh on this,  but you are too smart to be
> >>> saying such dumb things.
> >>
> >>
> >> Please read (from Darren Cook):
> >>>
> >>> Richard Segal (who operates Blue Fuego) has a paper on the upper limit
> >>> for scaling:
> >>> http://www.springerlink.com/content/b8p81h40129116kl/
> >>> (Sorry, I couldn't find an author's download link for the paper;
> Richard
> >>> is on the Fuego list but I'm not sure he is even a lurker here.)
> >>
> >> Another paper that mentions the topic (also Fuego specific) is here:
> >> http://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf
> >> The short conclusion of these papers is that it was not worth it to
> scale
> >> Fuego to a IBM/BlueGene machine (original purpose of the work), as it
> didn't
> >> get any better anymore, i.e., performance didn't (appreciably) scale
> beyond
> >> 512 or so cores. Obviously, that's still a big improvement from a
> desktop
> >> pc, but far from the capacity of the supercomputer available.
> >> Zen also has a similar issue according to its co-author Kideko Kato.
> >> That's evidence enough for me to indicate that there indeed is an issue
> with
> >> the current breed of programs.
> >> It appears that current specific implementations have a scaling ceiling.
> I
> >> expect, as expressed by multiple people here, that once that ceiling
> gets
> >> close enough to become a limitation, people will change their algorithms
> >> accordingly and scaling will continue. But it will only happen once you
> can
> >> comfortably test the program in that resource regime.
> >> René
> >> _______________________________________________
> >> Computer-go mailing list
> >> Computer-go at dvandva.org
> >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
> >
> >
> > _______________________________________________
> > Computer-go mailing list
> > Computer-go at dvandva.org
> > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
> >
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20110620/8963fc4f/attachment.html>


More information about the Computer-go mailing list