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

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



Antoine de Maricourt <antoine.demaricourt@xxxxxxxxxxxxxxxxx> wrote:

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

Here is one approach I have been playing with. It does not give you the
liberty count, but it gives you the liberties directly, in constant time. If
a string is encoded into a board-size bitmap, then all you need to do is to
"shake" it once to each direction (constant time), and AND it with the
bitmap that represents the empty points on the board. Voila, you have a
bitmap that shows the liberties of a string, in constant time.

Happy new year!

	Heikki



-- 
Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
               "In Murphy we Turst"