Re: computer-go: unmake move?

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

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

}