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

[Peter Drake]

On Jul 25, 2006, at 12:05 PM, Rémi Coulom wrote:

> Peter Drake wrote:
>> 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.
>
> Your misunderstanding may come from your confusion of what I call  
> internal nodes with nodes stored in memory. The complicated backup  
> and selectivity I describe in my paper are applied to internal  
> nodes only. A node of the tree is promoted to internal once it has  
> received 81 visits. Only a very smal proportion of all the nodes  
> store in memory is promoted to internal node.

Sorry, I was using "internal" to mean "having at least one child",  
not in the more restricted sense you use it in the paper.

> When the number of simulations that have passed through a node is  
> small, the value of the node is the average outcome. So there is no  
> loss of information for not storing information about its children.  
> The loss of information incurred by my node-allocation scheme  
> starts to have an effect only when many random games have passed  
> through this node. I expect the loss is much less than 1%.

Okay, let me see if I have this right.

You have a node A. You do a run that goes from A through B. You do  
not create a node for B, but you do store the result of the game in A.

Now you do a second run through A and then C. This does create a node  
for C. However, the game result is added (?) to the result already  
stored in A, and A's run count is incremented. Thus, to get the  
average value of A, you take this sum and divide by 2, getting the  
correct value even though the game that went through B is no longer  
in the tree.

By the time you promote A to internal (in your sense), it has many  
children, so basing the value on the existing children and ignoring  
the one "lost" game doesn't hurt much.

Is this correct?

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