On Jul 6, 2009, at 10:09 PM, Peter Drake wrote:
I suppose I could also include first child / next sibling pointers.
I wouldn't actually use them when performing playouts, but they
would greatly speed up the mark phase of marking and sweeping.
Hmm. That would work for a tree, but this is a DAG.
Consider this situation:
A
/ \
B C
\ / \
D E
(For simplicity, ignore the fact that an actual transposition must be
at least three moves long.) Here D can be reached from either B or C,
but E can only be reached from C (perhaps due to ko).
With first-child/next-sibling pointers, that might look like this:
A
|
B-C
|/
D-E
If we then actually move to B and try to keep the tree, we'll end up
keeping E, even though it's really an unreachable node. That's
probably acceptable: we can keep a few unreachable nodes, as long as
we keep all of the real ones.
There might be another problem, though. Suppose, from the situation
above, I add F and G as children of B:
A
|
B-C
| \
F-G-D-E
Later, I discover that F is also a child of C. I look through C's
apparent children (D and E) and discover that F is not among them. How
do I add F to the list of C's children without some serious list
traversal (and surgery)?
Perhaps a better solution is for each node to point to a linked list
of its children. The nodes in these lists (allocated from a pool at
load time, naturally) would each point to a search tree node and the
next list node.
Peter Drake
http://www.lclark.edu/~drake/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
