Benson's Definition of Unconditional Life / Version 20100208

Sub-page of BensonsDefinitionOfUnconditionalLife

This page contains the version of the Benson's Definition of Unconditional Life page on 2010 February 8, before wiki master editing took place.

[edit]

Overview

Benson's algorithm is a rigorous and static (i.e. no search is needed) method for recognizing stones that are uncapturable even if the attacker is allowed to play an infinite number of times in a row (i.e. the defender always passes). This is called unconditional life in Benson's paper ^[1], a confusing name for something that has no equivalent in traditional Go terminology.

Typically the groups for which it is possible to prove unconditionally life, don't have a very big eyespace - more accurately, the eyespace must not have empty intersections that are not liberties of the surrounding blocks.

Benson's Algorithm doesn't need to consider things like ko or seki, good moves or bad moves, opponent answers, because the matter is only unconditionally alive or not.

The algorithm is only used by a few specific life-and-death programs and modules.

[edit]

The Algorithm

Perhaps you could describe the algorithm? I have a rough mental idea of how it would work, but I'm not sure... -- Karl Knechtel

jvt: I don't want to paraphrase, so here is a completely rewritten and much simpler version. (See also the revised versions 1 and 2.)

"c" stands for black or white, "-c" for the opposite color. Each point of the board is, of course, either black, white or empty.

A c chain is a non-empty maximum connected set of c points.

A c region is a non-empty maximum connected set of -c and empty points.

A c chain is unconditionally alive if and only if it belongs to a set of c chains S such that every chain B in S is adjacent to at least two c regions R that satisfy:

(P1) all empty points in R are adjacent to B, and
(P2) all c chains adjacent to R belong to S.

This bars circularity implicitly ^[2].

Note that for every board, there exists one such set S that is maximal in size. A practical way to calculate S is to use fixpoint iteration downwards, i.e. first set S to contain all c chains, and then remove chains that do not fulfill the property above one by one.

Note: proof depends on suicide being forbidden by the rules. (see Example 4)

In the board "Example 1" there are 6 B-regions (a-f). Downwards iteration starts by including all the five chains (A6, A3, C2, D1, E6). The chain E6 is adjacent to only 2 B-regions (c and f) but f does not fulfill the property P1 so E6 must be removed from the set. The same holds for the chain C2. This ends the first iteration.

At the beginning of the second iteration S contains the chains A6, A3 and D1. Now regions c and d are no longer adjacent to chains in S only (because chains C2 and E6 are removed), so chain D1 is removed from the set S; it is connected to only one region (e) fulfilling property P2.

On the third iteration S={A6,A3} no more chains can be removed. Fixpoint has been reached, and the set of unconditionally alive strings is A6 and A3.

[edit]

Sketch of Proof

(1) prevents the attacker from filling all liberties of an unconditionally alive chain in 2 adjacent regions, because of the no-suicide rule. (2) prevents the attacker from making liberties by capturing another chain adjacent to the same region. And two liberties ensure the chain will never be in atari.

[edit]

Disclaimer

I don't claim these definitions are the same as in the original article ^[1] by David Benson. Besides I don't define small c-enclosed regions, healthy regions, nor vital regions.

The requirement about a c region's interior being filled with -c stones has been intentionally removed because of my different definition of regions.

[edit]

Examples

[edit]

Example 1

the single black stone is necessary

the single white stone is only next to one eyespace-region and even that one eyespace-region doesn't fulfill the condition

[edit]

Example 2: a group that is "alive" but not "unconditionally Alive"

The black group is not "unconditionally alive", because: if white has as much moves in a row as he wants, he can capture the stones.

The order of filling liberties is important, he starts with outside liberties, then the inside liberties:

The reason why this group (the group c1) isn't unconditionally alive (according to Bensons Algorithm) is that the two empty points marked with squares aren't liberties of c1 (all empty points in the adjacent eyespace(s) have to be liberties of the group of stones).

For the big chain it is no problem that the point marked with a circle is not a liberty of the big chain, because the big chain already has two (eyespace-)regions (a2 and b1) that fulfill the condition.

Remark on search: This example also shows how much and deep search would sometimes be needed to prove a group of stones is unconditionally alive (or find out it can't be proven yet). The search must consider filling liberties in the correct order (outside first, then inside), and another order could show the group is capturable, even if one certain order does say it isn't.

Note: The number of search could be reduced, by filling all regions with stones all over except at one point. Then trying to fill 1 region completly to see if some groups are captured. If not, then change 1 of the free points in 1 of the filled regions. Thereby it is not nessecary to consider move order. So there are 2 possible outcome of the previous example.

[edit]

Example 3: Big Eye Not Unconditionally Alive

The reason why this group is not unconditionally alive is that circle is an empty intersection in the (eyespace-) region but not a liberty of the black chain.

But instead, if A1 were a white stone, wouldn't the black chain be unconditionally alive ? This is weird because it is still not "safe" under Benson's algorithm... Or am I wrong ?

[edit]

Example 4: Bensons Algorithm on an unusual goban

[edit]

Bensons Algorithm on an unusual goban (1)

(middle row has no liberties to the bottom in the following diagram)

[edit]

Bensons Algorithm on an unusual goban (2)

In the following configuration: if the two single white stones are connected (through are wormhole in the 3rd dimension for example, so they form one group, but don't have additional liberties than those visible on the board), all white stones are unconditionally alive!

[edit]

Bensons Algorithm on an unusual goban (3)

[edit]

Example 5: ...

AshleyF: A clarifying example is useful for understanding why the algorithm depends on suicide being disallowed:

This is not unconditionally alive because the marked point is not immediately adjacent to black+square , and so that stone has only one safe eye.

This, however, is found to be unconditionally alive by Benson's Algorithm. The white+circle stone and the empty point to its left are together considered one region, and the empty point in this region is adjacent to both black groups.

Of course, though, if suicide is legal then White could clear the stone and be back to the previous diagram.

[edit]

Example 6: Can Benson's algorithm be adapted for rulesets that allow suicide?

Considering example 5, the condition in the algorithm has to be changed to: "all points (instead of only the empty points!) in a (eyespace-)region have to be adjacent to the group".

[edit]

Example:

In the following diagram: b1 is not a liberty of b3, so none of the black groups is safe.

(original explanation by Robert Pauli:)
term100?: Can Benson's algorithm be adapted for rulesets that allow suicide?

Yes, just restrict healthy regions additionally to be without any intersection not adjacent to the block using them as such.

Didn't prove it, but I strongly feel that this would make Benson's "safe" equivalent to his "unconditional alife" under with-suicide.

[edit]

References

[1] Benson, D.B., Life in the Game of Go. Information Sciences, Vol.10, pp.17-29, 1976. Reprinted (with corrections) in

  Computer Games II
  David N. L. Levy (ed.)
  Springer-Verlag, 1987
  ISBN 0-387-96609-9

[ext] Original Paper

[ext] David Dyer's eye shape library

[edit]

Discussion

[edit]

circularity-problem

[2] Jan: Doesn't this introduce a circularity? Take this example:

There is only one chain, and three regions - one large one and two of one point each. However when I apply the definition, I get the following:

The large region doesn't count (not all empty points are adjacent to the chain) so we turn our attention to the two small regions. The first requirement checks out OK, but for the other one, we need to know whether our chain is unconditionally alive. But that was the question we were asking in the first place.

I think the second requirement needs to be reworded like this: all other chains adjacent to R are unconditionally alive Did I miss anything here?

jvt: You are right. But there is still some indirect circularity remaining because you can have c1 - R1 - c2 - R2 - c1. (c = chain, R = region).

Benson uses "transitive closure" to convey the meaning of recursivity without circularity. I am not sure how to express this more clearly. Is "barring circularity" clear enough?

Reading again Benson's paper, I see his definition applies to a set of chains, not a single chain, to avoid the circularity problem. My definition needs re-wording:

[edit]

Revised version 1

A c chain is unconditionally alive if and only if it is a member of a set S of c chains so that each element B of S is adjacent to at least two c regions R that satisfy:

all empty points in R are adjacent to B,
all c chains adjacent to R are in S.

[edit]

Remark

Not all empty points in the c region have to be adjacent to all enclosing c chains. For example:

The empty point marked with a red square is adjacent to only one chain. This does not prevent the marked chain from getting its two eyes elsewhere.

ray?:In fact, this example does not bother me. Stated in Benson's article, the three blocks need 2 or above vital regions. For the the lower and left two blocks, two size-one regions are vital to both. If the region is not healthy to a specific block, then we just ignore it. Although the discussion here focus on the algorithm, but I think it is appropriate to note that there's something difference between the algorithm here and the original Benson's article.

All black chains are unconditionally alive

Here is a more complex example.

blubb: I didn't know Benson's article yet, but your revised "unconditional life" criteria is almost exactly what I found in 1993 when I was thinking about the same question. (Probably there are several hundreds of us having "discovered" these laws of unconditional life already :) .) Unfortunately, the definition of "c region" given above is way different from what it has established to be used for in the discussion about unified [ext] rulesets. A region may be one-, two-, or three-coloured (or, if containing no point, not coloured at all), and a one-coloured region often is called a "chain" (or "block" in Bensons's terminology). Calling a region which consists of white and empty points only, a "black region", seems misleading.

Though, I do also think that it is not necessary to define Benson's "small c-enclosed", "healthy" nor "vital" regions.

Therefore, and for some other reason (see below), I'd suggest the following wording:

[edit]

Revised version 2

c region: is a non-empty maximum connected set of c points.

non-c region: is a non-empty maximum connected set of -c and empty points.

A set G of c regions is pass-alive if and only if each element X of G is adjacent to at least two distinctive non-c regions Yi that satisfy:

all empty points in Yi are adjacent to X,
all regions adjacent to Yi are in G.

In order to implicate that the (at least) two decisive regions (Y1, Y2, ...) (i. e. the ones which make X pass-alive) must not be adjacent to anything but c regions, I chose all adjacent regions to have to be in G.

This wouldn't really be necessary if an adjacent pair of one empty and one -c point inside a non-c region was said to be "connected", but the general term "connected" in common go players` language is usually understood in a very different way.

Here is an illustration why this approach could be helpful:

Consider (mistakenly) columns b,c,d, including a5, to be Y1 and f,g,h, including i5, to be Y2.

As another workaround, we could deal with several kinds of "being connected":

Any pair of adjacent points is

I-connected: if and only if the color values of both points are element of I,

where I is any subset of {black, white, empty}.

I can be

 1. {}             (-> not connecting function),
 2. {b}            (-> common black string forming connection),
 3. {w}            (-> common white string forming connection),
 4. {e}            (-> common territory forming connection),
 5. {b, w}         (-> "non-empty" connection),
 6. {w, e}         (-> "non-black" connection),
 7. {e, b}         (-> "non-white" connection),or
 8. {b, w, e}      (-> plain "being adjacent" connection).

We probably don't need these definitions for the simplified Benson's algorithm, I just want to point out the difficulty with the term "connected". blubb

jvt:
About replacing "all c regions adjacent to Y are in G" with "all regions adjacent to Y are in G". Since 'region' is not defined it does not make this definition clearer. I would keep the 'c' because the same meaning is needed as in the beginning of the sentence "A set G of c regions is..." .
If you agree about the 'c' I would like to keep only your version and remove the other two versions, it would make this page less confusing.
About your example: Y1 and Y2 are clearly not maximum sets of non-black points. So I fail to see how they are relevant.

blubb: The three single-color "solidly connecting" functions (items 2. to 4. in the list above, see also here) are well-known and don't have to be explained. Though, IMHO, items 6. and 7., which are the ones we need for the "maximum connected" terminus when continuing to use the "all c-regions" phrase, ought to be specified if we want people to understand what we're talking about. I definitely prefer semantical consistency to ambiguousity. For the same reason, I'd even suggest to replace "unconditionally alive" with "pass-alive".

jvt: Yes, but this definitions are still informal. If "maximum connected" needs to be defined, a flood-fill algorithm could be described. Or, for the mathematically minded, "maximum connected" sets are actually the equivalence classes of the transitive closure of one of the "adjacent or same point in the same set of colors" relations.

blubb: Agreed. Well, considering an average reader, my point is simple: every new definition, as well as every alienation of a common Go term, makes our wording harder to grasp, and the way to go longer. Admittedly, this is not a logical but a pedagogical argument. But I want to keep this stuff comprehensible by people who would stop reading Benson`s paper at page two. Supposedly, the term "maximum connected" sounds rather obscure anyway to non-math folks. (Like, "Ok, so far about the neighbors that are c-regions. But what about others?") By referring to "all regions ...", we can implicitely clear the confusion which otherwise is likely to arise due to our unusual idea of "connected". To facilitate understanding - at the cost of some exactness -, I`d rather make use of such possibilities. Even without an explicit definition, the reader can easily see that the term "region", where not specified as either "c" or "non-c", embraces both.

Anyway, this is not "my" page, just "my" 2 ct.

[edit]

The actual algorithm

jvt: Using these criteria "backwards" as an elimination test may be more effective for an algorithm. A graph of regions and chains of the same color is generated, then it's like pulling a thread. False eyes don't satisfy the criteria and get eliminated.

Here is a description of my Java code (fully tested!)
Initially:
C is the set of all c-chains = {maximal connected sets of c points}
R is the set of all c-regions = {maximal connected sets of not c points}

Remove from C chains having less than two adjacent c regions in R with all their empty points adjacent to the chain.
Remove from R regions having an adjacent c chain that is not in C.

Repeat steps 1 and 2 until nothing remains to remove. The resulting C is the set of all unconditionally alive c chains.

Dmitry: I want to elaborate on the termination condition. You can terminate if there was no removal in step 1 OR no removal in step 2. The reason is quite simple: if there was no removal in step 1 then step 2 will have the same result as previous step 2. If there was no removal in step 1 and this is the first time we have entered step 2 then there will be no c chains not in C, so step 2 will have no effect. Similarly, if there was no removal in step 2 then step 1 will have the same result as previous step 1. I hope that made sense :-)

This is a nice algorithm. I've started to implement it, but then realized that it gets the following wrong:

This happens because the marked point is not adjacent to the c-chain and so this c-chain is not unconditionally alive and gets removed from C.

Dmitry Kamenetsky
blubb: The term "unconditionally alive" is ambiguous. It is often assigned to groups that can be successfully defended without ko, regardless of the attack. However, Benson's algorithm checks for pass-life. This black group is not pass-alive.

Oh oops I realized I was wrong, the group in my first diagram is indeed NOT unconditionally alive, so Benson gets it correctly. Dmitry

KarlKnechtel: That's very much what I had in mind with my contribution to the Formal Definitions of Eye, actually. :) I think this algorithm works:

Define a s string as a maximum connected set of s points, where s is one of {black, white, empty}.

Draw the graph where each vertex is in one-to-one correspondence with the strings on the board. The edges should connect identically each pair of vertices which correspond to adjacent strings. Each vertex may also have a 'mark' associated with it; every vertex is initially unmarked.

Repeat until no change is made on any iteration:
- Unmark every empty string.
- For each empty string: if all the adjacent unmarked strings are of the same colour, mark the empty string. The marked empty strings are temporarily considered "eyes".
- For each non-empty string: if there is no more than one adjacent, empty, marked string, mark the string. The marked non-empty strings are identified as "not unconditionally alive".

blubb: To deal with some special cases, this (nice!) algorithm supposedly needs to be modified somehow. Kjeld Petersen: Does it matter who played last? blubb: Unless you think of pass fights: no, it doesn`t matter. As we are talking about pass-life, all relevant sequences consist of moves by the attacker only, anyway.