Correct. Following David Fotland's suggestion, each node contains
arrays of the run and win counts of its (potential) children. This
way, searching the children of a node does not cause a cache miss.
When using RAVE (on which I'm still working), I also need arrays for
RAVE runs and counts through each child.
These are all Java chars (effectively 16-bit unsigned ints). On 9x9,
that's 81 * 2 * 4 = 648 bytes. Some other info pushes this up to
around 1k.
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.
Yes, I think this would be an improvement. Thanks!
Peter Drake
http://www.lclark.edu/~drake/
On Jul 6, 2009, at 8:15 PM, Michael Williams wrote:
I thought you had really heavy nodes? Like 1k bytes or so? But no
8 byte pointers to children?
Peter Drake wrote:
Well, there is one slight catch...
Nodes do not contain pointers to their children. To find the node
after making a move, I make the move on the board, then use the
Zobrist hash of the new board as a key to search for the child node
in the hash table. So traversing the tree would involve re-playing
all of the moves from the root. Worse, in the interest of speed, my
play code (modeled on LibEGO) doesn't support undoing. To do a
recursive traversal like this, I therefore have to perform a board
copy every time I backtrack.
On the other hand, I think I could get away with only traversing
the part of the tree that is still relevant (probably a small
fraction of the nodes in use), then traversing the set of nodes
linearly to rebuild the free list. In other words, I would perform
a mark-and-sweep garbage collection.
Peter Drake
http://www.lclark.edu/~drake/
On Jul 6, 2009, at 8:02 PM, Michael Williams wrote:
If you are talking about 128k nodes, I don't think traversing them
will take very long.
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
