Re: computer-go: unmake move?

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

One easy way is to have each group maintain a list of intersections
that are contained in the group.  When a move merges two groups,
allocate a new group number for the merged group.  The old group
numbers are no longer active, but they maintain their group lists.
When you want to unmake a move, just restore the old group numbers
to active status.  I keep a list for each move made of the group numbers 
that were made inactive by that move, so undo is easy.  Many Faces'
tactical analyzer uses an algorithm similar to this one.

David

At 10:42 AM 6/7/00 -0400, Bryan McQuade wrote:
>Hi everyone.  This is my first post, and I have a question about
>implementation of a method.  I am using minimax alpha-beta and am trying
>to develop a fast unmake move method.  I am stuck, however, because my Go
>program uses data structures GROUP and INTERSECTION where one of the
>elements of INTERSECTION is the group number of that piece.  In trying new
>moves, groups are restructured, requiring me to re-assign group numbers
>all the time.  To make matters worse, during the unmake move for minimax,
>I will have to re-assign group numbers when removing a piece from the
>board causes group structures to change.  This will have a drastic effect
>on the speed of the minimax search, and I'd like to avoid it if
>possible.  Has anyone run into this, and if so, do you have suggestions?
>
>Thanks very much,
>Bryan McQuade
>
>