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

[Darren Cook]

Sylvain's early ideas were basically the first one's I thought of.

> One UCT per each CPU? then, merge results?

Yes. How about the master machine does a simple 2-ply minimax, and for
the evaluation of each leaf node it calls another CPU (*) and that does
the UCT monte carlo.

*:asynchronously: once all leaf nodes have replied the minimax tree is made.

I.e. a branching factor of 9-10 will use up 100 CPUs. You can use the
knowledge gained from the leaf nodes on the previous turn to help the
master machine order moves.

Once the best move is chosen 10% of the CPUs will be on the mainline so
they broadcast their in-memory trees to the other 90%. (I.e. this is
done on the opponents thinking time.)

Admittedly you've only gained two ply from 100 times the processing
power! Perhaps the master machine can be more selective and search
deeper. Maybe the UCT trees at the nodes get half the time (i.e. lower
quality) but get called twice per search to allow the master machine
twice as many leaf nodes.

David Doshay has a paper on this subject; I wonder if UCT is a better
leaf evaluator than GnuGo?

Darren

P.S. Since I started typing this I see a couple more ideas have come
through... I think the above is similar to what Remi is saying, but I'm
suggesting minimax fixed depth, instead of UCT on the master node. UCT
may be more efficient.