Re: computer-go: unmake move?

[<Michael.Collins@xxxxxxx>]

     I Use something very similar,
     Joining two groups isn't too difficult ( depending what information
you hold against each group, liberty count, number of stones etc ).
     To unjoin if you add into the group structure values for what groups
were joined together initially ( a maximum of four other groups in any one
move )  ,a move number and a flag to state whether a group is valid/invalid
you just step back and make the older, invalid groups valid and invalidate
the joined group.

Regards,
Mike...


|--------+----------------------------------->
|        |          David Fotland            |
|        |          <fotland@xxxxxxxxxxxxxxxxx>|
|        |          Sent by:                 |
|        |          owner-computer-go@lists.u|
|        |          oregon.edu               |
|        |                                   |
|        |                                   |
|        |          08-06-00 04:35           |
|        |          Please respond to        |
|        |          computer-go              |
|        |                                   |
|--------+----------------------------------->
  >---------------------------------------------------------------------------------------------------------------------------------|
  |                                                                                                                                 |
  |       To:     computer-go@xxxxxxxxxxxxxxxxx, computer-go@xxxxxxxxxxxxxxxxx                                                      |
  |       cc:                                                                                                                       |
  |       Subject:     Re: computer-go: unmake move?                                                                                |
  >---------------------------------------------------------------------------------------------------------------------------------|





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
>
>