Instant Eye Tester
(For a general discussion of the formal definition of an eye, see Formal Definitions of Eye. Below is a more personal page by Matt Noonan)
There was once a discussion among Go programmers and others in the newsgroup rec.games.go as to whether or not you could tell if an eye was real or not without searching the game tree to see if the group could die. It turns out you don't need to do such a search, assuming that the group has only single-point eyes.
First, a few definitions.
Paths
A path from stone A to stone B exists if there is a direct, solid connection (in the legal, Go sense) between the stones:
Here, there is a path between the two marked stones.
In addition, a path can skip over a single space as if it was filled by a stone of that color. So:
is also a path.
Properties of Paths
Paths have some nice mathematical properties which will simplify things:
- symmetrical There is a path from B to A if and only if there is a path from A to B.
- transitive If there is a path from A to B, and there is a path from B to C, then there is a path from A to C.
Strings
The next level of abstraction is the string.
Let S be a set of stones on the board. S is a string if and only if, for all A,B in S there is a path between A and B.
The following examples should clarify:
Dieter Verhofstadt: why is this concept introduced? It's never used in the rest of this section.
Matt Noonan: It's been a while since I wrote this, but I think that in the section below, when I say "group" what I meant was "string". Still, it's only to justify the method, and not really needed to operate it.
Anonymous?: As the definition of a path is an equivalence relation (it is reflexive, symmetric and transitive) then, afaict, there is no distinction between a path and a string. S is a path <-> S is a string.
Anon2?: @Anonymous, no there is definitely a distinction. Here is a string which is not a path:
Eyes (True, False, and Otherwise)
Finally, we can define real eyes and false eyes in a static way.
Let an eye be any point which is surrounded on all four sides by stones of the same color - in case the eye isn't at an edge or corner - Let these four stones be called A, B, C and D, and define the set L = {A, B, C, D}
When talking about a real eye, what we mean is that the stones that define it are all connected to the same group. Therefore:
Let E be the eye to be tested, and let L be defined as above. An eye is a real eye if and only if for all x,y in L there exists a path between x and y, provided that the path does not go through E right away (since this would allow jumping across the eye to connect x and y directly).
If E is an eye and E is not a real eye, then E is a false eye.
Because of the properties for paths given above, it follows that rather than testing up to 12 paths per eye, it is sufficient to only test 6: A-B, B-A, A-C, C-A, A-D, and D-A (the restriction on the starting move for the path breaks the commutativity of the paths).
This is not exactly correct. You didn't exclude the reflective cases. For 4 Eyes there are 16 connections to check. You need to tell that Connections are reflective, too.
Brian M: According to this rule, wouldn't this be an eye?
The corners are a single space, so can't the path continue through them? I.e., wouldn't there be a string that wraps all the way around the eye, therefore connecting all adjacent stones?
David Peklak: The restriction should rather say that the path must never pass through E, and not only at the first step. Otherwise this would be a real eye:
Because I can always start the path going to another stone and jump the eye later. So if my assumption is correct, the commutativity of the paths holds again and only three tests are necessary.
Examples:
This method can even correctly give the status of this four-group beast:
Some friends and I have played around a little with extending the concept of "eye" to larger eyeshapes, but haven't put enough work in to generalize these techniques, though it looks at least somewhat promising.
Not exactly practical for everyday playing, but maybe interesting to the Go-programmers and bored players out there.. :)
-- Matt Noonan
David Peklak: I think I found a more simple aproach that works without searching and defines unsettled eyes as false eyes: Say the black eye "E" is surrounded by the black stones A, B, C and D has to be checked: Imagine white stones occupying all liberties of A, B, C and D as far as this is possible without putting white stones in atari. If neither A, B, C or D are in atari now, the eye is real, otherwise it is false.
Check out the logical definition in Formal Definitions of Eye. -- Dieter
FCS: Hmm... seems to me that there is only one real eye here and that the shape is unsettled. Whoever plays at a first will win.
Matt Noonan: It's true that the algorithm counts unsettled eyes as real eyes, but the main idea was to find false eyes without search, so there is a sort of implicit assumption that no more moves will be made. Perhaps it is better suited to automatically finding dead stones at the end of a game?
Bill Spight: What if a path were defined to go only through stones or eyes of the same color?
Then the marked point would not be an eye, because there is no path from the marked stone to the other Black stones, except through that point right away.
Also, between false eyes and real eyes are fractional eyes. See "Eyespace Values in Go" by Howard Landman, in Games of No Chance.
jsha: The above definition is not computationally useful, because you must determine all other eyes first. For instance, it is impossible to determine the status of this group using the above method. Each marked point is an eye only if the other marked point is an eye.
rubilia: To deal with the entire set of strings and eyes simultaneously, BensonsAlgorithm works quite well. Also, it doesn't require the eyes to be single-point ones.
What about this: Select a maximal group of chains that are all connected by eyes (real or false). Those eyes will be considered Unsettled Eyes. For each eye, do the eye test above, but a path cannot pass through an empty space unless it is an Unsettled Eye. If an eye fails the test, it is a False Eye. If no eye fails the test, the remaining eyes are all Real Eyes. If any eye fails the test, do the eye test on each remaining Unsettled Eye again. Repeat until you no longer find any more False Eyes. This algorithm also has some problems in that it can't pick out groups which have a string of false eyes but are alive (see diagram), but under the strict definition of "cannot be killed under an arbitrarily long sequence of consecutive moves by opponent," such groups aren't really alive anyhow.
Anyway, more to the point:
There is the question about what to call this shape (a ponnuki?). (Charles: You can call it a diamond - but ponnuki is definitely misleading.) I'd call it an eye in the absence of black stones. Perhaps the procedure can be expanded to find real, false and undefined eyes? This might not be possible without search, though.
Two (unsettled) eyes, but dead
I've tried finding some real eyes with this false-eye-test, but it fails on this example:
There are paths between each two of these black stones that don't touch the circled eyes, thus defining them as "real". But black is dead anyway.
If black plays on a, white can answer on b and take out one eye. If black plays on b, white could answer on a and also take out one eye.
I wonder if another path-definition should be used to determine real eyes. E.g. a path without spaces should be necessary. Well, I'm still thinking. (stw)
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 alive groupset: a groupset in which all of the members are orthogonally connected to two territories.
If every member of the groupset has two territories, those territories are eyes. Give me a counterexample if you please.
Benjimin: Counterexample: It seems that if an otherwise obviously live collection of stones happens to have captures within its eyespace, it is not defined above as an alive groupset. Territory definition seems to be a major difficulty. Consider having an alive enemy group inside the potential eyespace, or even the case where both potential eyes are completely filled by enemy groups that each have only one (two-point) eye respectively, although the latter case is not settled.
See also the pages in the Eyes Collection.