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
x
x
2) x..xA.xo
x
x
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
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:
xx
x32x
x41x
xx
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
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.