# Letter from Gurvich and Gol'berg to Heine

Dear Professor Heine

Your book "2nd 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 (page 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 ). 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 ) 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 (): 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, and dias. 8-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 . 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 played "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  (see , 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 sacrifice 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  ( dias 11-12, and dia 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
Transcription by Harry Fearnley (HF) of a letter from Vladimir Gurvich and Andrey Gol'berg to Prof Klaus Heine -- from a poor quality photocopy. The in-line diagrams have been drawn again by HF, but the originals are still supplied via links.