Re: Incremental Data Structures

[Tim Klinger <klinger@xxxxxxxxxx>]

Hi Matt,

At 06:04 PM 8/19/98 -0500, Matt Gokey wrote:
>I took a look at your implementation.  It looks like a pretty
>straightforward design and easy to use, but I would think its performance
>in a search examining many positions would not be all that good.

It's not really possible to define this question well without some
formalization of how much of the state is left unchanged by playing a move
(the "locality").  So, the answer may be different depending on what and
how much information you think it is valuable to compute each turn.  If you
meant search specifically in the context of our program, then an answer
would require implementing it both ways and comparing.  This isn't
something we've done or plan to do.
 
>Could you comment on your revertable system's performance characteristics
with
>regard to memory usage, memory fragmentation, and CPU cycles? 

Not quantitatively.  But on the bright side, I'm not really sure how you
could make much use of this information anyway except perhaps to say "It
uses too much memory for me." or "It will never finish a game on today's
fastest computer".  All I can say is that it performs very reasonably for
what we want in a go program (lots of knowledge and no huge searches) on a
266 MHZ pentium with 128 MB of memory (most of which is not used).

I suspect that the best measure of the system's usefulness will come
anecdotally if enough people decide to use it.

Tim