The History of Tic-Tac-Toe
Probably the best-known pencil-and-paper game of all - with roots in ancient Rome and a place in the history of computers.
Three Pebbles in Rome
An early relative was played in the Roman Empire around the first century BC, probably under the name terni lapilli, "three pebbles at a time". Each player had only three pieces, so once they were all on the board, they were moved to empty points to keep the game going.
Grid markings for the game have been found in many places around Rome.
Noughts and Crosses, Tic-Tac-Toe
The game has gone by many names. The British name "noughts and crosses" was already in print by the middle of the 19th century, for example in the journal Notes and Queries in 1858.
In the United States it came to be called tic-tac-toe during the 20th century. The name may go back to "tick-tack", an old form of backgammon known in England since the 16th century.
One of the First Computer Games
In 1952 A. S. (Sandy) Douglas wrote OXO for the EDSAC computer at the University of Cambridge, as part of his doctoral thesis on how people and computers interact. Players picked their square with a rotary telephone dial, and the computer played a perfect game. OXO counts among the first known video games.
The game is small enough to be worked out completely: up to rotations and reflections there are 26,830 possible games, and with perfect play every game ends in a draw. The Hard level here does exactly that - before each move it looks at every possible way the game can go on.