TOPICS

# Tic-Tac-Toe

The game of tic-tac-toe, also spelled ticktacktoe and also known as 3-in-a-row or "naughts and crosses," is a game in which players alternate placing pieces (typically Xs for the first player and Os for the second) on a board. The first player to get three pieces in a row (vertically, horizontally, or diagonally) is the winner. For the usual board, a draw can always be obtained, making it a futile game.

Wolfram (2022) analyzes and tic-tac-toe as multicomputational processes, including through the use of branchial graphs.

A generalized -in-a-row on an board can also be considered, as can a generalization to a three-dimensional "board." The game consisting of getting five (or more) in a row on a board variously considered to be of size or is known as go-moku. The specific case of tic-tac-toe is known as qubic.

For 2-in-a-row on any board larger than , the first player has a trivial win. In "revenge" tic-tac-toe (in which -in-a-row wins, but loses if the opponent can make -in-a-row on the next move), even 2-in-a-row is non-trivial. For instance, on a board is won for the first player if he starts in the second or fourth square, but not if he starts elsewhere.

In 3-in-a-row, the first player wins for any board at least . The first player also wins on a board with an augmented corner square, with three distinct winning first moves (Gardner 1978).

If the board is at least , the first player can win for (the board is a draw). The game is believed to be a draw for , is undecided for , believed to be a proven win for , and has been proved as a win for by means of variation trees (Ma).

For , a draw can always be obtained on a board, but the first player can win if the board is at least . The cases and 7 have not yet been fully analyzed for an board, although draws can always be forced for and 9.

In higher dimensions, for any -in-a-row, there exists a dimension board () with a winning strategy for the first player (Hales and Jewett 1963). The Hales-Jewett theorem, a central result in Ramsey theory, even allows for more than two players, a dimension will still exist that gives a first player win. For and , the first player can always win (Gardner 1979), thus establishing for and . For , Golomb has proven with a Hales-Jewett pairing strategy (Ma 2005). Values of for other are unknown, and the Hales-Jewett theorem does not help, as it is existential and not constructive.

Board, Connect-Four, Connection Game, Gomoku, No-Three-in-a-Line-Problem, Pong Hau K'i, Qubic

## Explore with Wolfram|Alpha

More things to try:

## References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 103-104, 1987.Browne, C. Connection Games: Variations on a Theme. Wellesley, MA: A K Peters, p. 9, 2005.de Fouquières, B. Ch. 18 in Les jeux des anciens, 2nd ed. Paris: 1873.Gardner, M. "Ridiculous Questions." Ch. 10 in Mathematical Magic Show: More Puzzles, Games, Diversions, Illusions and Other Mathematical Sleight-of-Mind from Scientific American. New York: Vintage, pp. 138-142, 1978.Gardner, M. "Mathematical Games: The Diverse Pleasures of Circles That Are Tangent to One Another." Sci. Amer. 240, 18-28, Jan. 1979.Gardner, M. "Ticktacktoe Games." Ch. 9 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 94-105, 1983.Hales, A. W. and Jewett, R. I. "Regularity and Positional Games." Trans. Amer. Math. Soc. 106, 222-229, 1963.Ma, W. J. "Generalized Tic-Tac-Toe." http://www.klab.caltech.edu/~ma/tictactoe.html.Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 10-11, 1999.Stewart, I. "A Shepherd Takes A Sheep Shot." Sci. Amer. 269, 154-156, 1993.Wolfram, S. "Games and Puzzles as Multicomputational Systems." Jun. 8, 2022. https://writings.stephenwolfram.com/2022/06/games-and-puzzles-as-multicomputational-systems/.

Tic-Tac-Toe

## Cite this as:

Weisstein, Eric W. "Tic-Tac-Toe." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Tic-Tac-Toe.html