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.^[1]

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.

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.^[2] 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.^[3] Every polyomino is a winner in high enough dimension.^[3]

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,^[4] although different animals require different pavings. Five different pavings suffice to defeat all known losers.^[2]

The "Snaky" hexomino (see below), on the other hand, is a paving winner:^[4] 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.^[4]

Harary calls a loser a "basic loser" if it contains no smaller loser. For example, the square tetromino is a basic loser.^[2] 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.^[1]

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.^[2] 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.^[1]

The following table gives those eleven winners along with the values of two derived variables that Harary termed ${\displaystyle b}$ and ${\displaystyle m}$. (For clarity, we follow Thompson (1996)^[5] in distinguishing ${\displaystyle m_{1}}$ and ${\displaystyle b_{1}}$ from ${\displaystyle b_{2}}$ and ${\displaystyle m_{2}}$.)

The value ${\displaystyle b_{2}}$ is what Harary calls^[1] 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. ${\displaystyle m_{2}}$ is the "move number": the smallest number of moves in which Player 1 can force a win on a board of size ${\displaystyle b_{2}}$.^[5][1] Vice versa, Berlekamp et al. (1982)^[6][7] compute ${\displaystyle m_{1}}$ and ${\displaystyle b_{1}}$. Their value ${\displaystyle m_{1}}$ is the smallest number of moves in which Player 1 can force a win on an infinitely large board, and ${\displaystyle b_{1}}$ is the side length of the smallest square board on which Player 1 can win in ${\displaystyle m_{1}}$ moves with perfect play.^[5]

The ${\displaystyle m_{1}}$ and ${\displaystyle b_{1}}$ values in the following table are from Berlekamp et al. (2003)^[7] unless otherwise indicated. The ${\displaystyle m_{2}}$ and ${\displaystyle b_{2}}$ values are from Gardner (2001)^[1] unless otherwise indicated.

Harary has conjectured^[1] that Snaky is a winner with ${\displaystyle b_{2}}$ about 15 (certainly ${\displaystyle b>8}$^[9]) and ${\displaystyle m_{2}}$ about 13.

Snaky is proved to be a pair-partition winner,^[4] 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.^[9] Snaky is a winner (on an infinite board^{[clarification needed]}) in 2 dimensions with handicap 1;^[10] therefore it is a winner in 3 dimensions with handicap zero.^[9]

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).^[2] 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"^[11] — 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."^[11] The strategy-stealing argument that applies in the ${\displaystyle (k,k)}$-achievement game does not apply in the ${\displaystyle (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.^[11] 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.^{[example needed]}

• Beck, József (2008), "Harary's Animal Tic-Tac-Toe", Combinatorial Games: Tic-Tac-Toe Theory, Encyclopedia of Mathematics and its Applications, vol. 114, Cambridge: Cambridge University Press, pp. 60–64, doi:10.1017/CBO9780511735202, ISBN 978-0-521-46100-9, MR 2402857
• Numberphile. The Snakey Hexomino (unsolved Tic-Tac-Toe problem) [1]