RENJU THEORY

Artem Shaposhnikovs view on the programming of renju .

1. Types of linear threats and winning combinations.

Recognizing different types of linear threats is the first step in

understanding renju and Go-Moku rules.

Here we hope to give a strict mathematical definition of various

types of threats and fall. For the sake of clarity we shall discuss

threats of black stones. In the end of this section we shall speak of

differences of white stones threats in renju.

To be more general we shall take an endless board - a plane of

squares. Let's denote the state of each square S with W(s). At the

beginning of the game when the playing plane is empty, each square can

be in any of two states: N - an empty square and E - a square to which

neither of the players may move (e.g. if a square is out of the 15x15

bounds used in renju). The players in turn make moves to squares with

N states. The black move triggers the square state to U, the white

one - to T. Those U and T states remain unchanged through the play. We

shall call them opposite states.

Definition 1. A LINE of colour U and weight K - l,k,u we shall call

any group of 5 adjacent squares in a line (vertical, horizontal or

diagonal) having the following common properties:

1) a line has exactly K squares in U state,

2) a line contains no squares in either T or E states,

3) the ends of a line mustn't border on any U-state square. The

exception to this rule are T-colour lines in renju.

Definition 2. A ZERO-WEIGHT line is called any line which doesn't

satisfy points (2) and (3) of definition 1.

The first player, who will build an L5 line of his colour wins the

game. Now let's consider two lines of the same direction and common

squares.

Definition 3. We shall say that in square S in any direction there

is a threat of type Pk1 if in this direction this square is an

intersection of two unidirectional lines L1k and L2k which have

exactly 4-k common squares. (Type 1).

But if in this direction the square has only one threat Lk or any

two pairs of lines L1k and L2k have more (or less) than 4-k common

squares then we shall call such threat Pk2 (Type 2).

Therefore there exist the following types of threats:

Example

Evidently, during the game threats can alter:

P02 -> P12 -> P22 -> P32 or

P01 -> P11 -> P21 -> P31

A move to P31 threat will result in a win if the opponent has no

threats of P42 type, whereas a move to P32 gets no win.

We shall point out that:

P31 threat corresponds to the renju notion "unstopped 4",

P32 - stopped 4,

P22 - stopped 3.

Forks

An intersection of two threats of type P32 or P21 is called "a fork".

Evidently you can win only making a fork like P32 x P32, P21 x P21,

P32 x P21.

As an example let us look at two different P21 x P21 forks:

1) xxA

2) x..xA.xo

Even though the horizontal threat in (2) looks weak it's still a

P21 x P21 fork.

In renju forks of P21xP21 and P32xP32, P32xP21xP21 types are

prohibited for black (as well as an overline) - they result in a black

fall.

Besides, the definition of P21 threat for black undergoes some

changes: the crossing lines L21 and L22 must not only have exactly 2

common empty squares, but also be separated from each other exactly

with 1 square.

And still more - the square which is not the object of discussion,

should not be a fall. We shall make it clear by examples:

1) .xx1A

inter-line distance = 1

2) x

xx1 A

square 1 here is a fall, so the threat lies in square A - P22,

not P21.

So the definition of a fall as a intersection of two threats

P21xP32 and P21xP21 is recursive. The following riddle is noteworthy:

x32x

x41x

The question: is square 1 a fall or not? The square seems to be an

intersection of three threats but in fact there is only one diagonal

threat of P21 type, while horizontal and vertical ones are of type P22

due to falls in points 2 and 4. To prove it you must use a recursion

of depth 4.

2. Virtual threats.

It may seem logical that a move to a point, which accumulates

maximum of your own threats and those of your opponent is the most

necessary one. But it proves true only in 7 cases out of 10. In other

cases it may well happen that the best move is to a point with a

P01xP01 threat instead of P32xP32. The following example, where move 1

proves the best one,illustrates my point:

However, if you stop to take a closer look, you will see, that in

fact move 1 is a move to a P21xP21 fork. This fork is not a usual one

- it's "virtual". because it's components are not real stones but only

threats of certain moves! Besides, if all those threats are mutually

independent, the virtual fork is equivalent to the real one. But

virtual forks cannot be components of a fall.

Deepening the recursion, we shall find still more "virtual" and

elegant moves.

3. Spatial forks

It turns out, that not only threats P21 and P32 are valuable - P22

and P11 also are. Let's look at the following position:

o o

x x

1.2x

A (P22xP22)

P22xP22 threat in A makes a virtual threat in point (2).

As a result, point (1) has a horizontal threat of P21 type, because

move 2 can give a threat of victory on fours.

Concluding this paper we must point out that the author hasn't yet

succeeded to build a consistent theory of spatial forks and virtual

threats. But he managed to write a Vertex program, which very

effectively recognizes all types of linear threats, in 100% recognizes

all falls with an unlimited recursion, as well as some components of

virtual threats and spatial forks. The strength of the program is

about 1 Dan.