Re: computer-go: Data structures

[A van Kessel <Adriaan.van.Kessel@xxxxxxx>]

Undo does not like dynamic allocation.
You can solve that by adding an extra
layer of indirection, which slows things
down. One way to do that, is to use a
"symbolic" undo/redo method: instead of
storing the bare {pointer+size+before_image+after_image}
, you can store the "opcode" + pre/after images.
This can also help debugging :-[

Redo is even more picky; you'll have to make
sure that the starting position is the same.

Another factor in datastructure design is
locality of reference. You need tight memory
structures, to avoid "cache trashing".
For go programs, this has not yet become a factor,
for chessprograms, it already is.

For storing the chain-members (and edges) I
use bitmaps, which are very cheap for {insert,delete,test}
, but rather costly for iteration.

Many programmes use a "union find" method for
storing chain/group membership. Every member
has an uplink to the previous member, and the
leader of the pack (the root of a tree) has 
a link to the chain's data, mostly coded with
an opposite sign.
For "generalised redo" , the UF method is not
appliccable, because the tree structure depends
on the order of the moves that built it.

Many people maintain more copies of the board,
in different rotations/mirrored, or with colours
swapped.

AvK