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.