Tic-tac-toe (also known as noughts and crosses or Xs and Os) is a paper and pencil game for two players, X and O, who take turns marking the spaces in a 3 × 3 grid. The player who achieves Placing three of your marks in a horizontal, vertical or diagonal row wins the game.
The following example of the game is won by the first player, X:
Players soon discover that the best game on both sides leads to a draw. Therefore, tic-tac-toe is most often played by young children.
Due to the simplicity of the tic-tac-toe, it is often used as a pedagogical tool to teach the concepts of good sportsmanship and the branch of artificial intelligence that deals with the search for game trees. It is easy to write a computer program to play perfectly to tic-tac-toe, to list the 765 essentially different positions (the spatial complexity of the state), or the 26,830 possible games until rotations and reflections (the complexity of the game tree) in this Space.
The game can be generalized to a m, n, k-game in which two players alternate placing stones of their own color on a m × n board, in order to get k of their own color in a row. Tic-tac-toe is the game (3,3,3). Harary's generalized tic-tac-toe is an even broader generalization of tic tac toe. It can also be generalized as a nd game. Tic-tac-toe is the game where n is equal to 3 and d equals 2. If played correctly, the game will end in a tie by tic-tac-toe a useless game.