[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: computer-go: unmake move?



>  Can you tell me the size of "POSITION" ?

Yes,  it's   4872 bytes   on   a  19x19  board.    I could  shrink  it
significantly  by making   type  STONE and  COUNTER 16   bits (see the
structure below.)  But   I  have tried  this  and  there   is a  small
reduction in  the search  speed.   I'm guessing  it's  because 16  bit
variables are less processor friendly that 32 bit variables.

Here is  what my actual  state looks like so you  can see what kind of
data I move around:


typedef struct ptag
{
  int          ctm;                 /* number of ply's (color to move is bit 0) */
  U64          signature;           /* hash key of position             */ 
  STONE        bd[BOARD_SIZE];	    /* the actual board                 */  
  COUNTER      in_hand[2];          /* enemy stones captured            */
  COUNTER      next_unit;           /* always incrmented unit number    */
  COUNTER      move;                /* move that created this state     */
  struct ptag  *his;                /* pointer to last position         */
  unit_type    unit[MAX_UNITS];     /* list of all units                */
  COUNTER      adjust;              /* evaluation term                  */

} position;

The units of unit_type look like this:

typedef struct
{
  COUNTER  stone_count;     /* how many stones in this unit?          */ 
  COUNTER  lib_count;       /* how many liberties for this unit?      */
  STONE    headstone;       /* a representative stone from the unit   */
} unit_type;


The contents of the board (bd[]) are coded with a color bit and a unit
number which indexes  a unit_type record.   BOARD_SIZE is N+2 or 21 in
the case of the 19x19 game for edge detection.

I'm guessing my implementation is naive compared  to any good program,
and the only thing I really keep track of is information about "units"
which in my terminolgy is a whole set of  connected stones of the same
color.    I always know how  many  stones  in  any unit   and how many
liberties, which of course is easy to maintain incrementally.

I have never seen  the code for  any other go program   or even a  low
level  description of how  the  board and state   is represented, so I
don't really have a clue  about how things SHOULD be  done.  But I can
imagine that a good program might  carry a whole  lot more data around
that mine  does.  In that case,  its possible that  this method is not
very close to optimal.  But I would argue that  if you carry more data
around, not only do you probably spend more  time keeping it all up to
date, but you probably have to save a lot  of state ANYWAY in order to
gracefully un-make a move.  So it isn't as if going all the trouble of
undoing moves stops  you from pushing  state around.  So I just choose
to push the whole thing in one simple and fast operation!

Based on my experience with chess, which admittedly requires much less
state, I would guess  that this is  probably at least reasonably close
to optimal.  It's certainly FAR simpler  and makes me more inclined to
experiment, knowing I  didn't have to  always provide for  undoing any
new gizmo I add to the search.

You brought  up the issue  of  memory bandwidth.  There is  always the
possiblity  that  this technique could  blow  out the  cache.  I don't
really know the answer, most of my experience  is with Chess programs,
I  am a beginner at go  as a player AND  a programmer and I have never
written a go program that  un-makes moves so I  don't have anything to
compare  against.  But I have  written MANY chess  programs using both
the position passing and the unmaker.  I just  know in chess it's hard
to demonstrate that  one technique is faster than  the other, so  I go
with the one  that leads to simpler code,   that has less bugs  and is
tailor made for parallel programming.

This probably goes without saying, but the more work your program does
making and unmaking moves, the more  attractive this idea becomes.  If
you push a huge amount of state around, maybe it's not so clear.

What I should probably do is  to profile my  code and measure the time
spent making a move  and how much of  this  time is spent  copying the
state.  Whether this turns out good for me or not  though, it would be
no guarantee that others would get the same  results.  If I do this, I
will post the results, ok?

By the way,  for what it's  worth, my program  looks at slightly under
300,000  nodes  per second on a   600 MHZ  Athlon.  This  probably has
little meaning without knowing exactly  how a given program works, but
at least you probably have a sense  of what I do to  keep the state up
to date  when a move is made.   I don't know  if this is  fast or slow
given what the program does.  An  unmake routine might slow this down,
or speed it up, but my guess is that it wouldn't make a big difference
either way.

I have this idea that many programmers  may be prejudiced against this
idea, I certainly was when I first  tried it in  my chess program.  It
just seemed silly to  me to push whole positions  around in the search
tree when  you can just update  in place.  But  then I realized  I was
keeping some data in a stack anyway to help me unmake a move, and that
the un-make routine  had plenty of  logic of its own,  a lot more than
you  would  imagine for  simply moving  a   piece from  one  square to
another!  So why not just do the ultra simple and high speed copy?  As
I said, modern  processors do this  well.  The real  bottlneck is code
with decision making logic in it, like un-make!

Well, all I  can say is don't  be afraid to give this  a try.  I don't
really know if it would pay off or not in a typical go program, I just
know it's a whole lot simpler, the code is a lot cleaner, and I have a
strong sense that it's not a lot slower,  and maybe it's not slower at
all.  If unmaking a move is really  complicated, it might very well be
faster.

Don



   From: Nobuhiro Yoshimura <yosimura@xxxxxxxxxxxxxxxxx>
   Date: Thu, 08 Jun 2000 10:08:49 +0900
   MIME-Version: 1.0
   X-Mailer: AL-Mail32 Version 1.01
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain; charset=us-ascii
   Content-Length: 1053

   Don Dailey wrote:

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

   Can you aply this rule to PCs ?    I thought that memory bandwidth 
   is very narrow for PC.


   Can you tell me the size of "POSITION" ?

   >
   >
   >/*  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 );
   >
   >}  
   >


   Nobuhiro Yoshimura 

   Konami Computer Entertainment Tokyo     The opinions expressed 
   Office: yosimura@xxxxxxxxxxxxxxxxx           here are mine and not 
     Home: yoshimura@xxxxxxxxxxxxxxxxx               necessarily those of Konami.