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/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
