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

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



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