Seki in Go

Authors: Vladimir GURVICH, Andrey GOL'BERG

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 -- dias. 0, 1-3, dias. 4-9, dias. 10-12, and dias. 13, and 14 -- 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)

Note that the matrix M2' given by:

M2' = (2 1)
      (1 2)

The matrix:

M5 = (3 2)
     (2 3)

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.