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 l1-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 l2-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 l1-tree (with (n, d) = (1, 7)) is shown first, followed by the winning l2-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}