Formal Definitions of Eye
This article collects attempts by many contributors to formally describe the concept of eye and the criticism and discussion those attempts have attracted.
These attempts go beyond the vague definition used in the main article Eye and the so-called 2/4 rule, used at Recognizing an Eye to help recognise potential eyes. Examples of groups that live despite their “eyes” failing the simple 2/4 test are found at Two-headed Dragon; two-headed dragons are important test cases for any formal definition.
The article begins with a summary of David Benson’s Definition of Unconditional Life, which is a mathematically proven definition in terms of eyes of chains and thus forms a benchmark for other attempts.
A summary of David Benson’s definition
- For more details see Benson's Definition of Unconditional Life and his paper cited there.
- This is a definition that actually works, may serve as a benchmark for comparing other attempts and supplies some more test cases for them. It does not however define eyes of groups but of chains.
- Patrick Traill: I have added this for the reasons just stated, but it needs some checking, and some of the material might be more useful in the Benson article. I hope to do both in the next day or two. N.B. also to check if our article correctly renders Benson's definition of “``R`` is vital to ``b`` in X”.
Benson’s Theorem
David Benson proves mathematically that a set of chains of one colour being ‘unconditionally alive’ is equivalent to it being ‘safe’. He defines ‘safe’ to mean pass-alive, i.e. none of it can be removed by a sequence of legal moves by the opponent; ‘unconditionally alive’ is defined below in terms of ‘eyes’ of chains.
Benson used his definition to justify a computer algorithm for determining safe stones far more efficiently than by checking the tree of possible sequences with backtracking. This is possible because of the equivalence between the dynamic property ‘safe’ and the static property ‘unconditionally alive’.
Benson’s Definition
This definition is adapted from the materials cited above, using the term ‘eye’ where they speak of a ‘vital region’:
- A set ``S`` of ‘chains’ of a given colour ``C`` is unconditionally alive if every chain in it has two ‘eyes’ ‘enclosed’ by ``S``.
- A chain is (as usual) a maximal strictly connected set of stones of the same colour ``C``.
- An eye of a chain ``H`` enclosed by ``S`` is a maximal strictly connected set ``E`` of empty points and opposing stones ‘enclosed’ by ``S`` in which every empty point is adjacent to ``H`` (is a liberty of ``H``).
- This is known in Benson’s Definition as a ‘black-enclosed region vital to a black chain’ (if ``S`` is black).
- If suicide is allowed, then any opposing stones in ``E`` must also all be adjacent to ``H``.
- A set of points is enclosed by ``S`` if it is not adjacent to any other point of colour ``C``.
Note that in this definition:
- Eyes are defined for chains rather than for groups and two are needed for each chain rather than for the group as a whole. This is different from the way in which eyes are usually introduced, which also omits the adjacency condition.
- An eye in the stomach does not provide an true eye for the surrounding group, as the enclosed eye is not adjacent to any of its chains.
- This definition is immediately applicable to go on an arbitrary graph (the concept ‘enclosed’ does not depend on a concept of inside/outside).
False and blind eyes
- The diagrams below may also prove useful as test cases for other definitions
When a set ``S`` fails this test, some chain ``H`` in ``S`` has at most one genuine eye, though it may touch eyes of other chains.
- If ``H`` touches only one eye, whether its own or of another chain, that is a false eye in the usual sense (f below).
- If ``H`` touches two or more eyes of other chains, of which at most one is its own, it does not touch all free points in those other eyes. The opponent can capture by partly filling the other eyes and then completely filling the own eye (if any). One might call such an eye of other groups a ‘blind eye’ of the chain (b below). It can also be false (g below).
False eyes and ‘blind eyes’
For the chains marked :
- f is a false eye
- g is false and blind
- b are blind eyes
- r is a real eye of the chain
(Unmarked chains may extend off the regions shown)
Robert Jasiek's scoring solution
RobertJasiek: After 5 years of absence from this page, I come back and you still have not stated a general definition of "eye"... First I suggest you read and understand [the [Japanese 2003 Rules], version 35a| http://home.snafu.de/jasiek/j2003.html]. From those rules' methods, defining eye, eye space, etc. in general is just a matter of hours. However, the following is necessary: Either you presume those rules or you a) presume some other rules, b) define "hypothetical-sequence", "hypothetical-strategy", "force" or analogous terms, and c) apply all that. Elsewhere (rec.games.go, etc.), I have given definitions of basic go terms like "eye" or "seki" for any position as if it were a scoring position. If you want an "eye" definition for any position interpreted as a current game position, you need to "copy and paste" the (b) terms for a continued played game to end in a final position that is only then scored a la Japanese 2003 Rules. I.e., you need a two-stage iterative application of its concepts. Should be easy enough if only you have understood those rules and can write well-defined definitions. If you don't do it in 20 hours without any mistake, then you will never succeed.
kb: Robert, let me give two definitions of an eye. The first definition does not try to handle seki situations, the second does.
1) An eye is an empty point of space surrounded by stones of one color such that a stone of the opposite color can only be played there after first playing to remove all external liberties from all eye-surrounding stones, given any number of consecutive moves from the player holding the opposite colored stones. 1) An eye is an empty point of space surrounded by stones of one color such that a stone of the opposite color can only be played there after first playing to remove all external liberties from all eye-surrounding stones, given local optimal play by both players.
You may define "local optimal play" however you like, but I use it to shortcut writing rigorous definitions of how alternating consecutive moves work. If you like, most of the time "local optimal play" is well-defined in terms of a life-and-death problem.
kb: Second comment. I haven't been on Sensei's as long as you, but your post here and in other areas seem to be slightly condescending. From reading many of your other contributions, you never appear to offend, but your words sometimes come off as offensive. (From my relationship with my wife, I am well aware that actions and impressions speak louder than intentions.) I thought wikis like this are to be for everyone's collaboratory benefit, not just a subset of them.
I am not saying this to parry any warranted criticism from my definitions above, so please criticize away.
RobertJasiek: Your attempt continues to make the same mistakes: 1) You fail to presume a ruleset. 2) You use grammar ("can") insted of contents ("can force"), i.e., you should rely on definitions of "hypothetical-strategy", "hypothetical-sequence", etc. Furthermore you make a new mistake: You use but do not define "external".
Yes, my criticism above is meant to sound harsh. How else does everybody wake up here to do at least the basic things right like a) presuming a ruleset, b) relying on formal definitions of sequences, strategy, and force, c) using instead of ignoring already solved intermediate steps. Everybody here tries to reinvent the wheel while the wheel already exists. Note that the reference to the Japanese 2003 Rules is essential because they do define "hypothetical-strategy", "hypothetical-sequence", "force", and the terms used but not defined again below. (There may be trivial gaps because the Japanese 2003 Rules were slightly changed after the cited definitions below had been written. E.g., "region" needs to be defined again as "either black-region or white-region".)
Citation
Subject: Group, Seki, Eyespace: Definitions
Date: Tue, 18 Nov 2003 18:37:42 +0100
From: Robert Jasiek
Newsgroups: rec.games.go
RGG: http://groups.google.com/group/rec.games.go/msg/e7cf3b4ec0848f3f
SL tries to define some basic terms unequivocally. Below I provide unequivocal definitions under the assumption that the Japanese 2003 Rules would already be in their final, unequivocal version.
http://home.snafu.de/jasiek/j2003.html
Definition: A black-group is the union of all black-strings of a black-region.
Definition: A white-group is the union of all white-strings of a white-region.
Definition: A group is either a black-group or a white-group.
Note: For other purposes one might want to define group differently.
Definition: An in-seki-space is a dame and, recursively, any adjacent dame or any adjacent intersection of an in-seki region.
Definition: A seki is the union of all strings of an in-seki-space.
Definition: A group is independently-alive if it is not part of a seki.
Definition: A black-eye is a black-eye-point and, recursively, any adjacent black-eye-point.
Definition: A white-eye is a white-eye-point and, recursively, any adjacent white-eye-point.
Definition: An eye is either a black-eye or a white-eye.
Definition: A black-eye-space of a black-group is the union of all black-eyes of the black-group's region.
Definition: A white-eye-space of a white-group is the union of all white-eyes of the white-group's region.
Definition: An eye-space is either a black-eye-space or a white-eye-space.
The definitions apply under the Japanese 2003 Rules and for some final-position. The latter is created trivially. For other rulesets, some modifications of the rules would be necessary. It is no problem if the scoring system should differ.
Attempt by Dieter, commented by Tapani Raiko
- A virtual eye is an empty space, reached by chains of the same color.
- A group lives, if every chain reach two virtual eyes, and both eyes are reached for all the chains.
[1] (If chains that don't reach the virtual eyes can connect to the chains that do, without filling any of the virtual eyes chosen, they can be included in the living group).
Reach is meant as in the Tromp/Taylor rules, i.e. “have a chain of its own colour reaching a given colour”. “Virtual eye” because it deviates from the concept of “eye” we are accustomed to.
Actually, this works great for humans! This is exactly the method I personally use (and last I checked I was a human). It is easy to quickly visually check if all your chains can reach both eyes. If one of your chains can only reach one eye, and can't be joined to one of the other chains (that reaches both) - then it isn't part of the live group. Furthermore, if such a chain is forming one of the eyes - then that eye is false. This is exactly and clearly the case with the chains above the point a in the first two figures on this page.
This brings up two points:
- Does it make sense to define the concept of "false" eye out of the context of finding two live eyes?
- This discussion uses the term "chain" where I've seen other literature use "string". And the Instant Eye Tester uses "string" to mean something else.
I suppose that's why this whole sequence needs ToBeMasterEdited!
The previous definition does not cover this simple example. These chains do not reach the same virtual eyes.
[2] (Bookmark)
My proposition for the definition is:
- A virtual eye is an empty point, reached by chains of the same color.
- A chain is about to live, if it reaches two virtual eyes that are not falsified.
- A virtual eye becomes false, if it is reached by a chain that is not about to live.
- A chain lives unconditionally, if it is still about to live when all the appropriate eyes are falsified.
A chain is said to be alive, if the unconditional life can be obtained with alternate play. Seki is not taken into account here.
If one would like to use the definition with larger eyes, they should be careful. This would be alive using the definition, if virtual eyes larger than one would be blindly accepted.
-- Tapani Raiko
If you include the side remark^{[1]} of my definition, your example meets it. The point A is then a connection point, and not a virtual eye.
(TapaniRaiko: Sorry, missed it. (Or there is a slight inaccuracy in the definition: no chain reaches the two virtual eyes in the example, so nothing can connect to such a chain either.) My definition is more complicated, but it does not require the selection.)
About your definition:
- The concept of a living chain relies on the concept of a false eye.
- The concept of a false eye relies on the concept of a living chain.
The definitions are thus self-recurrent.
(Tapani Raiko: Think of it as an algorithm. Virtual eyes are implicitely not false until the algorithm changes them to be. I did not want to write it mathematically, since it is less readable.)
About the Purpose of a Definition for Life
There is a difference between giving a correct definition and including theorems in your definition.
Of course other configurations of stones (chains) are said to be alive even if they don't meet the definition. That is because we know that the groups can always evolve to the status mentioned in the definition. Examples:
This group is alive but not according to the strict definition of alive. It's alive because it will always be able to make two eyes. One can't include such groups in definitions. Rather you make a "theorem" saying that this group is alive, and give a proof.
(Tapani Raiko: Having two eyes is a shortcut to know that the group can not be captured. You can end reading, when Black gets two eyes. "A chain has two liberties that the opponent cannot remove" is a nice definition in itself and these two just clarify, what the unremovable liberties would look like. A "better definition" could cut the reading shorter. In fact a lot of Go knowledge is shortcuts. (like: The L group is dead.))
How about this:
Definition:
- A virtual eye is an empty point, reached only by chains of the same color.
- A collection of chains lives with eyes, if all the chains reach the same two virtual eyes.
Addition:
- A group of stones is alive with eyes, if for any sequence of moves by the opponent, there is a sequence of answers that turns the group into a collection of chains complying with definition 2.
Remarks:
- The definition reads "if" and not "if and only if".
- There is no question of bigger eyes. A virtual eye is one empty point reached only by chains of one color (so no other empty points).
- The definition does not include seki.
- The addition gives a method to bring down the status of a group to the definition. The addition is not included in the definition, since there are groups of stones for which no pro, let alone a computer program, can decide whether they are alive or not.
Topological life, as defined by Howard Landman
Bill Spight: Howard Landman, in his "Eyespace Values in Go" paper in Games of No Chance, defines topological life this way: A group is topologically alive if and only if the chains of the group surround more than one one-point eye, and each chain reaches more than one of those eyes. The definition given above, which required all chains to reach the *same* two eyes, is not so good. Each chain just has to reach two eyes, not necessarily the same ones.
RobertJasiek: This is not a definition because "one-point eye" is undefined. But this is fixed easily: "single empty intersection". Likely, "group" can be clarified as "set". "Surround" can be clarified as "adjacent to and only adjacent to". - This kind of definition, quite like my two-eye-formation, provides static definitions. Such can be useful for simplistic rules like, e.g., greedy ancient rules or for terminal shapes to that all other shapes shall be reduced in an analysis phase. Static eye definitions do not answer in general what an "eye" is.
Karl Knechtel's attempt
Karl Knechtel: This is my attempt at definitions. It has an aesthetic advantage in that there is no distinction between chains/strings/groups/whatever. I'll call them strings.
Define a path as a set of stones including a and b such that every stone is orthogonally adjacent to some other stone in the set.
Define a string as a path which is not a subset of a larger path. (This is the easiest way I can think of to specify the things formally.)
Define an eyespace as a set of points on the board satisfying the above definition for string, except with "stones" replaced with "empty points".
Define a liberty of a string (just to make sure we're clear on everything) as a point which is
- empty; and
- orthogonally adjacent to some stone in the string.
Define an eye as an eyespace, such that every string which has a point in the eyespace as a liberty is of the same colour. These strings are said to enclose the eye.
Define a simple eye as an eye, such that every point of the eye is a liberty of every string enclosing it. (A 3x3 eye is not "simple", therefore: this is important to the definition of unconditional life which follows, because with infinite passes a group with two such eyes could be captured. See Two Eyes Can Die.)
Next, apply the following algorithm to define true eyes and false eyes:
- Mark every simple eye on the board as true.
- Iterate until no more simple eyes are marked false on an iteration:
- For each string on the board:
- If there is exactly one simple eye such that
- the simple eye is marked as true; and
- some point of the simple eye is a liberty of the string being considered,
- then mark that simple eye as false.
- If there is exactly one simple eye such that
- For each string on the board:
A true eye is any simple eye which is marked true after application of the algorithm; the simple eyes marked false are false eyes. (Large spaces are still not categorized as eyes; the idea is that further play can settle them into simple eyes which will almost certainly be true, but sufficient passes allow the other player to capture.)
Then:
[3] (Bookmark)
A string is unconditionally alive if and only if its liberties include two true eyes.
It is alive in sente if and only if,
- it is not unconditionally alive; and
- for any alternating play starting with the opposed player, the player owning the string can make it unconditionally alive. This is sufficient for "life" in endgame evaluation, I think.
It is alive in gote if and only if,
- it is not alive in sente or unconditionally alive; and
- there exists a point on the board such that if a same-colour stone is played there immediately, the group becomes alive in sente or unconditionally alive.
It is unconditionally dead if and only if there does not exist a set of points such that occupying those points with same-colour stones would render the group unconditionally alive.
It is dead in gote if none of the above apply, and it is not one of a pair of strings alive in seki:
Two strings are alive in seki if and only if
- the strings are opposite colours;
- for all points which are liberties of both strings, if a stone were played there by either player, both strings would immediately become alive in gote.
(Slight change here. "There exists" was the wrong criterion for the shared liberties in seki. If playing in one liberty makes a living shape and playing in the other makes a dead shape - that's no seki.)
Finally:
The game is completed when
- Any stone placed on the board by either player, not orthogonally adjacent to a string of the same colour (so that it forms a new string), would be unconditionally dead. (If it is dead in gote, the other player might well pass; but we should still demonstrate the status of the other group, for the reason given below, I think. Is it fair to punish new players by making a doomed invasion a contract to play until the string is unconditionally dead?);
- No string on the board is alive in gote or dead in gote. (The reason being that plays can render dead in gote strings alive in gote; if each player does that, then the next player has to choose between making his/her own group alive in sente or killing the other group, so the position is still unsettled.); and
- Having satisfied the above criteria, and having removed all unconditionally dead groups from the board, every empty point on the board is then either
- part of an eye (what we would call "territory"), or
- a liberty of a string which is alive in seki.
I think this is self-consistent, and sufficient to cover all cases. Comments?
RobertJasiek: I have read deeply enough to say that you have failed to define "eye" in general. Reasons: 1) You do not presume a ruleset. 2) You use grammer ("can") instead of contents ("can force"). You should understand the Japanese 2003 Rules and then adopt their methods. Thereby you could integrate a definition for "force". There are some alternatives for "force", but you use neither.
Saesneg's attempt
Saesneg: I think I can simplify your definition, though I consider it doomed from the outset!
Every point on the board has the colour black, white or empty. If a point is not empty it is filled.
Two points are hard-connected if they are the same colour, and there exists an orthogonal path from one to the other via other points of the same colour.
A string is a set of points of the same colour such that every pair of members is hard-connected, and none is hard-connected to any non-members. Note that by this definition a string may consistent of empty points.
Two strings are adjacent if any member of one is adjacent to any member of the other. Two adjacent strings are called neighbours. Note that neighbours are, by definition, coloured differently.
A simple eye is a small empty string whose neighbours are all the same colour ('small' will be discussed later!).
Two filled strings are soft-connected if they are the same colour, and there is a path from one to the other via simple eyes and strings of the same colour.
A group is a set of filled-strings such that each pair of members is soft-connected, and none is soft-connected to any non-members.
Every simple eye adjacent to a group is a true eye, except those with a neighbour which is adjacent to only one true eye. Is this recursive statement logically well-formed?
A group with two true eyes is alive.
Unfortunately these attempts to formalise the definition of life cause as many problems as they solve. I do think they are useful as long as you continue to apply intuition and 'common sense' (which can feel very uncommon to a beginner). Firstly a sufficiently large eye is not really an eye in any meaningful sense. Secondly an eye can in practice be adjacent to strings of either colour, when it contains dead stones. Any attempt to define a dead stone rigorously is not for the faint-hearted. If there really were a simple formal definition of true eyes Computer Go would be a lot stronger than it is.
jvt: Semantics... in my opinion you can't define a single global true eye rigorously but it's easy to define two (or more) eyes. There is a simple formal definition of true eyes no one mentioned yet: a stone or group of stones is said to have two eyes if there is a way for the defender (even if the attacker plays first) to reach a configuration (including these stones) which Benson's algorithm recognizes as unconditionaly alive. That's all. Simple isn't it? This algorithm is used in Computer Go by some life and death programs / modules. Search + Benson as a cutoff test recognize all sort of shapes that are alive with two eyes, including any two-headed dragon, etc. Benson's algorithm is static (i.e. without search). There is no way to recognize two eyes generally without search. However many programs use an eye shape library for the most usual shapes.
Dieter: Due to a question I received by a reader who felt like not disturbing this community - (we want to be bothered more!) - I feel compelled to add that the subject of the discussion are groups of stones of different colour that are both alive (can't be captured), yet do not fall under the usual forms of co-existing life we encounter on the board:
- seki (there are approach moves that neither party can occupy)
- two eyes, where eyes are recognized as being of a certain shape (real, not false)
One of the examples under discussion displays a group with two (or more) eyes that we ordinarily recognize as being false, yet the group is alive. The whole issue is rather of formal-algorithmic kind than crucial to our understanding of Go.
This is the curious situation I proposed.
There have been several definitions of eyes and alive / dead groups in this discussion. In this situation the small white group is unconditionally alive (black can't do anything to capture it) and the black group is dead (white can capture it at any time if needed).
I was simply wondering how well the definitions of an alive group presented here can handle this situation.
- Juha Nieminen?
Here's another position with 'eyes' that don't easily fit the usual sterotypes.
There are no eyes on the black group, so the implication is that if the position is a seki, there aren't any on the two-stone white groups either.
Bill: Not so. Seki where a group with no eye lies between two opposing groups, each with one eye, are well known.
Here's the same two-stone corner group, but here it's an eye. The black group has an eye, so for seki, the white stones do too.
Second attempt by Dieter
Dieter: It is harder to read what's on this page already than to think of something new. Well, here it comes:
Preamble: the Tromp-Taylor rules
Definitions
A stone is a point not colored empty.
A chain is a number of stones of the same color that all reach each other.
A liberty to a chain is an empty point adjacent to that chain.
A group is a number of chains.
A simple eye belonging to a group is a liberty to at least two chains of that group, which is no liberty to opponent chains, and which can only be filled by the opponent after all liberties of all chains to which it is a liberty, are filled by the opponent.
Theorem
- A group with two simple eyes cannot be captured as a whole, if there is at least one chain reaching both eyes.
I think this covers all examples of groups alive with one-space eyes, which form the basis of the rest of life and death theory.
RobertJasiek: You do not even attempt to define eye in general.
Should eyes own groups?
nstone
Conceptually, it might be easier to think of spaces owning contiguous groups, rather than vice versa. Consider:
A contiguous group of spaces is an ownerspace if it is continuously surrounded by stones of a single color, and/or a section of the board's boundary.
Ownerspaces own all boundary stones and their chains, Any ownerspace within an ownerspace is owned by the inner space. It can be other-colored.
A living group is a collection of stones made entirely of multiply-owned chains, all sharing owners. Assurance of life is equivalent to assurance of multiple-ownership.
Notice that when an ownerspace is entirely filled from the inside by an inner ownerspace, it ceases to exist, and its boundary groups may longer be multiply-owned and can be killed.
Unkx80's attempt
unkx80: Discussion moved from General Eye Definition.
Here is an attempt to give a general (not specific) definition of what is an eye (or sometimes called real eye). It is slightly modified from the 2/4 - 1/2 - 1/1 rule.
To qualify as an eye, the group must satisfy the following two conditions. If only the first condition is satisfied but not the second, then it is deemed as a false eye.
- The group must surround at least one empty point.
- The group must posess the following properties described below.
Confused: Here's an alternative wording for second condition which should work better:
- No subset of the group can be captured without capturing the whole group.
Jasonred OOOH!!! I find that really brilliant, man! Not only is it brief, exact, and clear, but you can actually program it into a computer! Now you can explain eyes and two eyes easily. Dude, you might have just revolutionized Go programming! (well, it'll help if I want to make a go program anyhow, much easier than the these points for sides, these points for corners, etc. thing.
Bill: Confused is right. I do not know of any way to distinguish real eyes from false eyes in general without reference to play. There are many examples that can be distinguished without reference to play, but a general algorithm requires determining whether a cutting stone can be captured without reading.
Matt Noonan: Although this is a decent heuristic for false eyes, i think is is important to remember that it is flat-out wrong. There are groups for which the only eyes have all four diagonals controlled by white. This shows that the problem of finding out if an eye is false is really not a local one. In fact, as Bill pointed out above it is even worse -- in general it can't be done without reading.
Instant Eye Tester has a diagram of a black group with two real eyes, both of which have all the diagonals controlled by white.
(The properties described below will use black eyes, please switch the colours around if we are discussing white eyes.)
For a Black eye in the center, three out of the four marked points must be unavailable to White. The corollary to this is that Two Corners Kills The Eye.
Further Attempts
iopq: Define a group: a group is an orthogonally connected set of stones. Define territory: territory is an empty space surrounded orthogonally by only one color's stones and the edges of the board. Define a groupset: a groupset is a set of all groups that share territory. Define an unconditionally alive groupset: a groupset in which all of the members are orthogonally connected to two territories that are not orthogonally connected.
If every member of the groupset has two territories, those territories are eyes. Give me a counterexample if you please.
You can see that I don't include the positions where there is a white stone in the eyespace as unconditionally alive. That means I should have a broader definition of unconditionally alive. But I don't want to limit myself to rulesets that prohibit multiple stone suicide. I also don't want to include groups that can be killed if the opponent can move as many times as he or she wants in that local situation. Maybe if I define territory as a set of stones of the other color and empty points... but then I'd have to say that those stones are also dead... which would be a recursive definition. And I'd still have to include not "unconditionally dead" stones in that definition. Too much work.
1. Define a group: a group is a set of orthogonally connected stones.
2. Define territory: territory is an empty space surrounded orthogonally by only one color's stones and the edges of the board.
3. Define a groupset: a groupset is a set of all groups that share territory.
4. Define an unconditionally alive groupset: a groupset in which all of the members are orthogonally connected to two territories that are not orthogonally connected themselves.
Roule: how about this: 1: an "eye" is an empty space with chains orthogonally connected to it 2: an "potentially alive eye" is an eye attached by potentially alive chains 3: a "potentially alive chain" is a chain witch is attached to at least 2 eyes. 4: a group of chains and eyes is alive if all chains AND all eyes are potentially alive and if all chains and eyes are connected. 5: a chain is "attached" to an eye if it is orthogonally connected to it.
RobertJasiek: You fail to consider the ruleset, move sequences, etc.
Unknown: O.K., here's what I've been able to come up with so far. Possibly flawed, but I haven't been able to come up with any counterexamples and I have what I think is a viable if informal proof. Thoughts?
1. A chain is an orthogonally connected set of stones of a given color which is not properly included in another such set.
2. A territory is a set of orthogonally connected empty intersections not properly included in another such set.
3. A group is a set of chains of a given color. A group encloses a territory if the only chains adjacent to the territory are members of the group.
4. Say that a chain "squeezes" a territory if every intersection of the territory is a liberty of the chain.
5. Say that a group is "complete" if the group is included in some group G = {A_1, A_2, ..., A_n} such that for some set T = {a_1, a_2, ..., a_n, b_1, b_2, ..., b_n} of territory, the following are true:
-a_i ≠ b_i, -A_i squeezes both a_i and b_i, -a_i and b_i are both enclosed by G.
Hypothesis: A group is unconditionally alive/has two eyes iff it is complete. (We are ignoring seki as a source of life.)
Proof of sufficiency of completeness (we'll say black has the complete formation): Suppose black's group is complete, so that it's included in a group G as described above. Suppose that some/all chains in G are capturable. In order for this to happen, white must fill in one of the territories of T. Assume WLOG that the first filled territory of T in this process is a_1 on move M. Since A_1 squeezes a_1, white must be capturing one of the chains enclosing a_1 on M, say, A_k, or else he would be self-capturing. However, by assumption a_1 is enclosed by G, so A_k squeezes a territory (WLOG b_k) in T different from a_1. If white captures A_k on M by playing in a_1, he must have already filled in b_k. But we assumed a_1 is the first member of T to be filled in. Contradiction.
Proof of necessity of completeness: Suppose black's chain A_1 is uncapturable. It clearly follows that A_1 must squeeze at least two territories, a_1 and b_1, or else A_1 could be placed in atari (proof of this is easy). Let X be the set of chains enclosing a_1. If any chains in X are capturable, then a_1 can be filled, rendering A_1 capturable. (That is, of course, unless A_1 squeezes a third or fourth or fifth, etc., territory. But we can keep using this reasoning until we get down to its final two squeezed territories, since it only has finitely many.) Hence the members of X are uncapturable as well! So we can place them, along with A_1, in a new set G. We can keep employing the same reasoning to construct the elements of G and corresponding elements of T, which process will terminate since there are only finitely many groups and territories on the board.
RobertJasiek: Whatever it does, it is not about defining "eye" in general.
Me: Well, maybe. I think, if there are no counterexamples I've missed, it formally captures the intuitive idea of eyes as empty enclosed territories which can be linked to other empty territories to make formations invincible.
gromovoi: I think that the statements and definitions are correct and useful for algorithmic implementation within go software. It also gives a linear time algorithm for deciding whether the group could be captured if the defending party is completely inactive (e.g. passes unconditionally).
PlatinumDragon's Attempt
- An eye, in general, is a single point surrounded on four sides (using edges of board is posible) by stones of one color.
- A real eye is a territory enclosed by one color at four sides and at least three corners (diagonal points).
- The edge of the board counts as covering the corners (diagonal points) of the eyes if and only if that color monopolizes the corners (diagonal points) of the eye on the board.
- When a color does not monopolize the eyes' corner (diagonal points) of an eye at the edge or corner of the board, then the eye is false. (Restating the previous comment)
- Two real eyes ensures life for a group.
- False Eyes are all eyes that are not real eyes.
- Two false eyes "facing" each other may give life, but are still false eyes (i.e. double headed dragon).
- Opinion: Maybe we should change the rule so false eyes don't count as territory for the same reason as one colored seki's eyes.
- Comments End.
Leachy's "attempt"
leachy?: I will not attempt defintions of "stones", "chains", rulesets and the like. However, it seems the most logical once one has a definition of "eye" to define an eye to be false when:
Removal of the eye disconnects the "group"
This simple identification of false eyes works of course works though I couldn't be asked to write it down since it is quite obvious that this is a perfect characterization of falsity.
Also it seems that no-one above has noticed that this is far simpler than any of the complex attempts above to define when a eye is "real" or not.
If you think that disconnected is not "defined", see that there is a definition of "connected graph" at http://en.wikipedia.org/wiki/Connected_graph
RobertJasiek: Nice idea, but needs to be worked out a bit because a connecting path can also go the other way round. What you mean is a local disconection of some kind.
Leachy's definitions of stuff
leachy?:
"Group": a connected subgraph G of the board with no enemy stones such that there is no path on the graph of the board from outside G to G that has no friendly stones on the path
"Eye": a connected subgraph of the "group" consisting of empty points such that there are no adjacent empty points.
"False eye": an "eye" E in a group G for which G-E is disconnected
Then, one can cleanly say that a group is "alive" if it has 2 eyes which are not false eyes.
That should do it Robert.
Note: in the above, it must be assumed that there are no enemy stones inside the eye space of the group since then we are put firmly into combinatorial game theory territory to determine if the group can actually make 2 eyes. But the above sorts out the false eye bit easily even in that case.
RobertJasiek: "I am not amused." But I lack time to work out your concept. Just one note: There are also groups with opposing stones amidst them! Why do you want to reinvent the wheel? Understand my definitions! They are correct! Or is your aim only to define "false eye" well? Then please use different words instead of "group" and "eye"; maybe "pre-false-eye-group" or the like.
leachy?: Robert, it seemed to me that many of the definitions given try to eliminate eyes which are ultimately not eyes and much is made of the "two-headed dragon" being some kind of "2/4 false eye" counterexample. I did simply want to point out that it is about connectivity. That's why the eye is false in the first place.
Ultimately, the definition of eye should either include "all eyes including false ones (including eye defects that enable capture)" or one is prepared to simply analyse all available plays by both thereby getting some combinatorial game-theoretic definition of eyes.
Also, I am not "reinventing the wheel" to give a simple graph-theoretic explanation of what I mean.
RobertJasiek: Mine includes all false eyes. (Well, in played out shapes. During the middle game, matters are more complicated.)
leachy?: ...and that is just the nub of it...."played out shapes".
Annonymous: Actually, this seems to be quite brilliant. It may feel a bit counter-intuitive, yet it does have its merits. Consider this situation:
Many go players would likely call the two marked eyes false, yet they suffice to give life to the black group.
With Leachy's definition, both would be considered real eyes, because the stones that would disconnect at either eye are still connected via the other one. And the count of two real eyes gives life to the group. I find that quite an elegant way to handle such situations.
The other interesting situation is this:
Here, the circled eye is false according to Leachy's definition, because it separates the left and the right parts from each other. Thus, two other real eyes are needed to give live to the black group, in this case the square marked ones.
So, while Leachy's definition does not allow us to decide the status of an eye by the local shape around the eye itself, it does correctly sort out at least some of the more tricky corner cases of life and death. That makes this approach really valuable, especially when it comes to computer go.
Bugcat's quick definition
bugcat: This is how I would define an eye quickly, without getting bogged down in technical details:
"An eye is an area of one or more contiguous empty points, enclosed by stones of colour A (a Group), and can be if necessary (through the course of one or more moves) reduced by colour B to having only one empty point within it, which cannot be filled by colour B without colour B filling every other liberty of the Group."
It's not a really formal definition but it's what I'd put in a tournament referee handbook.
Implications for Computer Go
EdPoor2: We want to know whether a group is "killable" and therefore needs to be watched, or is "unkillable" and therefore can be abandoned. If the computer passes continually, and there exists a sequence of moves by the opponent that can kill the group, then it might be "alive" (in a scoring sense) yet vulnerable.
I saw some material by expert author Charles Matthew and others defining "Unconditionally Alive" which contained some disputes. So I'd like to propose using terms like "killable" and "unkillable".
If there are miai points a and b such that the whichever the attacker plays, the defender plays the other one, then the group may be alive. I'd certainly mark it that way at the end of a game on KGS. The famous corner position with 4 empty points in a straight line is what comes to mind. But until the end of the game, that group is killable.
A killable group is relevant to ko battles, isn't it? If it's valuable enough, it may require a defensive response.
So perhaps we could distinguish among types of living groups for middle game play and end of game scoring. In the middle of the game, a living group which is "unkillable" requires no more attention; it does not figure into ko battles. But a "killable" group, even if it's unconditionally alive (in the usual sense) still requires some attention - like a plant that needs watering.
At the end of the game, it doesn't matter so much if it's "killable" (by a sequence of moves where one player attacks and the other passes). What counts in the scoring phase is whether reasonable people agree that with proper play the group will live. A stubborn player might insist on a particular battle being played out.
RobertJasiek: Do you just need n-alive?
See also
- Eyes Collection — A systematic collection of links to articles about eyes
- (add other links there rather than here)