Tic-tac-toe
Tic-tac-toe, also known as noughts and crosses or Xs and Os, is a two-player abstract strategy game traditionally played on a 3×3 grid using a pen and paper, where players alternate marking empty cells with their symbol—typically X for the first player and O for the second—with the goal of forming an unbroken line of three identical symbols horizontally, vertically, or diagonally.[1] The game concludes in a victory for the player who achieves this alignment first, or in a draw if all nine cells are filled without either player succeeding.[1] With optimal strategy from both participants, tic-tac-toe invariably results in a draw, making it a solved game in combinatorial game theory.[1] The game's roots extend to ancient civilizations, with the earliest evidence of similar three-in-a-row mechanics appearing on roofing tiles in Egypt dating to approximately 1300 BCE, suggesting it may have been used for recreational or ritual purposes.[1] It evolved across cultures, including the Roman variant terni lapilli—meaning "three pebbles"—played with stones on engraved boards, and later forms like Asian three men's morris and Native American Picaria.[1] By the 19th century in Britain, it was documented as noughts and crosses in an 1858 journal, reflecting its spread through Europe.[1] The American term "tic-tac-toe" gained popularity in the early 20th century, possibly derived from the sound of marking the grid or its rhythmic play.[1] Beyond its simplicity as a childhood pastime, tic-tac-toe holds significance in mathematics and computing as an accessible model for minimax algorithms and decision trees in artificial intelligence.[2] The first computerized version was developed in 1952 by Alexander S. Douglas on the EDSAC machine at the University of Cambridge, marking an early milestone in video gaming.[1] In 1975, MIT students created an unbeatable tic-tac-toe mechanical computer built from Tinkertoys using perfect strategy, now preserved at the Museum of Science in Boston.[1] The game has inspired countless variants, such as 3D tic-tac-toe on 3×3×3 cubes, misère versions where the last move loses, and larger grid adaptations that introduce greater complexity and potential for wins.[3]Introduction
Gameplay
Tic-tac-toe, also known as noughts and crosses, is played on a 3×3 grid consisting of nine empty cells arranged in three rows and three columns.[4] Two players alternate turns marking empty cells with their respective symbols: the first player uses X and begins the game, while the second player uses O.[5] On each turn, a player places their mark in one unoccupied cell, with the goal of achieving a winning configuration.[6] A player wins by placing three of their marks in an unbroken line, either horizontally, vertically, or diagonally across the board.[4] If the board fills completely without either player achieving three in a row, the game ends in a draw.[5] During play, a player may need to block an opponent's near-complete line by occupying the threatening cell or create a fork by setting up two potential winning lines simultaneously, though such actions depend on the unfolding sequence of moves.[7] A sample game sequence leading to a win for the first player (X) proceeds as follows, with cells numbered 1–9 from top-left to bottom-right in row-major order:-
X places in cell 1 (top-left).
Board:
| X | | |
| | | |
| | | | -
O places in cell 5 (center).
Board:
| X | | |
| | O | |
| | | | -
X places in cell 2 (top-middle).
Board:
| X | X | |
| | O | |
| | | | -
O places in cell 4 (middle-left).
Board:
| X | X | |
| O | O | |
| | | | -
X places in cell 3 (top-right), completing the top row.
Board:
| X | X | X |
| O | O | |
| | | |
X wins with three in the top row.[8]
| X | O | X |
| X | O | X |
| O | X | O |
No winner emerges, resulting in a draw.[7]
Names and Terminology
In English-speaking regions, the game is commonly known as tic-tac-toe in American English, noughts and crosses (or naughts and crosses) in British and Commonwealth English, and Xs and Os as a shorthand in North American contexts.[9][10] The term "tic-tac-toe" emerged in the late 19th century, with the earliest recorded use of "tick-tack-toe" appearing by 1892, though variants like "tit-tat-toe" date to 1852 in schoolboy reminiscences.[9] Its etymology is imitative, deriving from the "tick-tack" sound of a pencil or chalk marking a slate during play, a common medium for the game among children in that era; earlier associations link "tick-tack" to clicking sounds in board games like a 16th-century backgammon variant.[9] This onomatopoeic origin reflects the game's informal, playful nature in 19th-century British and American culture, where it evolved from older names like "noughts and crosses."[9] The game's symbols, X and O, originate from the British name "noughts and crosses," where "nought" represents the circle O (symbolizing zero) and "cross" the mark X, chosen for their simplicity in drawing on paper or slate.[9] While some folk etymologies connect X to Roman numeral ten and O to zero, or link them to affectionate "kisses" (X) and "hugs" (O) in correspondence, these are later associations unrelated to the game's core mechanics.[11] Across cultures, the game bears diverse names that often describe the alignment of symbols or evoke whimsical imagery, illustrating its widespread adoption through colonial and global exchanges.[10] In Spanish-speaking countries, it is frequently called tres en raya (three in a row), emphasizing the winning condition.[12] In Italy, the term tris refers to achieving three in a line, a concise nod to the objective.[13] Portuguese speakers in Brazil know it as jogo da velha (old woman's game), possibly alluding to a grandmotherly figure drawing circles, a cultural anecdote tying the name to domestic play.[12] A notable piece of terminology is cat's game, used in American English to describe a draw, where neither player secures three in a row. This phrase draws from the futile image of a cat chasing its own tail—an endless, winless pursuit—mirroring the balanced stalemate in optimal play; it gained traction in mid-20th-century children's slang, evoking lighthearted frustration in playground matches.History
Ancient Origins
The earliest known evidence of tic-tac-toe-like games appears in ancient Egypt during the second millennium BCE, where 3x3 grids were etched into roof tiles dating to around 1300 BCE. These archaeological finds, discovered on roofing materials, suggest early forms of alignment games played with simple markers, though the exact rules remain unknown due to the absence of accompanying texts.[1] In the Roman Empire, a variant known as terni lapilli ("three pebbles at a time") emerged around the first century BCE, involving each player placing exactly three marks on a 3x3 board to form a line. The poet Ovid referenced this game in his Ars Amatoria, describing it as a small board where victory comes from aligning one's pebbles, highlighting its popularity in Roman society as a pastime for courtship and leisure. Boards for terni lapilli have been found etched into stone surfaces across Roman sites, indicating widespread play.[14][15] Similar alignment games have been identified in other ancient cultures, including Native American variants like Picaria played by the Pueblo peoples, which involved forming lines with three pieces on a grid board, suggesting parallel developments in recreational play.[16] By medieval Europe around 1300 CE, similar alignment games like three men's morris appeared in manuscript illustrations, depicting players forming lines on grid boards, often in monastic or aristocratic contexts. These illustrations, found in European codices, show the game's evolution into more formalized variants. Unlike contemporary tic-tac-toe, ancient and medieval versions frequently permitted more than three marks per player or featured alternative win conditions, such as capturing opponents' pieces rather than solely completing a line.[15]Modern Development
The modern form of the game, referred to as "noughts and crosses" in Britain, first gained printed recognition in the late 1850s. A 1858 issue of the scholarly periodical Notes and Queries described it as a common pastime among English schoolboys, marking the earliest documented rules and terminology for the 3x3 grid version played with zeros and crosses.[1] This publication helped standardize the game's structure, distinguishing it from earlier informal grid games by emphasizing alternating turns and the goal of three in a row.[16] In the United States, the game adopted the name "tic-tac-toe" during the early 1900s, with the term appearing in newspapers around the early 20th century as a children's diversion.[16] The name likely derived from "tick-tack-toe," an older reference to backgammon variants, but became associated with American betting slang, where "tic-tac" denoted hand signals used by horse racing bookmakers to convey odds silently.[12] This linguistic shift reflected the game's adaptation in popular print media, including puzzles and cartoons that popularized it among American youth by the 1910s and 1920s. Commercialization accelerated in the 1930s as toy manufacturers packaged the game in dedicated sets, often with wooden or cardboard boards and markers, transforming it from a slate scribble into a marketable product for home entertainment.[16] The digital era brought further evolution in the 1950s, with early computer implementations serving as tests for machine intelligence and interaction. In 1952, British researcher A. S. Douglas programmed OXO, a tic-tac-toe simulation on the EDSAC computer at the University of Cambridge, displayed on a cathode-ray tube; it pitted users against an unbeatable electronic opponent to explore human-machine dialogue in his PhD thesis.[17] This marked one of the first graphical computer games, influencing subsequent AI experiments by demonstrating programmed decision-making in simple adversarial play. Through British colonization and 20th-century media, the game disseminated widely beyond Europe. In Asia, it appeared in Indian school curricula and print media by the 1920s under colonial influence, often as "noughts and crosses" in English-language publications. In Africa, British educational systems in regions like Nigeria and South Africa introduced it during the mid-1900s, where it integrated into local play via mission schools and newspapers, sometimes blending with indigenous grid games.Mathematical Foundations
Combinatorics
The total number of possible board configurations in tic-tac-toe is $3^9 = 19,683, as each of the nine cells can be empty, marked with X, or marked with O. These configurations can be categorized into equivalence classes using the symmetries of the square, described by the dihedral group D_4, which includes four rotations ($0^\circ, $90^\circ, $180^\circ, $270^\circ) and four reflections (horizontal, vertical, and two diagonals). Applying Burnside's lemma to count the fixed points under each group element yields the number of distinct configurations up to symmetry: \frac{1 \times 3^9 + 2 \times 3^3 + 1 \times 3^5 + 4 \times 3^6}{8} = 2862. Considering only reachable states under legal play—where X starts, players alternate turns, the difference in the number of X and O marks is at most one, and no player has three in a row before the current state—the total reduces to 5,478 positions. Accounting for D_4 symmetries in these reachable states further reduces the count to 765 unique positions.[18] The outcomes of complete games, counted as sequences of legal moves until termination, total 255,168. Among these, 131,184 end in an X win, 77,904 in an O win, and 46,080 in a draw.[19] The distribution of legal positions by the number of plays n (where a play is one mark placed), up to D_4 symmetry, is as follows:| n (plays) | Legal positions (up to symmetry) |
|---|---|
| 0 | 1 |
| 1 | 3 |
| 2 | 12 |
| 3 | 38 |
| 4 | 108 |
| 5 | 174 |
| 6 | 204 |
| 7 | 153 |
| 8 | 57 |
| 9 | 15 |