Re: computer-go: Languages for programming go are?

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

>  I would be interested into knowing how you can maintain the liberty count
>  for "free" (by "free" I assume you mean in constant time). It seems to me
>  it's difficult to do it better than in linear time (according to the number
>  of liberties of the strings you connect). Is this an amortized cost?
> 


Hi Antoine,

You probably   didn't understand my  description.  Maintaining liberty
counts is not  free, UNMAKING  moves is.  However,   as it turns  out,
maintaining liberty counts is very cheap and  I think that is true for
any program  that maintains them incrementally.  I  could test this by
trying to turn off the logic that does this.

As far as how fast is incredibly  fast, I would have  to measure it for
you.  But my program is not doing any real work  during the search, so
all it's doing is making moves and keeping up  with liberty counts and
stone  counts.   It does all evaluation work before the search begins.

Don




   From: "Antoine de Maricourt" <antoine.demaricourt@xxxxxxxxxxxxxxxxx>

   ----- Original Message -----
   From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
   To: <computer-go@xxxxxxxxxxxxxxxxx>
   Sent: Saturday, December 30, 2000 9:44 PM
   Subject: Re: computer-go: Languages for programming go are?


   >
   > I have limited understanding of go programming techniques but for what
   > it is worth, here is how I represent things:
   >
   > The board is a one dimensional array, with a border around it for easy
   > edge detection.  I store a "group number" on each intersection as well
   > as a white bit and a black bit.  The group number is really a "string"
   > number.  Separately, I have a structure that tells me things about any
   > given string (indexed by this group number) which I keep incrementally
   > updated.  This  is very simple and  my program is  primitive, so right
   > now all I keep is a liberty  count, a count of stones in the group and
   > the location of a reference  stone (it doesn't matter which stone) and
   > a hash key or signature number for the group.
   >
   > It's  not  very sophisticated,  but  it's  trivial  to implement,  and
   > incredibly fast.   The move maker is  very fast since I  don't need to
   > maintain hooks and complicated  logic for unmaking moves (which itself
   > is a FREE operation in my program.)  Free is a relative term since one
   > can argue that I pay a price for this simplicity.  I have noticed over
   > the years, with modern processors that state copy is incredibly cheap,
   > even  a substantial  amount  of  state, over  anything  that has  much
   > conditional logic  in it.  Unmake  routines have a lot  of conditional
   > logic, as does makes (which is simpler for me.)
   >
   > Don


   Hi Don,

   I would be interested into knowing how you can maintain the liberty count
   for "free" (by "free" I assume you mean in constant time). It seems to me
   it's difficult to do it better than in linear time (according to the number
   of liberties of the strings you connect). Is this an amortized cost?

   Also what do you mean by "incredibly fast"?

   Antoine.