Tic-tac-toe

 related topics {game, team, player} {math, number, function} {@card@, make, design} {line, north, south} {film, series, show} {system, computer, user} {theory, work, human} {service, military, aircraft} {war, force, army} {language, word, form} {school, student, university}

Tic-tac-toe, also spelled tick tack toe, or noughts and crosses as it is known in the UK, Ireland, Australia, New Zealand, is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first[citation needed]. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game.

The following example game is won by the first player, X:

Players soon discover that best play from both parties leads to a draw. Hence, tic-tac-toe is most often played by young children. This reputation for ease has led to casinos offering gamblers the chance to play tic-tac-toe against trained chickens called chick tac toe.[1]

The simplicity of tic-tac-toe makes it ideal as a pedagogical tool for teaching the concepts of combinatorial game theory and the branch of artificial intelligence that deals with the searching of game trees. It is 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 up to rotations and reflections (the game tree complexity) on this space.

The first known video game, OXO (or Noughts and Crosses, 1947) for the EDSAC computer played perfect games of tic-tac-toe against a human opponent.

The earliest known variant of tic-tac-toe originated in the Roman Empire around the first century BC. It was called Terni Lapilli and instead of having any number of pieces, each player only had three, thus they had to move them around to empty spaces to keep playing. The game's grid markings have been found chalked all over Rome.

One example of a Tic-Tac-Toe playing computer is the Tinkertoy computer, developed by MIT students, and made out of Tinker Toys.[2] It only plays Tic-Tac-Toe and has never lost a game. It is currently on display at the Museum of Science, Boston.