>Why do you keep nodes from previous searches?
All of the descendants of the move you choose are relevant to
future searches. Plus whatever nodes can be reached by transposition.
(In Go, there are a lot of transpositions.)
>By search, do you mean a "genmove"?
Move generation and pondering.
> How do you store which nodes are oldest (queue, heap)?
I put a 32-bit counter in each node. The entries of the node hash table
are linked lists. We will replace the oldest of the nodes in the same
hash bucket as the node we are inserting. When the hash table is "full,"
the average list length is about 16 or so. So it is the rough equivalent
of a 16-probe table.
Here is the code that calculates whether an entry is oldest.
callCount is a static uint32_t that represents the age of the
next node to be inserted:
if (entryToReplace == 0) {
entryToReplace = p;
}
// The following is written oddly, since it looks like you can just
subtract
// callCount from both sides, but that does not take into account
what happens
// when callCount "wraps around". In that case, the expression below
will still
// replace the oldest item, provided that we do not have 2^32 nodes
in any
// single search.
//
else if (callCount - p->getCallCount() > callCount -
entryToReplace->getCallCount()) {
entryToReplace = p;
}
I don't think Pebbles has ever played long enough for callCount to
"wrap around." It would require something like 2000 consecutive games
on its current hardware.
Brian
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
