Re: Incremental Data Structures

[David Mechner <mechner@xxxxxxxxxxxxxxxxx>]

The main point is that our revertible system is simple and easy to use
and it works. You only have to do one thing: make sure save() gets
called in each member function before member data is changed, and
you're guaranteed correct reversion.

We specifically wanted to avoid treating each data structure and
algorithm individually, because writing and debugging backtracking
routines is tricky and time consuming.

I could make further arguments "from intuition" for the efficiency of
our revertible system, but maybe that would be pointless. All I can
say with confidence is that in the case where most of the state stays
the same from move to move, it's not glaringly inefficient, and in our
program it uses a small fraction of cpu time and we haven't run into
memory problems.

I think there's a trap for all of us in computer go, which is the
impulse to put lots of time and effort into things that we know how go
about doing - like interface, or optimizing for memory and cpu time -
instead of the things that are hard and confusing - making the
computer play go.

-David


Matt Gokey wrote:
> IMHO, I feel an incremental system using algorithms implemented in
> concert with data structures designed to be revertable/incremental
> using deltas only would work more efficiently especially if paired
> with custom allocation/deallocation using a combination of
> pools/dynamic allocation by object type to prevent fragmentation
> problems.  

-- 
David A. Mechner            Center for Neural Science
mechner@xxxxxxxxxxxxxxxxx         4 Washington Place, New York, NY 10003
212.998.3580                http://cns.nyu.edu/~mechner/