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

[Peter Drake]

On Jul 25, 2006, at 11:00 AM, Rémi Coulom wrote:

> 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.

I can see how A's counter would be updated, but how is A's value  
updated?  It would seem to require the average value of the node for  
C and the (never-created) node for B.

> 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.

What if, instead of a second ABC.. run, you have an ABD... run?   
Wouldn't this also throw out the information acquired on the run  
through C?

If so, it seems that this would be significant, because (barring the  
coincidence of choosing C twice in a row) every time a node becomes  
internal a run is discarded, throwing away nearly half your runs.

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/