[computer-go] On expanding the UCT tree

[Peter Drake]

On May 2, 2007, at 8:07 AM, Erik van der Werf wrote:

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

Right, that's why I said "ignoring the other children". In fact, they  
would all exist before I created a grandchild. Perhaps therein lies  
the solution: by the time child A has to actually use UCT to choose a  
move (because all of its children exist), it will have N children and  
have N+1 runs recorded locally. Since N is close to the size of the  
board, this may be insignificant.

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

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?

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