[Computer-go] effectiveness of transposition tables for go

David Fotland fotland at smart-games.com
Tue May 11 09:22:24 PDT 2010


This is almost exactly the same way I do it in Many Faces.

> -----Original Message-----
> From: computer-go-bounces at dvandva.org
[mailto:computer-go-bounces at dvandva.org]
> On Behalf Of Thomas Lavergne
> Sent: Tuesday, May 11, 2010 8:40 AM
> To: computer-go at dvandva.org
> Subject: Re: [Computer-go] effectiveness of transposition tables for go
> 
> 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
> > Computer-go at dvandva.org
> > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
> >
> 
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go




More information about the Computer-go mailing list