[computer-go] transposition

[Don Dailey]

This sounds pretty good.   Let me see if I understand.   

Basically when you create children you do the lookup to calculate
zobrist keys and either find an existing record in the hash table or
create a new entry.  But after that, you just have pointers (or indices)
to the children of a node to save time having to look up all the
children.  

Is that correct?   It sounds like a pretty reasonable compromise between
space and time.

- Don


On Fri, 2007-05-11 at 12:49 -0400, Álvaro Begué wrote:
> We are using a compromise between the two options that Don described.
> We have a tree using indices to a big vector (which is about the same
> thing as pointers), and we have a separate structure that maps zobrist
> keys to indices in the vector, using a hash. This map is only queried
> when we add a position to the UCT tree. If we already have that
> position, we simply point to the existing node. If not, we add it to
> the map. The loss in speed is barely noticeable. But we haven't
> investigated carefully how much performance we are getting out of it,
> if any. It just seemed like the right thing to do.
> 
> Álvaro.
> 
> 
> On 5/11/07, Peter Drake <drake at lclark.edu> wrote:
> > On May 11, 2007, at 9:20 AM, Don Dailey wrote:
> >
> > > Going along with this, the numbers won't add up (although I don't know
> > > if that is important.)   In other words, if you do 10,000
> > > simulations at
> > > the root, all grandchildren will add up to more (due to
> > > transpositions.)
> > > If you propogate this up the tree you might come up with many more
> > > than
> > > 10,000 simulations at the root.
> >
> > As per the previous thread, it appears that one should not (even when
> > using a direct tree) assume that
> > the number of runs through the parent is the same as the sum of the
> > runs through the children.
> >
> > Your other comments match my experience.
> >
> > Peter Drake
> > http://www.lclark.edu/~drake/
> >
> >
> > _______________________________________________
> > computer-go mailing list
> > computer-go at computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/