Editing Tic-tac-toe (section)

== Gameplay ==

Tic-tac-toe is played on a three-by-three grid by two players, who alternately place the marks X and O in one of the nine spaces in the grid.

In the following example, the first player (''X'') wins the game in seven steps:
[[File:tic-tac-toe-game-1.svg|center|Game of Tic-tac-toe, won by X]]

There is no universally agreed rule as to who plays first, but in this article the convention that X plays first is used.

Players soon discover that the best play from both parties leads to a [[draw (tie)|draw]]. Hence, tic-tac-toe is often played by young children who may not have discovered the optimal strategy.

Because of the simplicity of tic-tac-toe, it is often used as a [[pedagogical]] tool for teaching the concepts of good [[sportsmanship]] and the branch of [[artificial intelligence]] that deals with the searching of [[game tree]]s. It is straightforward to write a computer program to play tic-tac-toe perfectly or 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.<ref>{{cite web|url=http://www.mathrec.org/old/2002jan/solutions.html|title=MathRec Solutions (Tic-Tac-Toe)|website=Mathematical Recreations|first=Steve|last=Schaefer|year=2002|access-date=September 18, 2015|archive-date=June 28, 2013|archive-url=https://web.archive.org/web/20130628112339/http://www.mathrec.org/old/2002jan/solutions.html|url-status=dead}}</ref> If played optimally by both players, the game always ends in a draw, making tic-tac-toe a [[futile game]].<ref>{{Cite web|url=http://mathworld.wolfram.com/Tic-Tac-Toe.html|title=Tic-Tac-Toe|last=W.|first=Weisstein, Eric|website=mathworld.wolfram.com|language=en|access-date=May 12, 2017}}</ref>

[[File:Three Men's Morris variant board.svg|thumb|160px|[[Incidence structure]] for tic-tac-toe]]

The game can be generalized to an [[m,n,k-game|''m'',''n'',''k''-game]], in which two players alternate placing stones of their own color on an ''m''-by-''n'' board with the goal of getting ''k'' of their own color in a row. Tic-tac-toe is the 3,3,3-game.<ref>{{cite book|last1=Pham|first1=Duc-Nghia|last2=Park|first2=Seong-Bae|title=PRICAI 2014: Trends in Artificial Intelligence: 13th Pacific Rim International Conference on Artificial Intelligence|url=https://books.google.com/books?id=1vdWBQAAQBAJ&pg=PA735|date=November 12, 2014|publisher=Springer|isbn=978-3-319-13560-1|page=735}}</ref> [[Harary's generalized tic-tac-toe]] is an even broader generalization of tic-tac-toe. It can also be generalized as an [[nd game|''n''<sup>''d''</sup> game]], specifically one in which ''n'' = 3 and ''d'' = 2.<ref name="gh02" /> It can be generalised even further by playing on an arbitrary [[incidence structure]], where rows are [[line (geometry)|lines]] and cells are [[point (geometry)|points]]. Tic-tac-toe's incidence structure consists of nine points, three horizontal lines, three vertical lines, and two diagonal lines, with each line consisting of at least three points.