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