[computer-go] transposition

[Álvaro Begué]

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/
>