Tic-Tac-Toe -- from Wolfram MathWorld
- ️Weisstein, Eric W.
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." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Tic-Tac-Toe.html