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

[sylvain.gelly at m4x.org]

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 ?

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/