TOPICS
Search

Tic-Tac-Toe


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 3×3 board. The first player to get three pieces in a row (vertically, horizontally, or diagonally) is the winner. For the usual 3×3 board, a draw can always be obtained, making it a futile game.

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

A generalized n-in-a-row on an k×m 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 13×13 or 15×15 is known as go-moku. The specific case of 4×4×4 tic-tac-toe is known as qubic.

For 2-in-a-row on any board larger than 1×2, the first player has a trivial win. In "revenge" tic-tac-toe (in which n-in-a-row wins, but loses if the opponent can make n-in-a-row on the next move), even 2-in-a-row is non-trivial. For instance, n=2 on a 1×5 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 3×4. The first player also wins on a 3×3 board with an augmented corner square, with three distinct winning first moves (Gardner 1978).

If the board is at least 5×6, the first player can win for n=4 (the 5×5 board is a draw). The game is believed to be a draw for 4×7, is undecided for 4×8, believed to be a proven win for 4×9, and has been proved as a win for 4×11 by means of variation trees (Ma).

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

In higher dimensions, for any n-in-a-row, there exists a dimension d board (n×n×...×n) 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 d will still exist that gives a first player win. For 3×3×3 and 4×4×4, the first player can always win (Gardner 1979), thus establishing d=3 for n=3 and n=4. For n=8, Golomb has proven d>3 with a Hales-Jewett pairing strategy (Ma 2005). Values of d for other n are unknown, and the Hales-Jewett theorem does not help, as it is existential and not constructive.


See also

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

Explore with Wolfram|Alpha

WolframAlpha

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

Referenced on Wolfram|Alpha

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

Subject classifications