Harary's generalized tic-tac-toe or animal tic-tac-toe is a generalization of the game
tic-tac-toe
Tic-tac-toe (American English), noughts and crosses (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...
, defining the game as a race to complete a particular
polyomino
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.
Polyominoes have been used in popu ...
(Harary called them "animals") on a grid of squares. It was devised by
Frank Harary
Frank Harary (March 11, 1921 – January 4, 2005) was an American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory.
Harary was a master of clear exposition and, together with ...
in March 1977.
Harary tic-tac-toe is similar to the
m,n,k-game
An ''m'',''n'',''k''-game is an abstract board game in which two players take turns in placing a stone of their color on an ''m''-by-''n'' board, the winner being the player who first gets ''k'' stones of their own color in a row, horizontally, ...
s, of which
tic-tac-toe
Tic-tac-toe (American English), noughts and crosses (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...
and
Gomoku
''Gomoku'', also called ''five in a row'', is an Abstract strategy game, abstract strategy board game. It is traditionally played with Go (game), Go pieces (black and white stones) on a 15×15 Go board while in the past a 19×19 board was standa ...
are examples; but in tic-tac-toe the first player is trying to complete ''either'' an I-
tromino
A tromino or triomino is a polyomino of size 3, that is, a polygon in the plane made of three equal-sized squares connected edge-to-edge.
Symmetry and enumeration
When rotations and reflections are not considered to be distinct shapes, there a ...
(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
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coordi ...
: for example, Player 1 may be trying to form a particular
polycube
image:tetracube_categories.svg, upAll 8 one-sided tetracubes – if chirality is ignored, the bottom 2 in grey are considered the same, giving 7 free tetracubes in total
image:9L cube puzzle solution.svg, A puzzle involving arranging nine L tricube ...
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
Dominoes is a family of tile-based games played with gaming pieces. Each domino is a rectangular tile, usually with a line dividing its face into two square ''ends''. Each end is marked with a number of spots (also called '' pips'' or ''dots'' ...
tiles arranged like a wall of
brick
A brick is a type of construction material used to build walls, pavements and other elements in masonry construction. Properly, the term ''brick'' denotes a unit primarily composed of clay. But is now also used informally to denote building un ...
s. 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
and
. (For clarity, we follow Thompson (1996)
in distinguishing
and
from
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. (1982)
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 (like ordinary
tic-tac-toe
Tic-tac-toe (American English), noughts and crosses (English in the Commonwealth of Nations, Commonwealth English), or Xs and Os (Canadian English, Canadian or Hiberno-English, Irish English) is a paper-and-pencil game for two players who ta ...
) 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
and
values in the following table are from Berlekamp et al. (2003)
unless otherwise indicated.
The
and
values are from Gardner (2001)
unless otherwise indicated.
Harary has conjectured
that Snaky is a winner with
about 15 (certainly
) 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 (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
-achievement game does not apply in the
-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
Connect6 (; Pinyin: liùzǐqí; ;; ) introduced in 2003 by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University in Taiwan, is a two-player strategy game similar to Gomoku.
Two player ...
(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
''Numberphile'' is an Educational entertainment, educational YouTube channel featuring videos that explore topics from a variety of fields of mathematics. In the early days of the channel, each video focused on a specific number, but the channe ...
. ''The Snakey Hexomino (unsolved Tic-Tac-Toe problem)'
{{Tic-Tac-Toe
Mathematical games
Tic-tac-toe