I was also hoping to use my DAG as a transposition table, so I could
use the Zobrist hash of the current position to find where the child
node would be if it existed. If the space was already occupied (by a
node at the right depth), I would have a transposition.
If each "node" might really require several nodes, this trick won't
work. Oh, well. I guess I was trying to kill too many birds with the
same stone.
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 3:46 PM, Anders Kierulf wrote:
Is anyone storing a search DAG (as opposed to a tree) and
using the firstChild/nextSibling representation?
When you traverse children (e.g., in UCT) you have to
know which move is associated with which child node. If a
node might have more than one parent, the node can't store
its last move.
SmartGo uses a DAG for tactical proof number search, and is using the
firstChild/nextSibling representation. Different moves leading to
the same
position are given their own node (a twin node), and that node then
points
to the base node on the same level. Any information about the
position is
stored in the base node; any information related to the move played is
stored in the twin nodes.
For tactical search, a DAG is a clear benefit; the extra space is
certainly
worth it. In my current implementation, each node contains pointers
to the
base node and to the next twin node, but that could be reduced to a
single
pointer linking the twin nodes in a circular list plus a bit to
indicate the
designated base node.
Anders Kierulf
www.smartgo.com
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
