[Computer-go] effectiveness of transposition tables for go

Don Dailey dailey.don at gmail.com
Mon May 10 15:44:41 PDT 2010

On Mon, May 10, 2010 at 6:33 PM, Petr Baudis <pasky at ucw.cz> wrote:

>  Hi!
> On Mon, May 10, 2010 at 06:05:58PM -0400, Don Dailey wrote:
> > As far as the caching issue is concerned,  (to answer Peter) I assumed
> that
> > all goes out the window with any of these schemes.   I don't know what
> Peter
> > is proposing as an alternative.   Tree's with pointers are not exactly
> cache
> > friendly and in Mark's scheme he has trees with pointers and an
> additional
> > non-cache friendly hash table with lists of pointers.   Are those lists
> of
> > pointers also linked lists?
>   Trees with pointers are pretty cache friendly since usually you expand
> the node in a single go, yielding continuous memory space for all the
> children instead of the children being spread uniformly over all the
> memory as in case of hash tables.
>  (Note that by "cache friendly" I mean not only "fitting and staying in
> the cache", but also "getting into the cache" - continuous region means
> automatic prefetching works great.)
> > With heavy playouts,  I believe accessing the child nodes using ANY
> scheme
> > is relatively cheap - when compared to the time you spend playing an
> entire
> > game using heavy playouts.   It might start to matter if you are using a
> > really fast uniform random super light playout, but no strong program
> does
> > that anymore.
>   My profiles of Pachi show that I spend about 30% of time on RAVE
> descend and propagation. I have just started optimizing again after
> some time though so I didn't have time to oprofile this in detail yet.
> My tree data structure actually rather sucks, though.

Yes, I agree with everything you said.   Fitting in cache is an issue too of

If you spend 30% of the time on the tree the issue is whether you have a
good or bad implementation (performance-wise) and how much this would
improve (or worsen) relative to some other data structure.   I suspect that
most of this time is constant and that it probably would only make a small
difference doing any other reasonable scheme.      I could be wrong but this
is usually how it works with me unless I actually identify a real issue that
I can fix.

> --
>                                Petr "Pasky" Baudis
> When I feel like exercising, I just lie down until the feeling
> goes away.  -- xed_over
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20100510/3f354f6d/attachment.html>

More information about the Computer-go mailing list