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 (Harary called them "animals") 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 (a horizontal or vertical line of three squares) ''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. (Note that it is impossible for Player 2 to form an I-tromino before Player 1 does: the strategy-stealing argument applies.) Harary defines the unqualified terms "winner" and "loser": A polyomino is a "winner" if Player 1 wins its game (assuming perfect play from both sides), 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. (The unqualified terms "winner" and "loser" always refer to the game on an infinite 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 ("paved with") 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 (see below), 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 (possibly non-contiguous) ''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 (in 2D, on an infinite grid, with no handicap).
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 $b$ and $m$. (For clarity, we follow Thompson (1996) in distinguishing $m_1$ and $b_1$ from $b_2$ and $m_2$.)

The value $b_2$ 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. $m_2$ is the "move number": the smallest number of moves in which Player 1 can force a win on a board of size $b_2$. Vice versa, Berlekamp et al. (1982) compute $m_1$ and $b_1$. Their value $m_1$ is the smallest number of moves in which Player 1 can force a win on an infinitely large board, and $b_1$ is the side length of the smallest square board on which Player 1 can win in $m_1$ 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 (like ordinary tic-tac-toe) or as a maker-breaker game. In a maker-breaker game (or ''weak'' achievement 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 (or ''strong'' achievement 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 $m_1$ and $b_1$ values in the following table are from Berlekamp et al. (2003) unless otherwise indicated.
The $m_2$ and $b_2$ values are from Gardner (2001) unless otherwise indicated.

Harary has conjectured that Snaky is a winner with $b_2$ about 15 (certainly $b > 8$) and $m_2$ 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 (on an infinite board) 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" (where the goal is to form a particular pattern) and "avoidance games" (where the goal is to ''avoid'' forming a particular pattern; or, equivalently, to force your opponent to form that pattern first). The avoidance game is the misère form of the achievement game.

Harary's "animal tic-tac-toe" considered only the "animals" corresponding to (edge-connected) 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 (where for example both forms of the L-tetromino are permitted); the game could be played with one-sided polyominoes instead (such that if Player 1 is trying to form a left-handed L, forming the right-handed L would not count as a victory).

A common variation is to permit Player 2 to place ''two'' marks per turn; this changes the game from what Harary called a "(1,1)-achievement game" to a "(1,2)-achievement game." The strategy-stealing argument that applies in the $(k,k)$-achievement game does not apply in the $(k,\ell)$-achievement game. The (1,2)-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 (in which both players attempt to form a row of six stones, placing two per turn) is a strong (2,2)-achievement game, with a handicap of -1 (that is, Player 1 places only one stone on his first turn).

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.

References

*
*Numberphile. ''The Snakey Hexomino (unsolved Tic-Tac-Toe problem)'

{{Tic-Tac-Toe

Mathematical games
Tic-tac-toe