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