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. of the game tree for tic-tac-toe.]] But the very 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's 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).

Table of contents

1 Variations 2 Alternative names 3 External Links

Variations

\nMany games share the element of trying to be the first to get n-in-a-row: three men's morris, nine men's morris, pente, gomoku, Connect Four, Quarto. The m,n,k-games are a family of generalized games based on tic-tac-toe.

• 3-dimensional tic-tac-toe on a 3×3×3 board is no fun: the first player has an easy win by playing in the centre. But the game on the 4×4×4 board (called Qubic) is much more subtle. It was solved by Victor Allis in 1994 (the first player can force a win) but is still interesting for humans.\n* In misère tic-tac-toe you win if the other player gets n in a row. The 3×3 game is a draw.\n* In nine board tic-tac-toe nine tic-tac-toe boards are themselves arranged in a 3×3 grid. The first player's move may go on any board; all moves afterwards are placed in the empty spaces on the board corresponding to the square of the previous move (that is, if a move were in the upper-left square of a board, the next move would take place on the upper-left board). If a player can't move because the indicated board is full, the next move may go on any board. Victory is attained by getting 3 in a row on any board. This makes the game considerably longer and more involved than tic-tac-toe, with a definite opening, middle game and endgame.

Alternative names

\n*Tic-tac-toe, tick-tat-toe, or tit-tat-toe (English - USA)\n*Noughts and crosses or naughts and crosses (English - United Kingdom and Ireland)\n*Ta-te-ti (Spanish)\n*Tres en raya ("three in a line") (Spanish)\n*Gato (Spanish)\n*Morpion (French)\n*Kaesekaestchen (Cheese Squares) (German)\n*Boter, kaas en eieren ("butter, cheese and eggs") (Dutch)\n*Amőba (Hungarian)\n*Kryds og bolle (Danish)\n*Tripp trapp trull (Swedish)\n*Ristinolla (Finnish)\n*X şi zero (Romanian)\n*Jogo da velha (Portuguese - Brazil)\n*Τρίλιζα (Greek)\n*Zero kata (Hindi)\n*Phool aur chaukadi (Hindi)\n*Maru batsu (円伐, "circle attack") (Japanese)\n*Sanme narabe (三目並べ, "row of three") (Japanese)\n*Морски шах ("sea chess") (Bulgarian) Category:Paper and pencil games\n\n\n\n

External Links

\n*Wolfram's MathWorld