[computer-go] UCT tree pruning
Pebbles prunes least recently used nodes. This eliminates nodes from previous searches first, and then nodes from the current search. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] UCT tree pruning
> Pebbles prunes least recently used nodes. This eliminates nodes > from previous searches first, and then nodes from the current search. Why do you keep nodes from previous searches? By search, do you mean a "genmove"? How do you store which nodes are oldest (queue, heap)? -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Tweak to MCTS selection criterion
I did this, stopping search if other moves mathematically couldn't catch up. I found that the savings in percentage of total nodes depended on how many playouts the program did. The larger the number of playouts, the larger the savings. I also made a rule where after a certain percentage of the total playouts, if one node is far ahead but theoretically another could still catch up, I'd still terminate, which doubled the savings. I don't have the details here but I remember this way I got equal winning-rate at 32K playouts with these rules vs. 64K playouts without. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] UCT tree pruning
>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
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
