Tic-tac-toe

Tic-tac-toe, known as noughts and crosses in Commonwealth English and Xs and Os in Canadian or Irish English, is a two-player paper-and-pencil game played on a three-by-three grid. Players alternate marking the nine spaces, one using X and the other O. A win is achieved by marking all three spaces of any row, column, or diagonal, traditionally indicated by drawing a line through those marks. The game is solved; with optimal play from both sides, it always ends in a draw. This simplicity makes it a common pedagogical tool for teaching sportsmanship and artificial intelligence concepts like game tree searching and the minimax algorithm.

History

A computer program can easily play perfectly, and the game tree complexity, accounting for rotations and reflections, includes 26,830 possible games, with 765 essentially different positions. The game’s roots trace back to ancient Egypt around 1300 BC, where similar boards were found on roofing tiles. A Roman variation called terni lapilli, played with three pebbles per player that had to be moved, dates to the first century BC.

The modern names are more recent: the first print reference to "noughts and crosses" appeared in 1858, while "tick-tack-toe" was recorded in 1884, though it originally described a different children’s game. The American renaming to "tic-tac-toe" occurred in the 20th century. In 1952, OXO, developed by Sandy Douglas for the EDSAC computer, became one of the first video games, playing perfect tic-tac-toe.

In 1975, MIT students built a Tinkertoy computer that could play the game perfectly, now displayed at the Computer History Museum. With the internet, the game became a staple of casual digital entertainment, with Google integrating a playable version into its search results in 2016. Considering board symmetries, there are only 138 terminal positions: 91 won by X, 44 by O, and 3 drawn. The game can be generalized to an m,n,k-game, where tic-tac-toe is the 3,3,3 variant.