Tic-Tac-Toe (original) (raw)
Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology
Alphabetical Index New in MathWorld
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.
See also
Board, Connect-Four, Connection Game, Gomoku,No-Three-in-a-Line-Problem, Pong Hau K'i, Qubic
Explore with Wolfram|Alpha
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
Cite this as:
Weisstein, Eric W. "Tic-Tac-Toe." FromMathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Tic-Tac-Toe.html