[computer-go] On expanding the UCT tree

[Erik van der Werf]

On 5/1/07, Peter Drake <drake at lclark.edu> wrote:
> Like most of the UCT programs (I believe), Orego adds one tree node per
> Monte Carlo run. At present, this node includes data from the run that
> created it. Thus, after the first run, my tree looks like this:
>
> ROOT: 1/1 wins
>  CHILD A: 1/1 wins
>
> Ignoring the other children, I eventually do another run through that child,
> getting this:
>
> ROOT: 1/2 wins
>  CHILD A: 1/2 wins
>  GRANDCHILD B: 0/1 wins

Let's see if I get this.

You have a just added a grandchild so does that mean that all children
of root have been explored? If not, why do you add a grandchild?

Here I would expect to see CHILD B expanded, not some grandchild.

>
> My concern here is that that there have been two runs recorded in node A and
> only one in node B. Does this cause a problem for the UCT formula, which
> assumes that the number of runs through a node is the sum of the number of
> runs through the children?

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?

Best,
Erik