Harary's generalized tic-tac-toe


Harary's generalized tic-tac-toe or animal tic-tac-toe is a generalization of the game tic-tac-toe, defining the game as a race to complete a particular polyomino on a grid of squares. It was devised by Frank Harary in March 1977.
Harary tic-tac-toe is similar to the m,n,k-games, of which tic-tac-toe and Gomoku are examples; but in tic-tac-toe the first player is trying to complete either an I-tromino or a diagonal line of three corner-connected squares, whereas in Harary's game there is only a single polyomino involved.

Categorization of polyominoes by properties of their games

Each polyomino corresponds to a generalized tic-tac-toe game: for example, the I-tromino corresponds to the game in which Player 1 is trying to form an I-tromino and Player 2 is trying to stop him. Harary defines the unqualified terms "winner" and "loser": A polyomino is a "winner" if Player 1 wins its game, and a "loser" if Player 2 can always prevent Player 1 from winning.
Harary generalizes over various restrictions of the board; for example, the V-tromino is a loser on the 2x2 board but a winner on the 3x3 board. Other mathematicians have generalized over a Go-style "handicap": A game with "handicap k" is a game in which Player 1 is allowed to place k of his own marks on the board before his first move. So, for example, the V-tromino is a winner with handicap 1 even on the 2x2 board.
Harary defines a polyomino of k cells to be an "economical winner" if it wins in exactly k moves; that is, if every one of Player 1's marks forms part of the finished animal. This may depend on the board size: for example, the Z-tetromino is a non-economical winner on the 3x3 board, but an economical winner on the 5x5 board.
The game has also been generalized to higher dimensions: for example, Player 1 may be trying to form a particular polycube on a 3D grid while Player 2 tries to stop him. The 2x2 square tetromino is a 2D loser, but a 3D winner. Every polyomino is a winner in high enough dimension.

Strategies for Player 2

Every known "loser" succumbs to a simple strategy from Player 2, known as the "paving strategy." For example, consider the game in which Player 1 is trying to form the square tetromino and Player 2 is trying to stop him. Player 2 imagines that the infinite grid has been partitioned into domino tiles arranged like a wall of bricks. Each time Player 1 puts his mark in one cell of a domino, Player 2 responds by putting his own mark in the other cell of that same domino. This prevents Player 1 from ever completing any domino that is part of Player 2's paving. It is impossible to place a square tetromino without including the whole of some domino from Player 2's paving; therefore Player 1 can never win.
A polyomino that succumbs to any such domino-paving strategy is called a "paving loser." Every known loser is a paving loser, although different animals require different pavings. Five different pavings suffice to defeat all known losers.
The "Snaky" hexomino, on the other hand, is a paving winner: it does not succumb to any paving strategy. In fact, it is a pair-partition winner: it does not succumb to any strategy that involves Player 2's partitioning the grid into pairs of cells, regardless of adjacency.

Known winners, and Snaky

Harary calls a loser a "basic loser" if it contains no smaller loser. For example, the square tetromino is a basic loser. The P-pentomino is a loser but not a basic loser, because it contains within itself the square tetromino. There are twelve known basic losers.
All heptominoes are known to be losers, which means that all higher-order polyominoes are necessarily losers.
All hexominoes are known to be losers, except for the one that Harary nicknames "Snaky," which consists of a domino joined to an I-tetromino.
This leaves eleven polyominoes which are known to be winners.
If Snaky is a winner, then there exist 12 winners and 12 basic losers; if Snaky is a loser, then there exist 11 winners and 13 basic losers.
The following table gives those eleven winners along with the values of two derived variables that Harary termed and.
The value is what Harary calls the "board number" of the game: the side length of the smallest square board on which Player 1 can force a win with perfect play. is the "move number": the smallest number of moves in which Player 1 can force a win on a board of size. Vice versa, Berlekamp et al. compute and. Their value is the smallest number of moves in which Player 1 can force a win on an infinitely large board, and is the side length of the smallest square board on which Player 1 can win in moves with perfect play.
The definition of m and b is also affected by whether the game is assumed to be played as a maker-maker game or as a maker-breaker game. In a maker-breaker game, the first player's sole goal is to make their pattern, and the second player wins only by preventing that outcome. In a maker-maker game, the second player can alternatively win by making the pattern first; this means that the first player must sometimes spend additional moves to "block a threat" from the second player, which increases m and perhaps even b. Since Harary tic-tac-toe generalizes ordinary tic-tac-toe — a maker-maker game — the m and b values below presumably should pertain to the maker-maker game. However, the maker-maker game is "quite challenging" to analyze, compared to the more tractable maker-breaker game.
The and values in the following table are from Berlekamp et al. unless otherwise indicated.
The and values are from Gardner unless otherwise indicated.
Shapeb1m1b2m2
monomino1111
domino2222
I-tromino4343
V-tromino3333
I-tetromino7878
L-tetromino4444
T-tetromino5454
Z-tetromino5435
L-pentomino777 10
N-pentomino6666
Y-pentomino767 9

Harary has conjectured that Snaky is a winner with about 15 and about 13.
Snaky is proved to be a pair-partition winner, but it is an open question whether it might lose via some non-partition-based strategy. Snaky is a loser on any board 8x8 or smaller. Snaky is a winner in 2 dimensions with handicap 1; therefore it is a winner in 3 dimensions with handicap zero.

Other generalizations

Harary divided tic-tac-toe-like games into what he called "achievement games" and "avoidance games". The avoidance game is the misère form of the achievement game.
Harary's "animal tic-tac-toe" considered only the "animals" corresponding to polyominoes. The game could also be played with so-called "wild animals" — sets of squares which are merely corner-connected — or even with arbitrary non-contiguous shapes. Harary's game considers the free polyominoes ; the game could be played with one-sided polyominoes instead.
A common variation is to permit Player 2 to place two marks per turn; this changes the game from what Harary called a "-achievement game" to a "-achievement game." The strategy-stealing argument that applies in the -achievement game does not apply in the -achievement game. The -achievement game may be played as a "strong" achievement game, in which Player 2 wins instantly if he forms the target shape before Player 1; or as a "weak" achievement game, in which Player 2's goal is merely to prevent Player 1 from winning. For example, the game Connect6 is a strong -achievement game, with a handicap of -1.
Another generalization would be to have Player 1 try to achieve one particular animal while Player 2 tries to achieve a different one: for example, Player 1 tries to achieve the I-tetromino before Player 2 achieves the I-tromino.