[computer-go] On expanding the UCT tree

[Peter Drake]

On May 2, 2007, at 8:17 AM, Peter Drake wrote:

> On May 2, 2007, at 8:07 AM, Erik van der Werf wrote:
>
>> Don't you determine the sum of visits by adding all values in the
>> children? I guess it looks like a nice speedup to get the sum  
>> directly
>> from their parent, but does that really matter in comparison to the
>> playout complexity?
>
> Yes, I've been getting the sum directly from the parent. Since this  
> has to be done for each move chosen within the tree (which,  
> granted, is not nearly as common as choosing a move beyond the  
> tree), I thought speed was important.
>
> What are others doing?

I'm contemplating making the change you suggest. The following is my  
one concern.

Suppose, to keep the example simple, that there are only two choices  
at each ply. My tree is originally

ROOT 0

meaning that there is just one node with no playouts.

In the first playout, my first move is A, so then I have:

ROOT 1
	A 1

Now I try move B, updating the tree to:

ROOT 2
	A 1
	B 1

Fine so far. Now UCT likes A better, so the next playout starts with  
A, C, giving me:

ROOT 3
	A 2
		C 1
	B 1

Here's the problem. On the next playout, I'll want to look at the  
other alternative to A. In doing so, I will need to compute the UCT  
value of trying C again, especially if (as in the Gelly tech report)  
I don't automatically choose untried moves over tried moves. When I  
look through the children of A and count a total of one playout, it  
seems natural that I should update the playout count for A:

ROOT 3
	A 1
		C 1
	B 1

Now I actually add the new move:

ROOT 4
	A 2
		C 1
		D 1
	B 1

On the next playout, I will begin by looking through the children of  
ROOT and updating ROOT's run count:

ROOT 3
	A 2
		C 1
		D 1
	B 1

The tree is accurate now, but I've lost a playout! I will, in fact,  
lose one playout every time some node gains its second child. Is this  
acceptable?

(The number of playouts at the root doesn't really matter, except  
that I can't just count the number of runs through the root to see  
how many playouts I did. More important is that every time some node  
in the subtree rooted at node X gains a second child, X loses a  
playout.)

Peter Drake
http://www.lclark.edu/~drake/