Tic-tac-toe is traditionally a pen-and-paper game for two players, O and X, who take turns to mark the spaces in a 3×3 grid. The player who succeeds in placing three of their own marks in a horizontal, vertical or diagonal row wins the game. You can download a free version of Tic-Tac-Toe for your mobile phone here.

Players soon discover that best play leads to a draw, regardless of where the first player plays. So tic-tac-toe is most often played by very young children; when they have discovered an unbeatable strategy they move on to more sophisticated games such as dots and boxes. This reputation for ease has led to casinos offering gamblers the chance to play tic-tac-toe against trained chickens.

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 31,896 possible games up to rotations and reflections (the game tree complexity) on this space.

Without eliminating symmetries, there are 255,168 possible games. Assuming that X makes the first move every time,

• 131,184 games are won by X
• 77,904 games are won by O
• 46,080 games are a draw