[computer-go] incremental liberty counts

[Łukasz Lew]

On 9/1/06, Antoine de Maricourt <antoine.de-maricourt at m4x.org> wrote:
> Hi,
>
> > Is it written in C/C++ without asm?
> It includes parts written directly in ASM.
> >> Regarding implementation:
> >> - I do not update liberty count
> >> - in order to know if a move is a capture or not, I use the pseudo
> >> liberty count: easy to build / drops to zero means dead stones
> >> - example of extra information I update are: B/W stone count on
> >> board, whole B/W/empty bitmap representation, small surrounding
> >> bitmap (8-bit, depth 2) to represent 8-neighbourhood status around
> >> every point.
> > How do You share the liberties of a whole group?
> Not sure I understand what you mean by "share liberties". I forgot to
> mention
> that I also maintain a list (linked list) of all point in a group. When
> I want
> to know the liberty count of a group, I follow the list of points in the
> group
> and build the liberty count/list on the fly.

It looks fast, but I cannot imagine how do You manage to join the
lists efficiently.
The problem is:
If You just crosscut your lists, then the play in contact with two
friendly stones, both
being a part of the same string will produce two lists (after two
crosscuts) instead of one.

Best Regards,
Łukasz Lew

>
> So far, I rarely need to get  the liberty count. Most of the time the
> question
> looks like "does the group have more or less than N libs", where N is
> usually
> small.
> >> If I had to reimplement a board for fast play, without undo, and
> >> without extra information I would very seriously consider a bitmap
> >> representation (especially for a 9x9 specialized version)
> > What would You gain if You use pseudo-liberites anyway?
> I've no specific idea, but since Intel gave back a decent latency to SIMD
> instructions in its latest brand new processor, this surely open perpectives
> for bitmap operations.
>
> Antoine.
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>