computer-go: Empty board spaces management

[Bryan McQuade <bmcquade@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

Hi again.  I would like to thank everyone for your responses on an unmake 
move method.  We found them all very helpful (and I hope some of you did as 
well).  We decided to implement an unmake move method rather than copy state. 

Now, we are debating how to tackle empty region management.  We would like 
to update data structures that manage empty parts of the board as the game 
moves along.  Our first thoughts were to look at the empty board as one big 
eye of sorts.  We would consider the empty regions of the board one big eye 
until two regions were completely separated from one another by stones (ie: 
once a corner was sealed off, the corner would become its own "eye" separate 
from the rest of the empty spaces on the board).  However, we found it very 
difficult to keep track of this information efficiently (time-wise).  It 
seems logical to partition the board into empty regions as pieces are played 
which split free areas (this will be especially helpful in determining eye 
spaces).  However, the search required to identify all separate regions of 
the board is too expensive as we see it.  I wanted to check with all of you 
and see if you had any suggestions as to how to manage data structures for 
empty regions of the board efficiently.  Ideally, we would like to update 
this information on a per-move basis rather than completely reevaluate the 
board at every move.  However, we are open to any suggestions. 

Thanks for all your help, 
Bryan McQuade