In previous versions of Orego, I have added one node per playout. I
just changed that to add a child to a node only if that node has at
least A runs, where A is the area of the board (e.g., 81). This seems
to make the program stronger, if only because it allows me to get in
more runs. Specifically, it allows me to get (a bit) more out of my 4-
processor-core machine, because the parts where the threads have to
synchronize on the tree (generating in-tree moves and incorporating
the playout) are shorter.
Remi (and, I think, others) were already doing this. I wasn't,
because I got the idea into my head that this would be throwing away
information. It is, but it's throwing away information that you're
almost certainly not going to use. If a move is truly bad, random
playouts will generally reveal this; it's not worth constructing a
subtree to figure out WHY it's bad.
Has anyone tried requiring more than A playouts before adding a child
to a node? This seems an arbitrary threshold, but I have no idea how
(other than empirically) to find the right tradeoff between tree
search and preemptive sampling.
On a related note, where are people applying heuristics? I see three
possibilities:
1) Incorporate heuristics into the UCT formula.
2) Use heuristics to order moves added as children to tree nodes that
don't have all their children yet. It is possible to preemptively
prune here, never exploring some moves that are rated as awful in the
heuristics.
3) Use heuristics in the playouts.
I have (recently) avoided 3, on the theory that the playouts need to
be very fast and are largely nonsensical. Given my new realization
that the playout threads are often waiting for the tree anyway, this
may not be valid. Again, it's a question of finding the right balance...
Peter Drake
http://www.lclark.edu/~drake/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
