[computer-go] Pay-as-you-go cluster?

[Don Dailey]

On Mon, 2006-10-02 at 14:20 +0200, sylvain.gelly at m4x.org wrote:
> I agree it seems good ideas. I have thought about that. The problem is 
> precisely in how to combine all the trees into a single tree ? You may think 
> at simply taking mean of values if the same node exists, and adding nodes if 
> not ? I am not sure that it would give good results. 
> Do you think at this way to combine trees ?

I doubt this is the BEST idea,  I just threw it out there as a
possibility.   

It is efficient in terms of parallelism, but I'm sure it is not as good
as doing the same amount of work on a single processor.   In fact, I'm
sure there would be plenty of redundant work that a serial program would
not perform.

Of course it is easy to merge the tree's together.  You just sum the
counts and results of all identical nodes.

I probably wouldn't pass the WHOLE tree either as this could be
expensive.  You could probably get most of the benefit if you chopped
off the leaf nodes.

With idea 1 you only need to pass the root node itself.

- Don



> Sylvain
> 
> 
> > Here are a couple of ideas that are efficient in terms of parallelism:
> >
> >   IDEA 1
> >
> >    1. Start all nodes searching the root position.
> >    2. At timeout, combine all the stats from each node.
> >
> >   IDEA  2
> >
> >    1. Start all nodes searching the root position for a predetermined
> >       small chunk of time, perhaps a second or two.
> >
> >    2. Merge all the tree's produced together into a single tree.
> >
> >    3. Distribute new tree to all nodes and repeat.
> >
> > - Don
> >
> > On Mon, 2006-10-02 at 10:45 +0200, sylvain.gelly at m4x.org wrote:
> > > Le Lundi 02 Octobre 2006 10:25, Darren Cook a écrit :
> > > > > as we have access here to an interesting cluster, I have worked
> > > > > several weeks on a way to efficiently distribute UCT. ...
> > > > > I have tried a lot of solutions, which seemed good ideas, but none of
> > > > > theses were so far successful.
> > > >
> > > > I was about to suggest the first few ideas that came to mind but you've
> > > > probably already thought of them.
> > >
> > > Perhaps, but often the first few ideas are the best, so please go ahead
> > > :-).
> > >
> > > > Would you be willing to post about the
> > > > ideas you've already tried that failed?
> > >
> > > I'll try. I hope it will be clear enough.
> > >
> > > - basic try: giving to each machine one possible move (assume that you
> > > have enough machine), and each machine compute the value for this move.
> > > It is not a real parallelization of UCT, but it was so simple that I
> > > tried. You don't win so much this way.
> > >
> > > - Basic unit: a node (a position). This is the chunk. Then the client
> > > compute all possible results for this position, that is to say, for each
> > > possible move, the result of one simulation. Then the data to send back
> > > is only numberOfMoves bits.
> > >   - Then imagine you have one server which keep the tree, and n clients.
> > >   - The server use normal UCT, and when it encounters a leaf in its tree,
> > > if this node is not already in a client, send it to a client, and do its
> > > simulation as usual.
> > >   - When the data from the client comes back, you update the tree as if
> > > all the simulations where done by the server.
> > > The BIG problem here is that you introduce a big bias in the algorithm.
> > >
> > > - Variant: instead of computing all the possible moves from a child,
> > > compute only a part (m moves). The problem is that if m is too small, the
> > > network delay is too big, and if m is too big, you have the previous
> > > problem. - Variant: when the message comes back, instead of updating tree
> > > as UCT would update it, keep the same number of simulations for each
> > > node, but update the probability using the new simulations you get.
> > > - Variant: when the message comes back you don't update the tree, but
> > > keep the result in an hashtable for further use. Then the UCT algorithm
> > > is not changed at all, but you don't win so much speed that way.
> > >
> > > I have tried some others small variants on this idea. I have also though
> > > about keeping a tree for each machine, and try to synchronize it as often
> > > as possible using the information from the others. But I think it would
> > > be very complicated, and I am not so convinced that it would be possible
> > > to keep the tree consistent.
> > >
> > > I hope the ideas are not too badly exposed.
> > >
> > > Sylvain
> > >
> > > _______________________________________________
> > > computer-go mailing list
> > > computer-go at computer-go.org
> > > http://www.computer-go.org/mailman/listinfo/computer-go/
>