Tic-tac-toe

Tic-tac-toe, also called noughts and crosses and many other names, is a paper and pencil game between two players, O and X, who alternate in marking the spaces in a 3×3 board. A player wins by getting three of their own marks in a horizontal, vertical or diagonal row.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This game is won by the first player, X:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This game is drawn:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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 Las Vegas casinos offering gamblers the chance to play tic-tac-toe against trained chickens.

Related Topics:
Dots and boxes - Las Vegas - Casino - Chicken

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The simplicity of tic-tac-toe makes it ideal as a pedagogical tool for teaching the concepts of 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 26,830 possible games (the game tree complexity) on this space. Ignoring symmetry, there are 255,168 possible games.

Related Topics:
Game theory - Artificial intelligence - Game tree - Computer program - State space complexity - Game tree complexity

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The first known computer game, OXO (or Noughts and Crosses, 1952) for the EDSAC computer played perfect games of tic-tac-toe against a human opponent.

Related Topics:
Computer game - OXO - 1952 - EDSAC

~ ~ ~ ~ ~ ~ ~ ~ ~ ~