Z = number of zeros (tails)
Two players alternate placing X's on a rectangular grid. No two X's may appear adjacent along a side or across the diagonal at a corner. The last X wins.
Some theory: The "indicator" for a position is: make all possible moves from the given position.
Evaluate the indicator of each of these successor positions.
The indicator of the first position is the smallest number which is not the indicator of a successor position. The indicator of the null position is 0. The second player wins iff the indicator is 0. Example of calculating an indicator for the 3 x 3 board: There are 3 distinct moves possible -- corner, side, center. Playing in the center leaves the null position, indicator 0. Playing on the side leaves a 1 x 3 line, indicator 2. Playing in the corner leaves a 3 x 3 L, indicator 3. The smallest number not appearing in our list is 1, so the indicator of a 3 x 3 square is 1. For two boards (not touching) played simultaneously, the indicator is the XOR of the indicators for the separate boards. For any position, the indicator is <= the maximum game length.
PROBLEM: Find some non-exponential way to compute the indicator of a given position. For lines, a period of 34 is entered after the line is about 80 long. For Ls: if one leg is held fixed, the indicator (as a function of the other leg) seems to become periodic with period 34. The time to enter the period becomes greater as the fixed leg increases.
white: pawns at QN3 and KN7, knight at QN4, bishop at KB7, king at QB2;
black: pawn at QN3, king at QR6. White mates in three moves.
PROBLEM: 6 dots is minimum to ensure no stalemate with 2 players; how many dots are required with 3 players?
A B C D E F G H I J K L M N P Q . S T U V W X Y Z 1 2 3 4 5 6 7 8From the starting position, complement the board. This is the ending position. Now from the starting position, make one move, then complement the board. This is a position one move from a win. By induction, you can win from the complement of any position you can reach. Thus every successful game has a dual game whose positions are the complements of the original ones. This debunks the heuristic of emptying the arms of the plus first and then cleaning up the middle, because there are just as many dual games which empty out the middle first and then the arms! The program found one counterintuitive win which at one point left the center nine empty but had ten in the arms.
. B . D E . . . . . . . . . P . . . T U V W . . . . . . 4 . . 7 .By dualizing and permuting a solution from the folklore, we found a similar winning position with 20. (T Q 4 R 1 L J H W Y M J) leaves:
A B C D E F G H . . . L . N . . . . . U V W . . . 1 2 3 . 5 6 7 8then (8 V A C/B 2 6 G M F/K S 8 1 Y V 3 Q A H E).
Another useful observation is that the pegs and their original hole
positions fall into four equivalence classes in which they stay
throughout the game. Thus the four pegs which can reach the center on
the first move are the only ones that ever can. Similarly, the peg
jumped over on the last move must be in one of the two classes of
eight members which get reduced on the first move. The program's main
heuristic was to reduce the larger classes first.
a b a
c d c
a b a b a b a
c d c . c d c
a b a b a b a
c d c
a b a
With its heuristics disabled, the program simply scanned
lexicographically (left to right in the inner loop, then top to
bottom) for a peg which could move. At one point, there is a peg
which can move two ways; it chose west. Twelve moves from the end it
stopped and went into an exhaustive tree search, in which it found two
basically different wins. (Try it yourself.)
. . .
. . .
. . . . K . .
. . Q . . . .
. . X Y Z 1 2
3 4 5
6 7 8
REMOVE CAN END WITH ONLY THE PEG 1 1, 7 = 10, 13 2 2, 6, 11, 14 4 3 = 12, 4, 9, 15 5 13Removing only one, no way exists to get to either 1 + 11 + 15 (tips) or 4 + 6 + 13 (centers of sides). Starting with peg 1 removed, 3,016 positions are attainable (not turning board); the sum of ways to get to each of these is 10,306. An example is: remove peg 1, then jump as follows: 6, 13, 10, 1, 2, 11, 14/13, 6, 12/13, 15, 7/4, 13, 4; leaving peg 1.