[Computer-go] effectiveness of transposition tables for go
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:
> 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
> > all goes out the window with any of these schemes. I don't know what
> > is proposing as an alternative. Tree's with pointers are not exactly
> > friendly and in Mark's scheme he has trees with pointers and an
> > non-cache friendly hash table with lists of pointers. Are those lists
> > 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
> > is relatively cheap - when compared to the time you spend playing an
> > 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
> > 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Computer-go