Re: computer-go: unmake move?

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

I use this idea in my chess program and it is very effective.
But the chess program board state is only 220 bytes.  Copying is
very fast, and there is no need to unmake moves.  Many Faces
has much more state per position, so copying to make moves
is not practical.  And I hadn't thought of this when I first
wrote Many Faces :)  If you can keep the move state small,
avoiding undo by copying positions is a very good idea.

David


At 02:05 PM 6/7/00 -0400, Don Dailey wrote:
>
>> 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 );
>
>}  
>
>