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

Shape	b₁	m₁	b₂	m₂
class="wikitable"
monomino	1	1	1	1
domino	2	2	2	2
I-tromino	4	3	4	3
V-tromino	3	3	3	3
I-tetromino	7	6	7 (6)	8
L-tetromino	4	4	4	4
T-tetromino	5	4	5	4
Z-tetromino	5?Winning Ways{{'}} table incorrectly lists the Z-tetromino with (b=3,m=5). The Z-tetromino is a winner (with $m_2=5$ ) on the 3x3 board, but it is an economical winner (with $m_1=4$ ) on the 5x5 board.	4	3	5
L-pentomino	7	7	7 (6)	10 (9)
N-pentomino	6	6	6	6
Y-pentomino	7	6	7 (6)	9

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{{huh|date=April 2025|reason=we should be able to compute at least an upper bound on the board number b; what is that upper bound and why?}}) 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.{{better example needed|date=April 2025}}

References

{{cite book |title=Winning Ways for Your Mathematical Plays |author1=Elwyn Berlekamp |author2=John Conway |author3=Richard Guy |edition=1st |publisher=Academic Press |year=1982 |volume=2 |pages=684–685 |isbn=978-0-12-091150-9 |url=https://archive.org/details/winningwaysforyo02berl/page/684/mode/2up}}

{{cite book |title=Winning Ways for Your Mathematical Plays |author1=Elwyn Berlekamp |author2=John Conway |author3=Richard Guy |edition=2nd |publisher=A. K. Peters |year=2003 |volume=3 |pages=748–749 |url=https://bobson.ludost.net/copycrime/Winning%20Ways%202nd%20Edition/Winning.Ways.for.Your.Mathematical.Plays.V3--1568811438.pdf}}

{{cite journal |author=Martin Gardner |title=In which players of ticktacktoe are taught to hunt bigger game |journal=Scientific American |series=Mathematical Games |date=April 1979 |volume=240 |number=4 |pages=18–36 |jstor=24965167 |url=https://www.jstor.org/stable/24965167}}

{{cite book |author=Martin Gardner |chapter=Harary's Generalized Ticktacktoe |title=The Colossal Book of Mathematics |edition=1st |publisher=W. W. Norton |year=2001 |isbn=0-393-02023-1 |pages=493–503 |chapter-url=https://archive.org/details/martingardnerthecolossalbookofmathematics/page/n509}}

{{cite journal |title=Achieving Snaky |author1=Immanuel Halupczok |author2=Jan-Christoph Schlage-Puchta |journal=Electronic Journal of Combinatorial Number Theory |volume=7 |year=2007 |url=https://www.aur.uni-rostock.de/storages/uni-rostock/Alle_MNF/Mathematik/Struktur/Lehrstuehle/Algebra/papers/snaky.alleszusammen.pdf}}

{{cite journal |title=Snaky is a Paving Winner |author1=Heiko Harborth |author2=Markus Seemann |journal=Bulletin of the Institute of Combinatorics and its Applications |volume=19 |year=1997 |pages=71–78 |url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=1f81e6d3d43e1c24d76f508357593f6eebbbb74a}}

{{cite journal |author1=Hiro Ito |author2=Hiromitsu Miyagawa |title=Snaky is a winner with one handicap |year=2007 |journal=8th Hellenic European Conference on Computer Mathematics and Its Applications}}

{{cite journal |author=Nándor Sieben |title=Snaky is a 41-dimensional winner |journal=Integers |volume=4 |year=2004 |issn=1867-0652 |url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=11c3efc72587d3feb238bd6875abb3e4906bc0eb}}

{{cite journal |author=Nándor Sieben |title=Wild Polyomino Weak (1,2)-Achievement Games |journal=Geombinatorics |volume=13 |number=4 |year=2004 |pages=180–185 |url=https://jan.ucc.nau.edu/~ns46/research/achieve12.pdf}}

{{cite newsgroup |title=Harary's animal-achievement game - some questions |newsgroup=sci.math |author=Chris Thompson |date=1996-10-14 |url=https://ics.uci.edu/~eppstein/junkyard/animal-game.html |access-date=2025-04-22}}

{{citation

| last = Beck | first = József | authorlink = József Beck

| doi = 10.1017/CBO9780511735202

| location = Cambridge

| mr = 2402857

| publisher = Cambridge University Press

| series = Encyclopedia of Mathematics and its Applications

| title = Combinatorial Games: Tic-Tac-Toe Theory

| title-link = Combinatorial Games: Tic-Tac-Toe Theory

| volume = 114

| year = 2008

| contribution = Harary's Animal Tic-Tac-Toe

| pages = 60–64| isbn = 978-0-521-46100-9 }}

Numberphile. The Snakey Hexomino (unsolved Tic-Tac-Toe problem) [https://www.youtube.com/watch?v=ouTE-GYGIA8]

Category:Mathematical games

Category:Tic-tac-toe