RE: computer-go: Live or Die

[Martin Mueller <mueller@xxxxxxxxx>]

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

I think you must allow them to overlap. Otherwise you get into trouble.
What is a region, and what is not? E.g. make a black wall horizontally
across the whole board, and a white wall vertically, with a cross-cut in
the center. What would be your regions? I have two black regions and two
white ones, which overlap each other on a quarter of the board.

A more realistic example is a dead white group with one eye. It is a white
1-point region
within the black region that contains the dead group. If you want to
eliminate these you must know a lot about Life and Death....


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

I think your definitions are okay, but I did not check closely. However,
the recursion does not give an efficient algorithm. These definitions are
similar to Benson's first paper. In his second paper, he gives a much more
efficient algorithm, which works by starting with all blocks and regions
and then successively deleting those that are not safe. I think it is
really best if you read his paper, since he explains it better and more
mathematically precise than I can do here. The good version of his paper is
reprinted in the Levy book, which should be easy to find.

@ARTICLE{Benson1976,
 AUTHOR       = "Benson, D.B.",
 TITLE        = "Life in the Game of {Go}",
 JOURNAL      = "Information Sciences",
 VOLUME       = "10",
 NUMBER       = "",
 PAGES        = "17--29",
 YEAR         = "1976",
 NOTE         = "Reprinted in Computer Games, Levy, D.N.L. (Editor), Vol.
II, pp. 203-213,
Springer Verlag, New York 1988"}

A less formal but maybe more readable summary of his method is in my PhD
thesis, p.61-62. Note that my comments about a bug in his paper apply only
to his old version. At the time I did not realize that there were two
different versions of his paper.

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

Benson's method is about safety in the case where the defender never plays,
just keeps passing against any attack. It is complete for this case, and
the proof is in the paper.

The other question, "regions in which neither player ever needs to play",
is much much much much harder. It involves knowing everything about life
and death, seki, ishinoshita, double ko, semeai etc.

Hope this helps

	Martin