Re: computer-go: Group understanding..

[Jeffrey Rainy <JRainy@xxxxxxxxxxxx>]

Hi there,

I'm a newcomer too.  This problem I solved in a different way :

First thing, I number every empty region and every string with a different number. In your case, this would give :
122333
452333
443333
333333

For evey empty area, I mark if they can be eyes. In this case, 1 and 5 are, and 3 isn't because it's too big.

Then, I compute a connectivity graph, showing what's connected to what. In this case, we have the folllowing :
1-2
1-4
5-2
5-4
4-3
2-3

Then, I mark as alive every string that touches at least two empty area that can be eyes and that only touch alive strings of the same 
color.
The actual algorithm to do this is to mark every string as alive, and disprove it for each until you can't, at which point you get the alive 
ones.

Where things get more difficult is when the string are not yet connected/closed :

#########
#XXXXXXX#
#OOOOOOO#
#########
#########
#########

For this I plan to used either some pattern recognition, or move planning to mark as alive.  But I'm not quite there yet. ;-)

Jeff.


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