Tic-tac-toe [1] - a logical game between two opponents in a square field of 3 by 3 cells or larger (up to the "endless field"). One of the players plays “crosses”, the second - “zero”. In the traditional Chinese game ( Gomoku ), black and white stones are used.
Content
Classic Edition
Game Rules
Players take turns placing 3x3 signs on free square cells (one always crosses, the other always zeros). The first, lined up 3 of his pieces vertically, horizontally or diagonally, wins. The first move is the cross-player.
Usually, at the end of the game, the winning side crosses out with a line their three characters (zero or cross), which make up a continuous row.
Analysis
For each of the parties, well-known algorithms that guarantee a draw for any game of the opponent, and with his mistake, allow you to win. Thus, the game is in a state of "no man's death . "
The following are some of these strategies. It is believed that a player always respects two rules that take precedence over all others:
- Rule 1. If a player can immediately win, he does it.
- Rule 2. If a player cannot immediately win, but his opponent could immediately win by making a move to some square, the player himself makes a move to this square, preventing an immediate loss.
Crosses
Make the first move to the center. The remaining moves, if rules 1-2 are not applicable, are made into that of the free corners, which is farthest from the previous move of the zeros , and if this is impossible, into any cell.
| X | ||
We prove that this strategy leads to a victory or a draw. If the toe goes to the side, then the position (accurate to symmetry) will be as follows:
| ABOUT | ||
| X | ||
| X |
After that, rules 1 and 2 will lead to the position:
| X | ABOUT | ABOUT |
| X | ||
| X |
Win .
If the toe goes to the corner, the position (accurate to symmetry) will be as follows:
| ABOUT | ||
| X | ||
| X |
Depending on the next move of the zero, one of three positions will appear:
| ABOUT | ABOUT | X |
| X | ||
| X |
| ABOUT | X | ABOUT |
| X | ||
| X |
| ABOUT | ||
| X | ABOUT | |
| X | X |
In the first and third positions - a win . In the second - a draw.
For Tac Toe
We recall that rules 1–2, if applicable, take precedence over everything written below.
- If the crosses made the first move to the center, go to any corner before the end of the game, and to any cell if this is impossible.
| ABOUT | ||
| X | ||
- If the crosses made the first move to the corner, respond with a move to the center.
| X | ||
| ABOUT | ||
- The next move to take the corner opposite the first move of the crosses, and if this is impossible - go to the side.
| X | ||
| ABOUT | ||
| X | ABOUT |
- If the crosses made the first move to the side, respond with a move to the center.
- If the next move of the crosses is into a corner, take the opposite corner:
| X | ABOUT | |
| ABOUT | ||
| X |
- If the next move of the crosses is on the opposite side, go to any corner:
| ABOUT | X | |
| ABOUT | ||
| X |
- If the next move of the crosses is on the side next to their first move, go to the corner next to both crosses
| ABOUT | X | |
| X | ABOUT | |
Game Tree
The tree of game situations for the game of tic-tac-toe, where the player for the "tic-tac-toe" goes first and acts according to the above algorithm, and the player for the "tic-tac-toe" can do anything (moreover, one vertex is given for a rational and irrational act, that is, any another), consists of 50 nodes.
Computer Solution
To solve this kind of games, a tree of game situations is built on the computer in accordance with the mini-max method. The total number of nodes in such a tree is 255168 [2] . This number is obtained as the sum of all possible moves - 9 options in the first step, 8 - for each of 9 in the second step, 7 - in each of 72 options in the third step, etc., minus the situations of early termination of the game (winning )
Generalizations
Longer lines
You can consider a game in which the winner is the player who first built identical signs on a rectangular field large enough for this. At the same time, you can limit the field to any size (starting from ), or not at all to limit (in this case we speak of an “infinite” field)
Playing up to 4 identical signs on an endless field is uninteresting, because a beginner builds a “plug” rather quickly and wins. Game at also uninteresting due to "no man's death." There are strategies that prevent the enemy from building the right line ever. However, when the game becomes much more informative. This option has a special name - gomoku . Initially, homoku was played on a 19 × 19 board, later it was reduced to a size of 15 × 15 cells.
The main winning tactics when playing on an endless field is the construction of intersections (“forks”), which do not give the enemy the opportunity to block all possible ways of building the five. In order not to lose, it is necessary to timely interrupt enemy lines with a length of three figures or more.
Practice has shown that, with equal rules for players, the one who makes the first move has the advantage of allowing a victory with a sufficiently qualified game, which was subsequently proved rigorously [3] [4] . To maintain interest in the game, various options for modifying the rules of the game were offered. So, with the introduction of fouls (forbidden moves) for the player starting first - he is forbidden to build 3 × 3, 4 × 4 forks, and also to build a “long row” of his pieces - a new game called renju with a wide variety of game strategies and equal chances for players.
Field Modification
The increase in field size has already been discussed above. The simplest, but increasing the tactical richness of the game, is the addition of one cell along one of the sides of the 3x3 field.
Another option is to change the field topology. For example, you can consider the opposite sides of the field glued together, forming either the surface of a cylinder or a torus , or a projective plane . You can also increase the dimension, for example, play in a 4x4x4 cube, in a hypercube, and so on.
Icon Exchange
You can undo the rule telling players to put only their own kind of badges.
For example, a variant of the game could be: players put a cross or a zero (whatever they want); the first wins if it draws a line of the required length from the same icons, the second - if this does not happen before filling out the field.
Another option: “your” icon changes with each move.
Change in win conditions
Instead of ending the game with the construction of the first line of the desired length, you can not stop there and continue until the field is completely filled. For example, on any field you can play on whoever builds the “fours” of their signs more.
There is also a variant of Silverman's tic-tac-toe . It uses a 4x4 square playing field. The crosses win if there is a series of 4 identical icons (crosses or zeros), otherwise the zeros win.
Elongation
Another option for modifying the game is to exhibit at each turn not one sign, but two or more. This is the game Connect6 , in which Black makes his first move by displaying one sign, after which the players alternately place two signs, the first one who draws a line of 6 or more of his signs wins.
See also
- Gomoku
- Renju
- Game with full information
- No man's death
- Hexapawn
Notes
- ↑ In the 19th century, along with the name “tic-tac-toe” (see N. A. Leikin , “Study Day at a German School”, 1871), “herik-onics” or “heriks” were also used - according to the old name of the Russian letters of the alphabet “X” - “dick” and “O” - “it” ( “Dick” in the Dahl dictionary; Archived copy of June 14, 2011 on the Wayback Machine ), “toe” ( N. P. Gilyarov-Platonov , “From the Past” , 1886
- ↑ How many Tic-Tac-Toe (noughts and crosses) games? . www.se16.info. Date accessed August 16, 2019.
- ↑ Allis, LV (1994). Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht.
- ↑ Allis, LV, Herik, HJ van den, and Huntjens, MPH (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence, Vol. 12.
Literature
- Gardner M. Tic-tac-toe. —M .: Mir, 1988. ISBN 5-03-001234-6 .