Re: computer-go: Group understanding..

[David Seaman <dseaman@xxxxxxxxxxx>]

Hi, Guillem.  It's my first time writing here, too!

>     Hi!.. It's the first time I write here. I haven't written a go program
> yet, but I hope to do it soon. Thinking about how to do it, a few questions
> arose. Maybe you find them quite simple, I beg for your pardon in advance.
> The first one is about groups. What do you consider a group ?.. I mean, if I
> have a position like this one:

> #OO####
> O#O####
> OO#####
> ########

> Being it in the top left corner. This stones are alive, but I don't know if
> a program should consider them one group or two groups that are alive. I
> think I can't consider it a group because the stones are not connected, but
> then It's quite more difficult to consider it being two living groups. And
> then, If it's two groups, how do I know if they're alive?, because they
> share liberties that happen to be alive ?.. I don't get it. It seems
> difficult to code.

You might want to use two different data structures; one for each.  Gnugo
calls a connected group a "worm", and both groups together would be a
"dragon", defined as stones that live or die together.  Gnugo is a Free
Software program you can download, source code included, so you might
want to look at it to get ideas.

I'm not sure of the best way to determine what's alive; one way that would
work most of the time would be to fill in all the liberties with enemy
stones that you legally could and see if you could kill it.  A faster
way might be to match against a bunch of patterns of known-to-be-alive
configurations.

I'm working on a Go program of my own, but I'm not serious about it yet,
so I only work on it when I feel like it.  Mine keeps track of "worms",
so far, and also a lower-level data structure for "shapes" of worms.
That way, each worm is a shape, and when playing a stone, it can look
up in the pre-computed shape table to instantly find the worm's new
shape number, number of liberties, and a whole lot of other pre-computed
information.  Eventually, I want it to keep known combinations of
shapes in some kind of hash table of known-to-be-alive dragons.  You
can steal these ideas if you want, because my program is going nowhere
fast.

David Seaman

> Thanks, Guillem.