RE: Incremental Data Structures

[Philipp Garcia <phil@xxxxxxxxxx>]

I want to thank everyone who responded to my e-mail regarding
Incremental Data Structures; especially David Mechner for sharing his
Revertable class. 

I was wondering if anyone had considered using a copy-on-write scheme
for GO data. In such a scheme, several object can share a data
structure. When an object method is called that requires a change to the
data structure, then that object first copies the data structure
somewhere else and then modifies the copy (if the data structure is not
shared, no copy is necessary). This technique is common in UNIX
operating system so that if five copies of "who", for example, are
running, only one copy would actually resigned in physical memory; each
process should share the memory (see Andrew S. Tanenbaum "Modern
Operating Systems for more information). Generally this scheme is
implemented using reference counting and additional (but not required)
with smart pointers in C++ (see Scott Meyers "More Effective C++" for
detailed information and sample code).

I was wondering if this approach would be feasible and more efficient in
a GO playing program as an alternative to methods which either record
"undo" information, or make copies of the data structure before each
more. Has anyone attempted this? Comments?

-----Original Message-----
From: Philipp Garcia [mailto:phil@xxxxxxxxxxxxxxxxx]
Sent: Friday, August 14, 1998 2:38 PM
To: 'computer-go@xxxxxxxxxxxxxxxxx'
Subject: Incremental Data Structures



I have a question for those that have written go-playing programs that
use incremental updates to maintain data structure like string-lists,
liberties lists, etc... When you take-back a move, do you "undo" the
modifications to the data structures OR do you revert back to a copy of
the data structure before the move that you are taking back was placed?
If you "undo" the modifications, how do you store "undo" information. Is
it log based similar to how modern databases work? Or does logic direct
the "undo"? If you revert back to a copy, do you really save enough CPU
cycles to even justify using incremental structures rather than a full
re-computation?