[Computer-go] UCT parameters and application to other games

Don Dailey dailey.don at gmail.com
Tue Apr 5 08:55:39 PDT 2011


I think you completely miss the point.   If you randomly choose a processor
for each first move and there is a single move that looks best but needs a
lot of searching to discover it loses, then only 1 processor is effectively
computing and the search may time-out before it's discovered that this is
bad.

That is just one scenario, but the point is that there are many scenario's
where most of the processors are working hard, but not contributing any
useful information to the tree.

The whole point of MCTS is that you should spend 98% of the effort on 2% of
the moves.   You are constructing an algorithm that spends an enormous
amount of effort on moves which should get less than 1% of the effort.

Unless I am completely misunderstanding what you propose here.    I assume
you are talking about making these decisions before the search beings, and
assigning each move playable (at the root) to one of the processors.    Is
that what you are proposing?

Don


On Tue, Apr 5, 2011 at 11:21 AM, steve uurtamo <uurtamo at gmail.com> wrote:

> just to expand on that second paragraph a bit:
>
> actually, you can represent a 4-move list on a 9x9 board, or a 3-move
> list on a 19x19 board in under 32 bits. total data transfer inbetween
> moves in this case would be on the order of 200MB, but thankfully, all
> of the tree bits are disjoint, so reassembly is simple, and pruning is
> uncomplicated.
>
> :)
>
> s.
>
> On Tue, Apr 5, 2011 at 11:06 AM, steve uurtamo <uurtamo at gmail.com> wrote:
> > the point of uniformly at random partitioning the space is that by a
> > simple probabilistic argument, most processors will be doing useful
> > work most of the time, and it requires no heuristics or
> > second-guessing. if you are really worried about the possibility of a
> > bad partitioning ruining the performance for the whole game, you can
> > always just repartition after each move. it's fast, requires a tiny
> > amount of communication, and is easy to implement.
> >
> > if you were super, super uptight about the possibility of there being
> > fewer useful moves to examine than processors (for instance, if you
> > had thousands of processors available), you could always partition at
> > the second level as well, either after narrowing down to a smaller
> > number of first moves, or just giving lists of allowed two-move
> > expansions for the first two moves. (on a 9x9 board this is entirely
> > reasonable, and on a 19x19 board this is still feasible).
> >
> > s.
> >
> > On Tue, Apr 5, 2011 at 10:57 AM, Daniel Shawul <dshawul at gmail.com>
> wrote:
> >> I doubt a domain partitioning strategy would solve the problem
> completely.
> >> The way I understand your explanation,root moves (points) are assigned
> >> randomly to processors.
> >> This is better than the naive partition since in Go many good moves are
> >> spatially close
> >> (maybe close to last move ?). But still more good moves could be
> assigned to
> >> one or two processors,
> >> and I don't think it is solvable with any static approach.
> >> Processors that get no good moves waste their time searching and
> expanding a
> >> useless part of
> >> the tree. If one processor has one good move and the other five, same
> >> problem still exists.
> >> From this point of view,allowing the processors to pick the first move
> from
> >> the whole list is better
> >> since it is dynamic. However it may have redundancy issues.
> >> So I think it is a compromise between load balancing Vs redundancy.
> >>
> >> On Tue, Apr 5, 2011 at 8:03 AM, steve uurtamo <uurtamo at gmail.com>
> wrote:
> >>>
> >>> i am coming late into this thread and apologize for the intrusiveness,
> >>> but i feel like i'm missing something here and thought that i'd give
> >>> my first thought.
> >>>
> >>> if the number of processors is fixed (i.e. you don't have to worry
> >>> about it increasing or decreasing over the course of the game), why
> >>> not partition the board?
> >>>
> >>> a naive partition (i.e. i have 4 processors, and processor one can
> >>> only examine first moves in the upper left quadrant of the board,
> >>> processor two can only examine first moves in the upper right quadrant
> >>> of the board, etc.) would have the problem that the only important
> >>> moves might be clustered all at one processor.
> >>>
> >>> a smarter partition would avoid this problem completely as long as the
> >>> number of first moves worth considering was on the order of the number
> >>> of processors -- randomly partition the board (it can be a fixed
> >>> random partition that never changes over the course of the game if you
> >>> want). so if you have P processors, assign every point on the board a
> >>> random floating point value, sort them by this value, take the first
> >>> 1/P fraction of points and assign them to processor #1, the next 1/P
> >>> fraction of points and assign them to processor #2, etc. this can be
> >>> done before the game even starts.
> >>>
> >>> so the rule should be that the first move examined for a given
> >>> processor must come from his assigned point list. it should be very
> >>> easy to force this to happen in an efficient way (i.e. you're just
> >>> randomly selecting the first move from a smaller list than all moves
> >>> afterward).
> >>>
> >>> s.
> >>>
> >>> On Tue, Apr 5, 2011 at 4:50 AM, Daniel Shawul <dshawul at gmail.com>
> wrote:
> >>> > Oh no I actually agree with you. But I share concerns of Joona about
> the
> >>> > kind of algorithm to be used.
> >>> > He probably used root parallelization scheme like I just did. It
> scales
> >>> > almost perfectly on a cluster of 16 cpus nps wise.
> >>> > But then I realized this might not be as good as it seems because the
> >>> > different processors might not produce
> >>> > significantly different trees.. Infact at first I wrongly seeded the
> >>> > random
> >>> > number generator to time(NULL) which
> >>> > gave me almost the same tree in all the processors. Then I modified
> that
> >>> > to
> >>> > include the processor id and it starts
> >>> > producing different trees, but I still think there is lot
> >>> > of redundancy in
> >>> > there. If I still use the same exploration constant
> >>> > UCTK all processors are going to explore more or less to the same
> depth.
> >>> > So
> >>> > the benefit will be a wider (i.e safer) search
> >>> > ,not necessarily deeper. The improvement from a 16x more computing
> time
> >>> >  (i.e shared tree) should be much more than the one I get
> >>> > by using this simple parallelization scheme. I am trying to introduce
> >>> > more
> >>> > selectivity by dividing  UCTK by number of processors N
> >>> > (i.e  UCTK / N). Does that sound reasonable ?
> >>> > On Tue, Apr 5, 2011 at 3:25 AM, Gian-Carlo Pascutto <gcp at sjeng.org>
> >>> > wrote:
> >>> >>
> >>> >> Those were single processor tests.
> >>> >>
> >>> >>
> >>> >>
> >>> >> I wanted to point out that your “speed is not a very big issue”
> guess
> >>> >> is
> >>> >> wrong and that the heaviness of the playouts doesn’t change that
> >>> >> either.
> >>> >> Strength scales strongly with playouts/speed. So something is
> limiting
> >>> >> your
> >>> >> result, and a bad parallelization can very well be it.
> >>> >>
> >>> >>
> >>> >>
> >>> >>
> >>> >>
> >>> >> From: computer-go-bounces at dvandva.org
> >>> >> [mailto:computer-go-bounces at dvandva.org] On Behalf Of Daniel Shawul
> >>> >> Sent: Tuesday, April 05, 2011 1:56 AM
> >>> >>
> >>> >> To: computer-go at dvandva.org
> >>> >> Subject: Re: [Computer-go] UCT parameters and application to other
> >>> >> games
> >>> >>
> >>> >>
> >>> >>
> >>> >> Something I am not clear about is the algorithm used. Or is it just
> a
> >>> >> test
> >>> >> on a single
> >>> >>
> >>> >> processor version by giving it more time to search?  If the tree is
> not
> >>> >> shared as in the 'root parallelization'
> >>> >> scheme, I have doubts if it can search 'deeper' even though nps
> scales
> >>> >> almost perfectly.
> >>> >> By deeper ,I mean more expansion to the best moves. Since the
> >>> >> processors
> >>> >> are not searching the same tree ,
> >>> >> it seems to me the search in parallel is wider (more alternatives)
> but
> >>> >> not
> >>> >> necessarily deeper searched.
> >>> >> Or is this taken care of by using a lower exploration constant (c)
> for
> >>> >> the
> >>> >> parallel search in the hope that
> >>> >> it would fill the void introduced by adding more selectivity ?
> >>> >>
> >>> >>
> >>> >> On Mon, Mar 28, 2011 at 5:49 AM, Gian-Carlo Pascutto <gcp at sjeng.org
> >
> >>> >> wrote:
> >>> >>
> >>> >> >However one of my early observations with Go programming has been
> >>> >> >that the speed is not a very big issue in this field (at least in
> >>> >> > lower
> >>> >> levels).
> >>> >>
> >>> >> >[...]
> >>> >>
> >>> >> >10x more processing power only gave around 100 extra elo points.
> >>> >> >
> >>> >> >
> >>> >> >Of course with heavy playouts and more fine tuned programs things
> can
> >>> >> >be very different...
> >>> >>
> >>> >> No. You probably have some other problem or bugs. See for example
> this
> >>> >> study:
> >>> >>
> >>> >> http://cgos.boardspace.net/study/13/index.html
> >>> >>
> >>> >> Leela Lite was using light playouts. The slope is a bit flatter than
> >>> >> the
> >>> >> real program, but not much more so. You should get far more than 100
> >>> >> ELO
> >>> >> for
> >>> >> a 10x speedup.
> >>> >>
> >>> >> --
> >>> >> GCP
> >>> >>
> >>> >> _______________________________________________
> >>> >> 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
> >>> >
> >>
> >>
> >
> _______________________________________________
> 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/20110405/1d8020fe/attachment.html>


More information about the Computer-go mailing list