Tic-tac-toe
Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. A player wins by getting three of their own marks in a horizontal, vertical or diagonal row.
This game is won by the first player, X:
This game is drawn:
Players soon discover that best play leads to a draw, regardless of where the first player plays. So tic-tac-toe is most often played by very young children; when they have discovered an unbeatable strategy they move on to more sophisticated games such as dots and boxes.
But the very simplicity of tic-tac-toe makes it ideal as a pedagogical tool for teaching the concepts of game theory and the branch of artificial intelligence that deals with the searching of game trees. It's straightforward to write a computer program to play tic-tac-toe perfectly, to enumerate the 765 essentially different positions (the state space complexity), or the 26,830 possible games (the game tree complexity).
Variations
Many games share the element of trying to be the first to get n-in-a-row: three men's morris, nine men's morris, pente, gomoku, Connect Four, Quarto. The m,n,k-games are a family of generalized games based on tic-tac-toe.
- 3-dimensional tic-tac-toe on a 3×3×3 board is no fun: the first player has an easy win by playing in the centre. But the game on the 4×4×4 board (called Qubic) is much more subtle. It was solved by Victor Allis in 1994 (the first player can force a win) but is still interesting for humans.
- In misère tic-tac-toe you win if the other player gets n in a row. The 3×3 game is a draw.
- In nine board tic-tac-toe nine tic-tac-toe boards are themselves arranged in a 3×3 grid. The first player's move may go on any board; all moves afterwards are placed in the empty spaces on the board corresponding to the square of the previous move (that is, if a move were in the upper-left square of a board, the next move would take place on the upper-left board). If a player can't move because the indicated board is full, the next move may go on any board. Victory is attained by getting 3 in a row on any board. This makes the game considerably longer and more involved than tic-tac-toe, with a definite opening, middle game and endgame.
Alternative names
