RE: computer-go: Live or Die

[Jean-Pierre Vesinet <jvt@xxxxxxxxxx>]

> Read out the situation again, very carefully :)
> 
The ko was just me hallucinating :). The diagram is a perfect example of
_just barely_ safe stones and territory. Sorry I mentioned it. 

> You can be more formal if you like. Let s be the set of points not
> occupied
> by stones of 'color', i.e. empty points plus opponent's stones. Then
> regions are the connected components of s. Note that black regions and
> white regions are completely different in this construction.
> 
Yes, that's about what I had in mind. See below.

> That's the whole point of publishing stuff, to let others build on it. It
> would be nice if you share your insights with the rest of us.
> 
> Where exactly do you think are loopholes?
> 
The definitions and algorithms in your paper didn't look quite satisfactory
to me, either from the strictly mathematical point of view or from a
programmer's point of view. One must interpret some of them (regions for
example) in order to make them less equivocal and OTOH not use them too
literally to program them. My comments may sound as nit-picking, since I
fully agree with everything you say in your paper, but my concern was about
the way it is formulated. I expect anyone reading about Benson's algorithm
for the first time in your paper would have the same difficulties.

Let me explain: about Benson's algorithm, which is really quite simple, it
took me some time to understand how it could actually be used to check the
safety of stones AND territory. Since I have no idea how Mr. Benson
formulated it himself, I will try to express my understanding of it in the
simplest form. I'd also like too know if it helps Mr Yu Jiang, who asked the
question about eyes in the first place.

First some remarks:
- A block should be defined as a non-empty connected set of points of the
same color (either black or white) (OK, this _is_ nit-picking).
- The definition of regions is less confusing if black regions and white
regions are not allowed to overlap. Also a simple "flood fill" definition is
easier to understand.
- A recursive definition of Benson-alive blocks is much less confusing to me
(see (iii) below).
- I will be using your conventions (a "block" is also known as a "string" or
"chain" or "unit" in the literature), and your definitions of a "point
adjacent to a block" and a "region's interior".
- I will use "c" for either of the two colors (black and white), "-c" for
the opposite color. Each point is, of course, either colored black, white or
empty.

Now the definitions:
- A c colored region is a maximum connected set of -c and empty points.
- A c colored block B is Benson-alive iff it is adjacent to at least two c
colored regions R (1,2) (let's call them Benson-safe regions) that verify
(i), (ii) and (iii):
(i). all points in R's interior are -c colored,
(ii). B is adjacent to all empty points in R,
(iii). all blocks adjacent to R are Benson-alive.

That's all. Please let me know if something is missing. I can only hope this
is understandable, since English is not my first language (nor my second
language).

	I make no claim that my static life criteria are complete. Go is
much too
	complicated for that :) But they should be correct.

Agreed. What I also wanted to know is how to recognize most instances of
unconditionally safe territory (regions in which neither player ever needs
to play). Benson-safe regions are not alone; another class of regions (at
least) have the same property. Let's call this class of regions Benson2 (I
don't know if they have another name in the literature). I would define such
a region as a c colored region that is:
(a) surrounded by Benson-alive blocks (same test as (iii) previously),
(b) too small to live independently (the region's interior is either empty
or restricted to one point or two connected points).

I think the condition (b) could be improved a bit by taking into account the
region's potential eye space instead of the interior. I will need to reread
your definition of PES...

> >	Are Thomas Wolf's papers available on the internet or in books ?
> >
> http://www.maths.qmw.ac.uk/~tw/public2.html#3
> 
	Thanks !

	[Jean-Pierre Vesinet]