Strategic Tic-Tac-Toe (Starategic Tic-Tac-Toe)

Playing one game in tic-tac-toe for more than two hours is easy.

The article will discuss how to introduce elements of "strategy and tactics" into the tic-tac-toe familiar to everyone. Will be described and analyzed the rules of the game, talked about playing fields.

What is offered?

The game S tarategic T ic- T ac- T oe ( STTT ) or Strategic tic-tac-toe is, like its progenitor, a game for two participants for which only a pencil and paper are needed. It is a superset of the Ultimate Tic-Tac-Toe game as well as the Ultimate Tic-Tac-Toe is a superset of the usual Orc Tic-Tac-Toe . The task of the game is to help players acquire the skills of strategic thinking.
Project home page

Content

1. Terms and Definitions
2. Rules of the game
   
   • Operational tic-tac-toe
   • Tactical tic-tac-toe
   • Strategic tic-tac-toe
     
     1. General rules
     2. Tactical rule set
     3. Functional rule set
     4. Hyper-functional rule set
3. Playing fields
4. Game analysis
5. Conclusions and afterword

Terms and Definitions

Carefully, many similar definitions and their number can push you away, but without this basis you cannot understand what will be discussed further.

• Ordinary tic-tac-toe will be called Operational tic-tac-toe .
• Ultimate Tic-Tac-Toe will be called Tactical Noughts and crosses .
• A cage is a place on the playing field in which players can place a cross or a zero, also called the Operational cell .
• Operational field - the playing field of Operational daggers, also called Tactical cell - 3x3 grid of cells.
• Tactical field - the playing field of Tactical daggers, also called the Strategic cell - 9x9 grid of cells, 3x3 grid of tactical cells.
• Strategic field - playing field Strategic noughts and crosses - 27x27 grid of cells, 9x9 grid of tactical cells, 3x3 grid of strategic cells.
• Operational level - a game of Operational tic-tac-toe - move rules, win conditions and restrictions.
• Tactical level - Tactical tic-tac-toe game - rules of interaction between Cells and Tactical cells, winning conditions and restrictions.
• Strategic level - the game of Strategic Tic-Tac-Toe presented with the help of the concepts of the Tactical level - the rules of interaction between the Tactical cells and the Strategic cells, the conditions of gain and limitations.
• Cell of the current move - The cell in which the current player puts, depending on which side he plays, a cross or a toe.

At this point, all the definitions we need are set and we can begin to discuss the game itself.

Rules of the game

By asking and analyzing this class of games (a superset of the Tic-tac-toe game), we, to simplify understanding and comparison, divide the game rules into three parts: the turn rules, the win rules and the restrictions. Consider the game Operational tic-tac-toe according to this approach.

Operational tic-tac-toe

Rules of the course:

• Players take turns, one by one.
• The first player to play is a cross.
• The current player makes a move to any of the non-occupied cells.

Winning Rules:

• The player whose symbols form a line (horizontal, vertical, diagonal) of three symbols wins.
• A draw is assigned in the case when the entire playing field is filled and it is impossible to designate a winner.

Limitations:

• A player cannot make a move to a cell in which his character or another player’s character already exists.
• You can not continue to make moves after the appointment of a draw or winner.

Now that the rules of the familiar game are set according to the proposed approach, it will be easier for the reader to navigate the rules of Tactical and Strategic tic-tac-toe.
The sets of rules of the Strategic noughts and crosses are based on the rules of the Tactical noughts and crosses, therefore, we present them in the proposed form.

Tactical tic-tac-toe

Rules of the course:

• Players take turns, one by one.
• The first is the player who plays for the cross in any of the 81st free cells.
• Each next move is determined by the previous one as follows: the next player must go to that Tactical cell, which in the Tactical field has the same position as the Operational cell in the current Operational field to which the current player went. This provision is well illustrated by a picture from the English page of the game on Wikipedia.

Picture

Как видно первый игрок сходил в третью Оперативную клетку пятого Оперативного поля, поэтому второй игрок должен ходить в третью Тактическую клетку данного Тактического поля.

Winning Rules:

• A tactical cell can have four game states : Game, Defeated X, Defeated Oh, Draw. The condition of the Draw is considered both for X and for O.
• Wins the player who wins according to the rules of Operational tic zeros on the Tactical field.

Limitations:

1. A tactical cell can have two states of filling : There are places, Filled.
2. If the player's turn is to occur in the Tactical cell with the filling state Filled, then the player can make a move to any empty Operational cell of the Tactical field.
   
   • Optional restriction: If a player's move is to occur in a Tactical cell with a game state not a Game (i.e., Defeated X, Defeated O, or Draw), then the player can make a move to any empty Tactical Field.
3. Optional Restriction: You cannot send the next player to the Tactical box in which he made the previous turn.
4. No one can win with a line of 3 tactical cells with a game state. Draw, if such a situation occurs, the game either ends in a draw or continues until one of the players wins.
5. A player cannot make a move to a cage in which his character or another player’s character already exists.
6. You can not continue to make moves after the appointment of a draw or winner.

For the multitude of students the players with whom I had to fight, this set of rules was maligned to be understood by ear, but during the first trial game, most of them were sorted out, so at this stage I invite the reader to play Tactical tic-tac-toe for which you will need a pencil / pen, a notebook sheet (or usual if well draw straight lines) and an interested friend.

It is time to talk about the strategic tic-tac-toe themselves. First of all, when creating a new game, the goal was to expand the current playing field by increasing the number of “levels” of the game; as a result, it became necessary to create new rules of the move, as the old ones, as we will see below, were complete and could not provide new paths for the task player moves. At the table of discussions of the future rules of this game, three main directions were born after the rules that were transformed into sets: Tactical, Functional and Hyper-functional. We describe these sets of rules.

Strategic tic-tac-toe

General rules

All three sets of rules retain winning rules and restrictions at the Tactical level and declare the same rules for the Strategic level. Thus, the winning rules and restrictions for the Strategic level look exactly the same as the rules of Tactical daggers up to cell names. The reader is invited to write the rules of the Strategic level for checking the understanding of current terms and regulations.

Tactical rule set

The rules of Tactical tic-tacs set the mapping from the set of Cells to the set of Tactical cells to determine where the current player should go depending on the turn of the previous player or other owls on the Tactical level rules. The tactical rule set preserves the mapping from the set of cells of the previous Operational Field to the set of Tactical cells of the current Tactical Field, while declaring that the display from the set of Tactical cells of the previous Tactical Field to the set of Strategic Cells of the Strategic Field is the same as the display from the set of Cells of the previous Operational Field Tactical cells of the current Tactical field or in other words kticheskom level.

Functional rule set

The second idea was to compare lines 9x1 (or columns 1x9, as will be shown below, this is not so significant and the choice in favor of the lines was made only from the aesthetics of the resulting playing field) of the cells of the Strategic cell number to which the next move should be made. This idea was realized by placing the numbers of Strategic cells for the next turn, on the left in the same line as the cell of the current turn. To understand what is at stake, go to the section with playing fields. Features of the choice of the following strategic cells will be disclosed in the analysis of the game. The mapping rules from the set of cells of the current operational field to the set of tactical cells of the next tactical field remain unchanged.

Hyper-functional rule set

The third idea was to determine the number of the Strategic cell of the next turn for each Cell of the current turn. This set of rules determines just such a mapping, while the mapping rules from the set of cells of the current operational field to the set of tactical cells of the next tactical field remain unchanged. Features of the choice of the following strategic cells will be disclosed in the analysis of the game.

Playing fields

The second integral component of the game is its playing field. In this section, the game fields proposed by the author will be described and the prerequisites for the final design obtained will be included and described. All the game and auxiliary fields described in the section, as well as their variations, ready for printing on an A4 sheet, are available for download at the link .
The first challenge in the development of playing fields was the fact that they had to be placed on one side of a sheet of Folio format (better known as a tetrad sheet) so that there was room for auxiliary fields on the sheet. Imagine the field characteristics in the form of a pivot table.

Further, under the appropriate spoilers are images of the fields and notes on their design and purpose.

Game analysis

This section will discuss how the choice of numbers, meaning the following Strategic Box for the Functional and Hyperfunctional Rule Set, was justified. The method of analyzing the game is as follows:

1. Construct the transition graph of the playing field - the very mapping is given on convenient for analysis sets, the graph is given by the adjacency matrix.
2. Exclude from the matrix and memorize the diagonal elements.
3. Apply the Floyd-Worshell algorithm to the resulting matrix to find the shortest path from all vertices to all vertices.
4. Remember all the elements, except the diagonal ones, in the diagonal ones, which were previously stored.
5. Once again, apply the Floyd-Worshell algorithm to the resulting matrix to find the shortest path from vertices to themselves.
6. Add the diagonal elements obtained in the second pass to the memorized non-diagonal elements.
7. Build a heatmap of the resulting matrix.
8. Calculate the average distance between the vertices.

All code implementing the analysis steps can be found by reference . The code is written in Lua 5.1 and runs on both the interpreter and the JIT compiler (the latter is more preferable due to the computational complexity of the proposed method). The final stages of the analysis - the construction of heatmap and the calculation of the average distance was carried out in Excel.

Let's analyze the results. As a reference, take the result for the Tactical rule set. And so for a given set of rules, it is convenient to take a mapping from a set of Tactical cells into it, the average distance between Tactical cells was 1. (8) moves. Not a lot, it means that for a successful game it is worth keeping the last two moves in memory and thinking at least two moves ahead. Heatmap can be seen under the spoiler. For all heatmap, the scale goes from red to green through yellow to increase.

Heatmap Tactical rule set

Next we apply the analysis method to the Functional rule set. In order to determine exactly how the numbers in this set of rules existed some prerequisites, their discussion is beyond the scope of this article, let us just say that during the development a rather effective method of creating sets of numbers was proposed, after analyzing which we were able to come to conclusions about the effectiveness of sets selected from received.

For a given set of rules, it was convenient to take a mapping from the set of triplets of Tactical cells into it (the triplets combined Tactical cells 1-3, 4-6, 7-9 for each Strategic cell). Let's look at the results: two sets of numbers were named optimal under the code names map34 and map67 ; for these sets, the average distance between triplets was 2. (6) turns. Their peculiarity is that the distance from each triplet to itself is exactly 3 turns.

Heatmap sets

map34

map67

Для визуального сравнения представлены heatmap'ы других наборов:
map14

map42

Last we analyze the Hyper-functional rule set. A detailed examination of the playing fields, created under this set of rules, the reader could see the pattern in the arrangement of the numbers responsible for the next Strategic cell. Using this pattern, we created nine sets of numbers describing the transition for the Hyper-functional rule set, from which the optimal code-named hmap2 was found . His performance was 2.206 moves on average between Tactical cells and exactly 3 turns to get into the same Tactical cell.

Heatmap hmap1 and hmap2

hmap1

hmap2

Conclusions and afterword

The article was about the new game in its type - Strategic tic-tac-toe, design decisions during the creation of the game were justified by analysis.

Future directions

The main directions for the authors are:

• Creation of applications and websites of a cooperative game based on this Strategic Tic-Tac-Toe.
• The creation of AI algorithms for playing with a computer, according to the author of the AI ​​data, does not exist for Tactical daggers because they are not trivial, the multilevel gameplay and the fast branching game tree.
• Generalization of the rules of the game to create its infinite, multidimensional variations.

Afterword

The creation history and information about the authors can be found on the project page , and there you can find possible restrictions on the copyright of the derivative activity. The authors will be happy to help with the translation of the remaining Russian text into English on the main page of the project.