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

steve uurtamo uurtamo at gmail.com
Tue Apr 5 08:06:51 PDT 2011


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
>> >
>
>



More information about the Computer-go mailing list