HOME

TheInfoList



OR:

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 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 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 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 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