**Explanation of
Java-output**

First (case 1) the
program analyzes a 4x4 board with attacker's stones (black) in
three of the four corners, the objective being to get four stones
in a row horizontally, vertically or diagonally. After this, the
program analyzes tic-tac-toe (case 2), verifying that it is a
draw. The program produces (*n*, *d*)-tables by
analyzing each combination of *n* and *d*, and not
stopping if a solution is found.

How to search such
a table in a real application is a difficult question because it
is two-dimensional. Using a depth-first algorithm (like
alpha-beta) as the search engine, an idea could be to assume some
maximum value for *d*, and then first search *n* =
1 for *d *= 3, *d* = 5, *d* = 7, and so on
up to the depth limit. If this does not yield a solution, *n*
= 2 is tried, for *d *= 5, *d* = 7, *d* = 9,
and so on. This continues for higher and higher *n*,
searching the table column-wise top-down, until a solution is
found or time runs out (equivalent to using iterative-deepening
alpha-beta for *n* = 1, *n* = 2, and so on).

**Case 1: 4-in-a-row on a 4x4 board**

The starting position (attacker = #, defender = O):

Position to analyze, with # (attacker) moving first: . . . # . . . . . . . . # . . #

As it is seen in
the table below (taken from the output of the large version of
the Java-code), an attacker's win for *n* = 1 (direct
threat-sequence) is found at depth *d* = 11, at the cost
of generating 324 positions.

n=1 n=2 n=3 n=4 n=5 n=6 d=3: 0.5 {459} d=5: 0.5 {1879} 0.5 {10119} d=7: 0.5 {5123} 1.0 {58522} 1.0 {58522} d=9: 0.5 {10995} 1.0 {19055} 1.0 {19055} 1.0 {19055} d=11: 1.0 {324} 1.0 {324} 1.0 {324} 1.0 {324} 1.0 {324} d=13: 1.0 {386} 1.0 {386} 1.0 {386} 1.0 {386} 1.0 {386} 1.0 {386}

The winning
sequence for *n* = 1 runs as follows:

n=1 d=10 dMax=11 moveColor=-1 1 . . . # . . . . . . . . # # . # n=1 d=9 dMax=11 moveColor=1 1 1 . . . # . . . . . . . . # # O # n=1 d=8 dMax=11 moveColor=-1 1 1 1 . . . # . . . . . # . . # # O # n=1 d=7 dMax=11 moveColor=1 1 1 1 1 . . . # . . O . . # . . # # O # n=1 d=6 dMax=11 moveColor=-1 1 1 1 1 1 . . . # . . O . . # . # # # O # n=1 d=5 dMax=11 moveColor=1 1 1 1 1 1 1 . . . # . . O O . # . # # # O # n=1 d=4 dMax=11 moveColor=-1 1 1 1 1 1 1 2 . . . # . . O O . # # # # # O # n=1 d=3 dMax=11 moveColor=1 1 1 1 1 1 1 2 1 . . . # . . O O O # # # # # O # n=1 d=2 dMax=11 moveColor=-1 1 1 1 1 1 1 2 1 1 . . . # . # O O O # # # # # O #

After this the defender has no l^{1}-moves. This is not the shortest win,
however, because a l-search to order *n* = 2 can find a win in 7
plies only, at the cost of 58522 generated positions. This
sequence runs as follows:

n=2 d=6 dMax=7 moveColor=-1 5 . . . # . . . . . . # . # . . # n=2 d=5 dMax=7 moveColor=1 5 2 . . . # . . O . . . # . # . . # n=2 d=4 dMax=7 moveColor=-1 5 2 3 . . . # . . O . # . # . # . . #

After this the defender has no l^{2}-moves. This means that no matter where he
plays, the attacker can follow up with a winning direct
threat-sequence (within the depth limit of 7 plies).

a . . # . . O . # . # b # . . #

For instance, if the defender plays *a*,
black plays *b*, and vice versa. For reference, standard
alpha-beta search is shown below, also finding the win in 7 plies
(at the cost of 28757 generated positions). In the output, this
special case (*n*,* d*) = (2, 7) is shown. [Note
that in the output, the failing l^{1}-tree (with (*n*,* d*) = (1, 7)) is shown
first, followed by the winning l^{2}-tree.]

ALPHABETA d=0: 0.5 {0} ALPHABETA d=1: 0.5 {13} ALPHABETA d=2: 0.5 {26} ALPHABETA d=3: 0.5 {339} ALPHABETA d=4: 0.5 {606} ALPHABETA d=5: 0.5 {5001} ALPHABETA d=6: 0.5 {8452} ALPHABETA d=7: 1.0 {28757} ALPHABETA d=8: 1.0 {46699} ALPHABETA d=9: 1.0 {4489} ALPHABETA d=10: 1.0 {6501} ALPHABETA d=11: 1.0 {14879} ALPHABETA d=12: 1.0 {19933} ALPHABETA d=13: 1.0 {27360}

**Case 2: 3-in-a-row on a 3x3 board**

In addition, tic-tac-toe is also analyzed. The starting position (attacker = #, defender = O)::

Position to analyze, with # (attacker) moving first: . . . . . . . . .

As the table shows, no attacker's win can be fount:

n=1 n=2 n=3 n=4 n=5 n=6 d=3: 0.0 {90} d=5: 0.0 {90} 0.5 {2107} d=7: 0.0 {90} 0.5 {18814} 0.5 {55634} d=9: 0.0 {90} 0.5 {33755} 0.5 {115385} 0.5 {272692}

In the above table, it should be noted that for
*n* = 1, the algorithm returns value 0 (not value 0.5),
looking at 90 positions. This means that already at depth *d*
= 3, it is disproved that the attacker's goal can be obtained at l-order *n* = 1 (in a
direct threat-sequence). Hence, searching deeper for *n* =
1 is meaningless. In contrast, no disproofs are found for the
larger l-order
searches. In the small version of the code, disproofs are not
handled in this more elaborate way, so in the small version of
the code the above table is full of zeroes (however, a one is
always a one in both versions of the code).

Standard alpha-beta is shown for reference (not finding any win, either):

ALPHABETA d=0: 0.5 {0} ALPHABETA d=1: 0.5 {9} ALPHABETA d=2: 0.5 {18} ALPHABETA d=3: 0.5 {81} ALPHABETA d=4: 0.5 {144} ALPHABETA d=5: 0.5 {905} ALPHABETA d=6: 0.5 {1476} ALPHABETA d=7: 0.5 {7929} ALPHABETA d=8: 0.5 {10876} ALPHABETA d=9: 0.5 {16158}