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