[computer-go] Transpostions in UCT search
A while ago I implemented what I thought was a fairly straightforward way to deal with transpositions. But to my surprise it made the program weaker instead of stronger. Since I couldn't figure out immediately what was wrong with it, I decided to leave it alone for the time being. Just now I decided to do a search on transpostions and UCT in this mailing list and it seems to have been discussed several times in the past. But from what I found it's not entirely clear to me what was the conclusion of those discussions. Let me first describe what I did (ar attempted to do): all nodes are stored in a hash-table using a checksum. Whenever I create a new node in the tree I add it in the hash-table as well. If two nodes have the same checksum, they are stored at the same slot in the hashtable in a small list. When I add a node to a slot that already contains something, then I use the playout statistics of the node(s) already there and propagate that up the tree. When I have done a playout I propagate the result of the single playout up the tree, but at each step I check in the hashtable to see if there are multiple paths to update. I've seen some posts that expressed concerns about using the existing statistics of another path. This may be the reason I'm not seeing any improvement. So I was wondering if there's any consensus about how to deal with transpositions in a UCT tree. Or if someone could point me to other sources of information on the subject. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpostions in UCT search
- Original Message From: Mark Boon [EMAIL PROTECTED] snippage Let me first describe what I did (ar attempted to do): all nodes are stored in a hash-table using a checksum. Whenever I create a new node in the tree I add it in the hash-table as well. If two nodes have the same checksum, they are stored at the same slot in the hashtable in a small list. When I add a node to a slot that already contains something, then I use the playout statistics of the node(s) already there and propagate that up the tree. Am I reading this right? Are all nodes in the same slot considered equivalent? Could some of these nodes be collisions? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpostions in UCT search
On 27-okt-08, at 11:51, terry mcintyre wrote: - Original Message From: Mark Boon [EMAIL PROTECTED] snippage Let me first describe what I did (ar attempted to do): all nodes are stored in a hash-table using a checksum. Whenever I create a new node in the tree I add it in the hash-table as well. If two nodes have the same checksum, they are stored at the same slot in the hashtable in a small list. When I add a node to a slot that already contains something, then I use the playout statistics of the node(s) already there and propagate that up the tree. Am I reading this right? Are all nodes in the same slot considered equivalent? Could some of these nodes be collisions? Yes, all the nodes in the same slot are considered equivalent. They're not collisions. If a node hashes to a slot with a different checksum, it keeps looking for an empty slot. If it doesn't find an empty slot it throws out some nodes to which it collided. Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpostions in UCT search
When a child has been sampled often through some other path a naive implementation may initially explore other less frequently visited children first. The new path leading to the transposition may therefore suffer from some initial bias. Using state-action values appears to solve the problem. Erik On Mon, Oct 27, 2008 at 2:21 PM, Mark Boon [EMAIL PROTECTED] wrote: A while ago I implemented what I thought was a fairly straightforward way to deal with transpositions. But to my surprise it made the program weaker instead of stronger. Since I couldn't figure out immediately what was wrong with it, I decided to leave it alone for the time being. Just now I decided to do a search on transpostions and UCT in this mailing list and it seems to have been discussed several times in the past. But from what I found it's not entirely clear to me what was the conclusion of those discussions. Let me first describe what I did (ar attempted to do): all nodes are stored in a hash-table using a checksum. Whenever I create a new node in the tree I add it in the hash-table as well. If two nodes have the same checksum, they are stored at the same slot in the hashtable in a small list. When I add a node to a slot that already contains something, then I use the playout statistics of the node(s) already there and propagate that up the tree. When I have done a playout I propagate the result of the single playout up the tree, but at each step I check in the hashtable to see if there are multiple paths to update. I've seen some posts that expressed concerns about using the existing statistics of another path. This may be the reason I'm not seeing any improvement. So I was wondering if there's any consensus about how to deal with transpositions in a UCT tree. Or if someone could point me to other sources of information on the subject. Mark ___ 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/
Re: [computer-go] Transpostions in UCT search
[EMAIL PROTECTED] wrote on 27-10-2008 14:57:54: On 27-okt-08, at 11:51, terry mcintyre wrote: - Original Message From: Mark Boon [EMAIL PROTECTED] snippage Let me first describe what I did (ar attempted to do): all nodes are stored in a hash-table using a checksum. Whenever I create a new node in the tree I add it in the hash-table as well. If two nodes have the same checksum, they are stored at the same slot in the hashtable in a small list. When I add a node to a slot that already contains something, then I use the playout statistics of the node(s) already there and propagate that up the tree. Am I reading this right? Are all nodes in the same slot considered equivalent? Could some of these nodes be collisions? Yes, all the nodes in the same slot are considered equivalent. They're not collisions. If a node hashes to a slot with a different checksum, it keeps looking for an empty slot. If it doesn't find an empty slot it throws out some nodes to which it collided. Do you mean the Graph History Interaction ? (GHI) If you implement (some kind of) superko, the result of the evaluation ( = playouts) *should* depend on the path taken. For simple ko, the path is not relevant, IMHO. There may also be some information-theoretic complications (propagating twice means that some measurements are counted twice, while they have been estimated only once. This _could_ lead to inflation, because you underestimate the variance in these branches)I am not a statistician. YMMV. AvK ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpostions in UCT search
On 27-okt-08, at 12:45, Erik van der Werf wrote: Using state-action values appears to solve the problem. What are 'state-action values'? Mark ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Transpostions in UCT search
Reinforcement Learning terminology :-) In Go the state is the board situation (stones, player to move, ko info, etc.), the action is simply the move. Together they form state-action pairs. A standard transposition table typically only has state values; action values can then be inferred from a one ply search. In a full graph representation the state-action values are the values of the edges. Erik On Mon, Oct 27, 2008 at 4:03 PM, Mark Boon [EMAIL PROTECTED] wrote: On 27-okt-08, at 12:45, Erik van der Werf wrote: Using state-action values appears to solve the problem. What are 'state-action values'? Mark ___ 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/
