Dear Professor Heine
Your book "2-nd Seminar of Scientific Go Theory" made a great
impression on me. Unfortunately some points were not quite
clear for me because of the absence of some important diagrams.
So, the example announced in the paper by Liu (p.13) looks
very intriguing. The author writes that he has constructed a
position with an absolute live group, which has only one
single eye. It is alive since if an enemy stone is put into
this single eye and hereby remove the whole group, then there
results a reappearance of configuration on the board.
Unfortunately there is no corresponding diagram in the book.
Please send it to me if possible. Also I would be glad to
know what is "Long-Life and Round Robin" Ko (p. 4, dia. 1-3
are absent).
Now it is a pleasure for me to send you some new information
concerning the problem of seki-classification. The position
with the following properties will be constructed here (see
dia. 9).
1) There are 4 Black and 4 White groups. All the groups
are connected and eyeless.
2) 6 groups have 5 dame each, and 2 groups have 4 dame each.
3) The position is a seki -- that is all the groups are
alive.
4) The position is a "complete seki" -- that is, any move
by either player leads to some loss for him. (In other
words, there are no neutral points -- alternatively,
the game is finished by the slowest version of the
Chinese rules).
This position is a counter-example to the Hypothesis 1
in the paper "Seki in Go" (in future it will be referred
to as [1]). This Hypothesis states that every complete
seki, containing connected eyeless groups only, necessarily
has an equal number of Black and White groups, and all
these groups have the same number of dame -- that is, the
corresponding "seki-matrix" (see later) is an even-sum
square (compare with the property 2 above).
We will consider those seki positions which contain
connected eyeless groups only; and we'll give a regular
way to to construct complete sekis, containing groups
with a variable number of dame.
For this purpose we introduce a new model for studying
seki : seki-graphs. This approach is equivalent to
the seki-matrices technique (see [1]) but appears to
be more convenient.
Let us consider a graph, whose vertices (corresponding
to Black and White groups) are coloured with two colours.
Two vertices of different colours can be joined by an
arbitrary number of edges. These edges represent dame
between the corresponding groups
We can define a game, equivalent to the Nil-game ([1]):
Black and White take moves in turn. On the move a
player can remove any edge (but only one edge).
White (Black) wins if, after his move, there appears
an isolated Black (White) vertex. The analogy with Go
is clear. An isolated vertex corresponds to a captured
group. A complete seki corresponds to those graphs
which represent zugzwang positions in Nil -- that is
whichever player moves first, anywhere, loses. Such
graphs will be called seki-graphs. See dias. 1-5, 8,
and 9, for example.
There exists only one seki-graph of two vertices (dia. 1).
There exist three connected seki-graphs of 4 vertices
(dias. 2, 3, and 4). (A disconnected graph corresponds
to several independent positions in Go. We will
consider connected graphs only.) See dia. 5 for
examples of seki-graphs of 6 vertices.
Note that the graphs in dia. 6 are not seki-graphs.
There is no zugzwang, though the player who moves first
cannot win. The corresponding positions in Go will be
seki, but not complete seki (see [1]. dia. 8).
Note also that the position corresponding to a given
graph can be constructed on a flat board, if, and only
if, the graph is a planar graph.
All the seki-graphs considered above have a constant
index. (The index of a vertex is the number of
vertices adjacent to it). Our aim is to construct
seki-graphs of variable index. Let us denote by "m"
the minimal index among all the vertices of the graph.
It can be proved that there exist no seki-graphs of
variable indices, and m = 1, 2, or 3. (I omit the
uncomplicated proof). But for m = 4, there is a
regular way to construct seki-graphs of variable
indices. Consider the piece "Ol" (Dia. 7). Let us
take any seki-graph "Le" of constant index r >= 4;
choose an arbirary edge "e" in "Le" and change it for
"Ol" -- see dia. 7. Seemingly it can be proved that
the resulting graph "G" is a seki-graph.
The sketch of the proof is given here. Let us show
that any move by either player leads to his defeat.
Consider dia. 7. Suppose that Black plays "a", then
White plays "c"; Black is forced to play "b",
detaching a seki-graph of two vertices. Now White
can play in "Le'" = "Le" \ "e" -- that is the same
as if Black had played "e" in "Le". But "Le" is a
seki-graph, hence White can win. Suppose that Black
plays "c", then White plays "a", Black is forced to
play "b", and the result is the same. Suppose that
Black plays "", then White plays in "Le" as if Black
has palyed "e" there, then White can win this game,
because "Le" is a seki-graph. But the game in hand
is "even better" for White, as he has an additional
dame "c".
The single difficult case is when Black plays "d"
somewhere in "Le'". White's idea is to play as if
the game proceeds as in "Le", but in our case we
have "Ol" instead of "e". If, at any time, Black
plays "a", "b", or "c" then it is likely that White
can force the detachment of a seki-graph of two
vertices. However we need some additional
assumptions for a strict proof. But in all the
following simple examples the exchange of "e" for
"Ol" gives a seki-graph. Therefore we will use this
technique as a heuristic for constructing new
seki-graphs.
The examples are given in dias. 8 and 9. If the
initial seki-graph "Le" was of index 4 then the new
seki-graph "G" is also of index 4 -- see dia. 8. If
the initial seki-graph "Le" was of index r>4 then the
new seki-graph "G" will not have a constant index --
see dia. 9. So we obtain the example that we
announced earlier. We see that the simplest
seki-graphs of variable index have 8 vertices, because
there exist no seki-graphs of 4 vertices and of index 5
-- see dia. 6.
More complicated graphs analogous to "Ol" can be
obtained by the repetition of this procedure -- see,
for example, dia. 10. Injecting these graphs instead
of an arbitrary edge in any seki-graph of index ?????,
one obtains a new seki-graph.
To be sure that the position corresponding to a
seki-graph is really a complete seki, one must prove
that the player who moves first can not force a
profitable exchange by sacrificing one of his groups.
An example of such an exchange was given in [1] (see
[1], dia. 13). Thus a seki-graph does not necessarily
correspond to a complete seki. However there is a
simple way to avoid the existence of such exchanges.
If, in the seki-graphs in dia. 5, all 6 groups in the
corresponding Go positions have the same number of
stones, then a profitable exchange is not possible
because the player who moves first (and forces an
exchange) adds one stone to his group, and thus has to
sacrififce a group containing one more stone than the
group he will capture.
The numbers of stones in the groups in dia.. 9 satisfy
the equations:
A1 = A2 = A3 + A4 = B1 = B2 = B3 + B4.
These equations exclude the exchanges. (If the group
A3 (B3) is captured then A4 (B4) is also necessarily
captured, so A3 + A4 (B3 + B4) is to be considered [sic]
Thus the positions in dia. 9 are complete sekis.
These examples, and examples considered in [1] (dias.
11, 12, and 13), show that a simple classification of
seki-positions is hardly possible. These are all the
news concerning seki that I have had.
Moscow 29-6-1981
+++++++++-+++++++++-+++++++++-+++++++++-+++++++++-+++++++++-+++++++++-+++++++++-
Seki in Go
V. Gourvitsh, A. Golberg
Group Analysis of Seki Positions
Firstly consider the following three problems:
The questions are the same: Is the game over?
A seki position will be called complete if any move
by either player leads to some loss for him. What
kinds of complete seki exist? For example two
eyeless groups and two dame between them (dia. 1);
or two one-eyed groups and one dame between them
(dia. 2); or one eyeless White group, two one-eyed
Black groups, and two dame (dia. 3). Something else?
Using one's imaginaion, more abstract examples can be
constructed. Such as a ring of arbitrary size,
consisting of alternating eyeless Black and White
groups, with one dame between each pair of
neighbouring groups. Another example can be obtained
by breaking up this ring, and substituting the end
groups by one-eyed ones.
In this paper we consider some examples, some hypotheses,
and results connected with a classification of complete
seki. It is natural to classify them according to
the number of groups and the number of dame between them.
We first consider the case of eyeless groups.
Let us define the seki-matrix. Its rows correspond to
Black groups, and its columns correspond to White groups.
At the intersection of a row and a column we put the
number of dame between the corresponding groups. See the
diagrams for examples.
We now have a new game using matrices with integer
non-negative elements. The players (Black and White)
move in turn. A "move" consists of subtracting 1 from
any positive element. Black wins if, after his move, a
column of zeroes appears. Similarly, White wins if,
after his move, a row of zeroes appears. If both a zero-
column, and a zero-row, appear simultaneously after a
move, the player of that move wins.
This game will be called "Nil".
The analogy with Go is clear. A move in Nil corresponds
to a move in Go where a stone is put on a dame. A
zero-row corresponds to a captured Black group and a
zero-column corresponds to a captured White group. A
matrix in Nil such that any move by either player leads
to a loss for them corresponds to a complete seki.
However exclusions [? exceptions] are possible, as we
shall see later. Such matrices will be called seki
matrices.
The 1x1 matrix M0 = (2) gives the simplest example (see
dia. 1). There exists no 2x1 seki matrix. This means
that three eyeless groups can't form a seki. There are
four 2x2 seki matrices:
M1 = (1 1), M2 = (1 2), M3 = (2 2), M4 = (2 0)
(1 1) (2 1) (2 2) (0 2)
The sekis corresponding to M1, M2, and M3 are shown in
dias. 4, 5, and 6.
Note that the matrix M2' given by:
M2' = (2 1)
(1 2)
corresponds to the same seki situation as M2. Generally
we will not distinguish between matrices which differ
only by a permutation of rows or columns. Note also
that the matrix M4 corresponds to two independent copies
of the matrix of type M0 (dia. 1). More generally, any
matrix that can be transformed to the block-diagonal
form (see dia. 7) by permutation of the rows and columns
actually corresponds to some set of independent positions
in Go. Such matrices will be called disconnected. We
will consider connected matrices only.
The matrix:
M5 = (3 2)
(2 3)
is already not a seki-matrix. Really the corresponding
seki in Go can be completed -- see dia. 8.
Let us state some results and hypotheses concerning
eyeless sekis.
Hypothesis 1: All seki-matrices are even-sum-squares
-- that is the number of rows is equal to the number of
columns, and the sum of every row and every column is a
constant. This sum will be called the index of an
even-sum-square. In the language of Go an index is the
number of dame, provided this number is the same for all
groups involved.
Theorem: If the matrix is an even-sum-square, and its
index equals 2, 3, or 4 then the player who moves first
can't win in Nil. In other words, the corresponding
positions in Go are sekis (complete or incomplete).
However the theorem is not valid for indices greater
than 4 -- see the example in dia. 9 -- all the groups
there have 5 dame, but if Black plays first he captures
all the White stones.
Hypothesis 2: For any positive integer "n", there
exists only a finite number of nxn seki-matrices.
The game "Nil" can easily be changed so as to describe
sekis which include one-eyed groups. For this purpose,
let us add to the matrix one special column (consisting
of zeros and ones) indicating the number of eyes of the
Black groups. Similarly, add a special row indicating
the number of eyes of the White groups. Now Black
(White) has first to obtain a zero column (row), and
then possibly play one extra move to remove the eye
(if there is one).
Examples are given in dias. 2 and 3. Note that for both
of them, the analogy to Hypothesis 1 is valid -- that is
the sum in all the rows and columns (excluding the
additional special ones) is a constant. However there
are examples which contradict this hypothesis -- see
dias. 10 and 11.
Until now, in our study of sekis, we have assumed that
if a player loses one of his groups then he loses.
However there are positions in Go which contradict this
seemingly natural statement. Consider, for example,
dia. 12. The matrix shown there is not a seki-matrix
-- actually White can capture the Black group in the
upper right corner with 2 moves, however this manouevre
in a net loss for White since he loses the larger White
group in the lower left corner. Therefore the position
in dia. 12 is a complete seki.
Now consider another example -- dia. 13. The matrix
shown there is a seki matrix. One can easily prove that
the player who moves first loses the Nil game. This
means literally that the player who moves first in
the game of Go is the first one to lose a group.
However, both Black and White profit by sacrificing
one of their groups, because after that it is then
possible to capture the more important opponent's
group. Therefore this position is not complete.
If Black moves first he wins by 2 points; if White
moves first the game ends in Jigo.
These examples show that an exchange of groups is
possible in seki-type positions. If lots of exchanges
are possible, it may be rather difficult to decide whether
a position is complete -- see, for example, dia. 14.
To reduce the dimension of dia. 14, we dared to consider
Go fields without the centre point. Why not? One may
play Go on an arbitrary graph and the problems considered
here will be the same.
Moscow 25-3-1981