[computer-go] Is Crazy Stone throwing away half its work?

[Rémi Coulom]

Peter Drake wrote:
> We were looking at Coulom's paper on Crazy Stone and something gave us 
> pause.  Near the end of section 2, he explains:
> 
> "Whenever a random game goes through a node that has been already 
> visited once, create a new node at the next move, if it does not already 
> exist."
> 
> Suppose I create node A. The next move, B, is not used to create a new 
> node. I finish the game through B and store the value of this final 
> position in A. Later I come back through A and randomly make move C. 
> Since I've been through A before, I create a node for C. I then complete 
> that game, creating no new nodes, and back the value up to C.
> 
> Do I also back the move up to A? If so, isn't the game that was played 
> through B forgotten (and therefore wasted)?

I am not sure what you mean by backing the move up to A. Each node has a 
counter that counts the number simulations that were run through this 
node, and the total outcome of these simulations. So whenever a random 
game is finished, all the counters of all the nodes that this random 
game crossed are updated. In your example, this would include C and A.

This sentence in the paper was to explain how I store the search tree. I 
cannot store the whole tree of complete random simulations, because it 
would take far too much memory. So I create a node in memory only if the 
parent was already in memory before this simulation.

This scheme may incur some losses, in the following situation. Let's 
suppose I start with only one node at A. I run one first game that 
starts at A, then goes to B, then to C, then continues to the end. This 
has the effect of creating a node for B. But there is still no node for 
C. Later, when another random game starts by A, B, C, a node for C is 
created. The result of this simulation is stored in C, but the first 
simulation that went through C has been forgotten.

In practice, I don't believe this loss is significant. If you really 
want to avoid this loss, you could create a new node each time the 
grand-parent was already created before the current simulation. There 
would still be losses, but an order of magnitude less. This would 
require twice more memory.

I hope this is clearer now.

Rémi