Re: computer-go: unmake move?

[Tanguy Urvoy <turvoy@xxxxxxxx>]

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


Hello,
On gnugo we use an incremental scheme to maintain groups (we call them
strings)
and liberties. When doing a move register all the modifications
in a stack of couples (address,old value) with a special couple (NULL,0)
as move marker.
To unplay a move we simply scan back the stack until we find the move
marker.
have a look at
http://www.irisa.fr/prive/Tanguy.Urvoy/gnugo/gnugo.html#Incremental%20Board



-- 
----------------------------------------------------
Tanguy Urvoy                   Doctorant IRISA             
mailto:Tanguy.Urvoy@xxxxxxxxxxxxxxxxx   Tel: 02.99.84.25.15
----------------------------------------------------