This is almost exactly the same way I do it in Many Faces. > -----Original Message----- > From: [email protected] [mailto:[email protected]] > On Behalf Of Thomas Lavergne > Sent: Tuesday, May 11, 2010 8:40 AM > To: [email protected] > 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 > > [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
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
