Benson's Definition of Unconditional Life
This article explains the meaning of unconditional life as defined by David B. Benson in his article Life in the Game of Go. It also describes Benson's algorithm for finding the chains that are unconditionally alive.
Table of contents |
Background and Significance
A set of chains of a player is said to be pass-alive if none of the chains in this set can be captured even if the player always passes. However, the above definition can be tedious to apply, because the required search space to prove pass-alive can be large. Benson defined the concept of unconditional life in a way that is easier to apply, because no search is required. At the same time, Benson also proved that a set of chains is unconditionally alive if and only if it is pass-alive. As such, unconditional life and pass-alive have become synonyms.
Note that Benson does not consider issues such as ko, seki, good or bad moves, opponent's answers. This is because only unconditional life is considered here.
Benson's definition of unconditional life also leads to an algorithm for finding chains that are unconditionally alive, known as Benson's algorithm. This algorithm is not easy to apply manually, and therefore is intended for computer life-and-death programs. Unfortunately, Benson's algorithm is only used by a few specific life-and-death programs and modules.
Benson's Definition of Unconditional Life
Benson's definition of unconditional life requires that the ruleset in use prohibits suicide. For simplicity, without loss of generality, we only explain what it means for a set of Black chains to be unconditionally alive.
We consider a set of Black chains, which we denote as X, for which we want to determine whether it is unconditionally alive. It is convenient to first define what is a region, which is a connected set of intersections, regardless of their colour. We then consider a Black-enclosed region, which is a maximal region containing no Black stones, and that all the Black chains that enclose or surround this region to belong to X. Note that X can have zero or more Black-enclosed regions.
In this example, there is a Black-enclosed region consisting of five intersections, of which three are empty and the other two have White stones. Note that the single Black stone is not part of the Black-enclosed region. Also, because only the maximal region of empty or White intersections is considered, any proper subset of these intersections do not form a Black-enclosed region.
Now, we say that a Black-enclosed region is vital to a Black chain in X if all its empty intersections are also liberties of the chain. Thus, a vital Black-enclosed region cannot contain White stones that form something that is similar to an eye in the stomach inside.
In this example, the left Black-enclosed region is vital to the left Black chain but not vital to the right Black chain. ( is not a liberty of the right chain) The right Black-enclosed region is vital to both Black chains.
Finally, we say that a set of Black chains X is unconditionally alive if each chain in X has at least two distinct Black-enclosed regions that are vital to it. If a set of Black chains X is unconditionally alive, then the Black regions of X are its eyes (in the ordinary sense in Go).
In this example, these two Black chains are not unconditionally alive, because the Black chain on the right has only one Black-enclosed region that is vital to it. If Black always passes, then White can capture the Black chain on the right by playing at a followed by b.
What Benson's definition of unconditional life means that if Black always passes, and White attempts to capture a chain in the set under consideration by filling its liberties, then White will have to perform suicide in one of its eyes at some point of time.
In this example, the both Black-enclosed regions are vital to the Black chain. Therefore, this Black chain is unconditionally alive.
In this example, all the Black chains are unconditionally alive.
For more examples, go to this page.
Benson's Algorithm
Using his definition of unconditional life, Benson also came out with an algorithm for finding a maximal set of unconditionally alive chains for a player. Again, we describe Benson's algorithm for the Black player.
Initially, let X be the set of Black chains, and let R be the set of Black-enclosed regions of X. We perform the following two steps repeatedly:
- Remove from X all Black chains with less than two vital Black-enclosed regions in R.
- Remove from R all Black-enclosed regions with a surrounding stone in a chain not in X.
We stop the algorithm when either step fails to remove any item. The resultant set X is then the desired set of unconditionally alive Black chains. In the process, chains with false eyes are removed from the set of unconditionally alive chains.
The algorithm can be finalized by removing from the remaining R all Black-enclosed regions that are not vital to any chain in the remaining X. This way the final R will give the unconditional eyespace (unless Black decides to fill his own eyes, of course).
In this board, we start the algorithm with five chains in the set X, i.e., the chains containing A6, A3, C2, D1, and E6 respectively. The set R contains all six Black-enclosed regions labeled a to f.
In the first iteration, we note that region f is not vital to any Black chain. For the C2 chain, only region d is vital to it. For the E6 chain, only region c is vital to it. Therefore we remove the C2 and E6 chains from the set X. As a result, region f is surrounded by C2 and E6, which are not in R, and therefore region f is removed from the set R.
In the second iteration, we remove regions c and d from the set R. Now the set X contains the A3, A6, and D1 chains, and the set R contains the regions a, b, and e.
In the third iteration, we note that for the D1 chain, only region e is vital to it. Therefore the D1 chain is removed from the set X, and we remove region e from the set R as well. Now the set X consists of the A3 and A6 chains, and the set R contains the regions a and b.
In the final iteration, no chains or regions can be removed from the sets X and R. Therefore, the set of unconditionally alive chains consists of the A3 and A6 chains.
Unconditional Life on Rulesets that allow Suicide
Benson's definition of unconditional life only works for rulesets that disallow suicide. To adapt Benson's definition for rulesets that allows suicide, the notion of vital Black-enclosed regions needs to be modified. Specifically, instead of requiring that all empty intersections of the vital Black-enclosed region to be adjacent to the Black chain, we now require that all intersections (empty or otherwise) of the vital Black-enclosed region to be adjacent to the Black chain.
This Black corner is unconditionally alive for rulesets that prohibit suicide. However, for rulesets that allow suicide, it is not unconditionally alive by the modified definition. This is because the intersection at the stone is not adjacent to the chain, therefore the two-space Black-enclosed region is not vital to the chain. Indeed, White can commit suicide at a, then play at a, followed by b to capture the stone.
These Black chains are pass-alive, regardless of whether the ruleset allows suicide or not.
Notes
The term Black-enclosed region does not appear in Benson's article. He uses the term small Black-enclosed region instead, with a more constrained meaning. However, this more constrained meaning is not required for defining the term vital.
The definition of two-eye-formation identifies a subset of chains that are unconditionally alive and with exactly two eyes. In particular, unconditionally alive chains with liberties outside their enclosed regions are not two-eye-formations. Therefore, a player can turn a two-eye-formation of his into a non-two-eye-formation by capturing some of the opponent's stones that surround it, even though it will continue to be unconditionally alive.
Reference
David B. Benson. Life in the Game of Go. Information Sciences, Vol. 10, pages 17-29, 1976. Reprinted (with corrections) in Computer Games II, 1987.
See Also
- Construction problem 1
- The Benson Pass Alive algorithm can be implemented with BinMatrix'es.
This page is part of the eyes collection.