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.
--
Petr "Pasky" Baudis
When I feel like exercising, I just lie down until the feeling
goes away. -- xed_over
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
