Hi,
as it seems people that their is a lot of different approach of transposition
tables, I just want to put my grain of salt here. This is an explanation of how
it works in my engine.
I've a big hash table of node. As in a tree, each node refer to a goban
position but doesn't store any explicit pointer to his child. Instead, I store
in node the information needed by UCT to go down in the virtual tree: number of
playout that have gone through this node with winrate and same for each childs.
So, when I want to do a playout. I first make a copy of the goban and repeat
the following :
- get the node corresponding to the current goban
- if no node was found, go to the out of tree playout
- else select one childs using UCT and informations stored in the node
- play the move on current goban
This means that I don't need any explicit link to childs node or anything else.
All transposition are handled automatically. I keep the list of traversed node
during this step and update them at the end.
This also mean that I update only the node I've traversed during this run, so
other implicit parents of nodes are not updated. Choosing the next child of a
node is always done localy in this node I never have to go in another node to
get informations.
So when I select a child I use only the winrate of choosing this specific child
from this specific position, not choosing any child from any goban who have
lead to the same target position. I think this is cleaner.
But, this also mean that my nodes can be a bit heavy. I use some tricks to
reduce this but they are still heavier that the nodes of most of other
programs. So I run into out of memory quicker than other programs. I handle
this by using a time marker in my nodes that I update each time I pass through
a node. When I need to add a new node and there is no more free one, I search
an old one in his neighboring and use it instead, so I discard old nodes
automatically.
This scheme allow me to allocate the full table of node at the start using all
memory available and don't care about this later. When I play a stone, I don't
care about freeing unreachable nodes as they will be automatically be replaced
by newer nodes later.
This also give pondering for free as I let my thinking function run forever,
just updating it's root position when a stone is played.
Opposed to other people here, I've implemented it this way as it seems to me
way more simple that getting a tree version right. If you take care of not
wasting too much memory in your node it's very efficient and very cache
friendly as all information needed for getting the next child is stored in the
node itself. And getting the next node from the hashtable is easy as you just
need its zobrist hashkey and you compute it when playing the stone.
I hope this will help some of you to understand how hashtable can allow very
efficient tree traversal.
Tom
Le 11 mai 2010 à 16:34, Mark Boon a écrit :
>
> On May 10, 2010, at 11:09 PM, Petr Baudis wrote:
>
>>> OK. Then I'm curious, was the solution something along the lines what
>>> Don described?
>>
>> I admit I got a bit lost in who described what. ;-)
>
> Whether you store some information about each successor in the node or if you
> compute the hash-key for each child while you get its win-rate.
>
> Mark
> _______________________________________________
> Computer-go mailing list
> [email protected]
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
