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

Re: [computer-go] Groups, liberties, and such

On Fri, Oct 14, 2005 at 04:09:25PM -0400, Jason House wrote:
> 1. When connecting two stone chains is there any way to calculate the 
> new chain's liberties without iterating over all the stones?  While not 
> simple, tracking a chain's identifier can be done in O(1) and I'm 
> looking for a comparably efficient solution if it exists.

Well, if you keep your liberties as a board-sized array of bits, you can
combine the liberties of the two connected groups, and of the connecting
stone, in a simple logical OR. That would be O(1), but probably slower
than many other approaches.

- Heikki

Heikki Levanto   "In Murphy We Turst"     heikki (at) lsd (dot) dk

computer-go mailing list