Others view: Welcome ♦ A star algorithm ♦ 2D Fast Fourier Transform ♦ Moon phase ♦ Ring counter ♦ rss.xml ♦ Binary counter ♦ 2-3-4 tree ♦ RSA encryption algorithm ♦ Ray diagram ♦

TicTacToe (game)

Tic-tac-toe (tick tack toe, noughts and crosses, Xs and Os and many other names) is a very old pencil-and-paper game for two players, O and X, who take turns marking the spaces in a rectangular grid, usually X going first.

On the 3x3 board this game is more like "amusing applet"
The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game. The simplest version is played in 3x3 grid and the line must span over the board, consisting of three pieces. More complex (also shown in the applet) versions use larger (or even "infinite") board requiring to make long (often five pieces) vertical, horizontal or diagonal line.

According to Claudia Zaslavsky's book Tic Tac Toe: And Other Three-In-A Row Games from Ancient Egypt to the Modern Computer, the game Tic Tac Toe is originally from ancient Egypt.[1].

3 x 3 board

When playing on the 3x3 board, players soon discover that best play from both parties leads to a draw. Hence, tic-tac-toe is most often played by young children; when they have discovered an unbeatable strategy they move on to more sophisticated games. This reputation for ease has led to casinos offering gamblers the chance to play tic-tac-toe against trained chickens (though the chicken is advised by a computer program)[2]

The simplicity of tic-tac-toe makes it ideal as a 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, enumerating the 765 essentially different positions (the state space complexity), or the 26,830 possible games up to rotations and reflections (game tree complexity) on this space.

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

One example of a Tic-Tac-Toe playing computer is the Tinkertoy computer, developed by Massachusetts Institute of Technology, and made out of Tinker Toys.[3] It only plays Tic-Tac-Toe and has never lost a game. It is currently on display at the Museum of Science, Boston.

This version of the game is called Moku in Japan. An amusing applet exists that allows to play this game[4].

Playing strategies

Surprisingly few people know optimal stategy of this game. Apart just random moves, there are two major strategies of playing this Tic Tac Toe[5]:

  • To block opponent from winning (reactionary player)
  • To know that playing into the certain squares will loose the game.
  • To enumerate all possible future scenarios of the game (possible for computer but not for a human player).

Both first and second player needs to avoid edges, preferring corners or center. If the first player takes the center during the first move, the second player should take any corner. If the first player takes the corner instead, the second player should take the center.

Experienced player never looses (for the two experts, the game ends in a draw).

Go - Moku

Go-Moku with the goal to make five pieces in a row on larger board is playable as a real game
Another variation on tic-tac-toe is played on a larger grid (say 10x10) where the object is to get 5 in a row. The increased amount of space creates a greater complexity. There is a variation on tic-tac-toe that is popular in Vietnam, in which the player has to get 5 in a row to win the game. Each player takes turns to mark "x" or "o" on the board. The stategy is to not only block the opponent, but create chances for yourself to form 5 in a row in any direction. The board is unlimited and has no boundary until one wins. This version is also called Go-Moku and is also old. The name "Gomoku" is from the Japanese language. Go means five, moku is a counter word for pieces and narabe means line-up. The game is also popular in Korea, where it is called omok (오목) which has the same structure and origin as the Japanese name.

In the nineteenth century, the game was introduced to Britain where it was known as "Go Bang", said to be a corrupution. Japanese goban, said to be adapted from Chinese k'i pan (qí bàn) 'chess-board'.[6]

References

  1. 1 http://www.jacketflap.com/bookdetail.asp?bookid=0690043163
  2. 2 Columnist Susan Snyder: Defeat a chicken? Good cluck
  3. 3 Tinkertoys and tic-tac-toe
  4. 4 Amusing applet to play Moku
  5. 5 Tic Tac Toe strategy analysis
  6. 6 OED citations: 1886 GUILLEMARD Cruise ‘Marchesa’ I. 267 Some of the games are purely Japanese..as go-ban. Note, This game is the one lately introduced into England under the misspelt name of Go Bang. 1888 Pall Mall Gazette 1. Nov. 3/1 These young persons (..) played go-bang and cat's cradle.

Acknowledgements: This article reuses material from the two Wikipedia articles:

under the rights of Creative Commons Attribution Share Alike license. It is and will stay available under this license regardless of any restrictions that may be specified in the terms of use section.