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 (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. T ...

, 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 pop ...

on a square grid of varying size, rather than being limited to "in a row" constructions. 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, and is a broader definition than that of an

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

. Harary's generalization does not include tic-tac-toe itself, as diagonal constructions are not considered a win. Like many other two-player games, strategy stealing means that the second player can never win. All that is left to study is to determine whether the first player can win, on what board sizes he may do so, and in how many moves it will take.

Results

Square boards

Let ''b'' be the smallest size square board on which the first player can win, and let ''m'' be the smallest number of moves in which the first player can force a win, assuming perfect play by both sides. *

monomino 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 pop ...

: ''b'' = 1, ''m'' = 1 *

domino Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. 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 ca ...

: ''b'' = 2, ''m'' = 2 *straight

tromino A tromino or triomino is a polyomino of order 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 ...

: ''b'' = 4, ''m'' = 3 *L-tromino: ''b'' = 3, ''m'' = 3 *square-

tetromino A tetromino is a geometric shape composed of four squares, connected orthogonally (i.e. at the edges and not the corners). Tetrominoes, like dominoes and pentominoes, are a particular type of polyomino. The corresponding polycube, called a tetracu ...

: The first player cannot win *straight-tetromino: ''b'' = 7, ''m'' = 8 *T-tetromino: ''b'' = 5, ''m'' = 4 *Z-tetromino: ''b'' = 3, ''m'' = 5 *L-tetromino: ''b'' = 4, ''m'' = 4

References

* * Gardner, Martin. ''The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems: Number Theory, Algebra, Geometry, Probability, Topology, Game Theory, Infinity, and Other Topics of Recreational Mathematics.'' 1st ed. New York: W. W. Norton & Company, 2001. 286-311. {{Tic-Tac-Toe Recreational mathematics Tic-tac-toe