[computer-go] More UCT / Monte-Carlo questions

[Gunnar Farnebäck]

David Fotland wrote:
 > Can you elaborate on what is in a node, and what you mean by expand?   I
 > assume you have simple node, where each node represents a position and
 > the single move to get there.  Then when you find a node with no
 > children and expand it, you allocate up to 81 new nodes, but you only
 > make one random playout.  If uct picks a different leaf next time, you
 > end up with most of the leaf nodes never visited.  In this case you run
 > out of memory quickly.  If there are a few hundred K playouts to pick a
 > move, and 90% of the leaves have no visits, then you need over a million
 > nodes of memory.
 >
 >
 >
 > How do other programs handle this?  I see that aya has an array of all
 > children in each node.  This still means allocating memory for all
 > children when a new node is allocated.

MonteGNU has a linked list of visited children and a bitboard marking
moves which have not yet been visited. A new node is created without
children and the bitboard marks all possible moves.

 > It think many programs run several simulations through a node before
 > allocating the children.  I can see how this saves memory, but then how
 > do you save the RAVE information from the early simulations?

I have never managed to implement RAVE successfully. It made my
program significantly slower but no stronger even at a fixed number of
simulations.

/Gunnar