Re: computer-go: unmake move?

["Mark Boon" <tesuji@xxxxxxxxx>]

Copying instead of unmaking is certainly an interesting idea worth
considering. But it costs more memory. Still I would be surprised if memory
bandwidth would restrict it to only 100.000 moves per second, just making
and unmaking moves should be in the millions per second nowadays.

If you're just talking stone position information and chain-numbers there's
a very simple solution that hardly takes memory at all. (If you keep more
information, the copy method becomes even more expensive.) Keep four stacks
with the four chain-numbers around the move being played. The chain where
the move is played gets its position as its chain-number, ensuring it's
unique. Any chain it connects to gets propagated the same number. When doing
undo, any of the four chains that have a different chain-number than the one
on the stack gets the old number propagated again. Voila.

The expensive bit is recursively propagating the unique number through the
stones it connects to. And reversing it on undo. If the chains are large
it's *very* expensive but fortunately connecting large chains is relatively
rare and on average this method doesn't take much time. (Except in ladders,
but I have another solution for that.)

Mark

----- Original Message -----
From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Wednesday, June 07, 2000 8:05 PM
Subject: Re: computer-go: unmake move?


>
> > Hello Bryan.
> >
> > My data structures are probably nothing like yours, but I only change
what's
> > equivalent to your group number when merging groups.  I also maintain
undo
> > information (as you're probably doing.)
> >
> > I have the impression in my own code that checking for superko is more
> > costly than undoing moves.
> >
> > Regards,
> >
> > Peter Smith.
>
>
> Peter,
>
> Have you ever considered not unmaking moves at all?
>
> In   my chess and go   program, I use a  c  structure to represent one
> position state.  I pass a  whole position down the  tree when I make a
> move.  My structure contains the position, a  hash key, a stone count,
> liberty  count, head   stone  and so on  for   each group  as well  as
> incremetal scores and any other relevant information I need to keep up
> with.
>
> Now to address your  problem, unmaking is completely non-existant  and
> move  MAKING becomes greately  simplified  and faster.   Suddenly your
> code simplifies and you are not going out of  your way to maintain all
> the un-move state information.  And there can  be a significant amount
> of this.
>
> Note that modern processors are extremely fast at copying data that is
> layed out consecutively in  memory, believe  me, you  can have  a very
> fast   program that uses  this  technique.    I have  found that  this
> arrangement cleans up the code a lot because it  can get sloppy having
> global   state all  over the   place.    It also  simplifies  parallel
> programming if you decide to go for that later.
>
> A lot of people, when first hearing of this thinks it must be terribly
> expensive, but it turns out that is  not the case.  They don't realize
> that they are already passing a lot of state anyway, but doing it kind
> of piecemeal, not processor friendly.   I first started doing this  to
> facilitate parallel program, I would not have considered it otherwise,
> but I was pleaantly shocked and rewarded to find I could still write a
> blazingly fast chess program.
>
> Unfortunately, every  program is different, and  if you are  keeping a
> huge amount of  auxillary  information that must be  constatly updated
> and downdated, then there is no guarantee this will work well for you.
> But I am just throwing this out as a suggestion for you and urging you
> not to be too predjudiced against the  idea.  It would certainly solve
> your problem  but   of  course I   can   imagine it  would  require  a
> substantial  rewriting of your program.  But   you would be removing a
> lot more code that you would be adding!
>
> Don
>
>
> P.S.  Off the top of my head, here is a kind of psudo code example of
>       how things might look.
>
>
> /*  nega-max search */
> /*  --------------- */
>
> int  search( position *state,  int depth,  int alpha, int beta )
> {
>    POSITION  new_state;   /* allocate state */
>
>
>    foreach move in (0 .. number_of_moves)
>    {
>      make_move( state, &new_state, move );
>      score = -search( &new_state, depth-1, -alpha, -beta );
>
>      /* No need to unmake!!! */
>
>      if (score > best_found_so_far)
>      {
> ...
>
>      }
>
>    }
>
>    return( best_found_so_far );
>
> }
>