Quantum morris

The circle of dancers squirmed like a living creature. But among them was an empty seat and it moved. She knew this place was for her. Miss Tenet forbade her. But when did she say that? And then, where to understand it. What does she even understand? When did she last dance? The dance was in Tiffany's blood, he beckoned her. Six dancing is not enough!
... The dancers did not take their eyes off her, and she jumped up and circled between them, each time finding herself where no one was.

Sir Terry Pratchett " Winter Affairs Master "

Despite all its clumsy, " Tic-tac-toe " is the cornerstone of the world of board games. The principle " N in a row " is so simple and natural that it was independently invented by several ancient peoples at once. In China and Japan, he laid the foundation for such games as Renju and Hasami Shogi , in ancient Europe he spawned the Mill , the progenitor of Alquerque , and, ultimately, the whole variety of modern drafts .
')
In its original form, "Tic-tac-toe" does not seem like a game as something interesting. In fact, a win-win strategy for each of the players in this game is completely obvious, and to win, with the right game, is absolutely impossible. Such a game can attract younger schoolchildren to themselves, but not serious players. However, there are several ways to fix it ...

And then the cat?

When it comes to improving the “Noughts and Crosses”, the first thing that comes to mind is an increase in the size (or dimension) of the playing space. Indeed, the game on the 3x3x3 board is no longer so trivial, and among the many variations of the game on the big board there are disciplines considered professional (although, in this case, we are talking about building five figures in a row). There are also less obvious ways to improve the game. So, using gravity as one of the gaming factors, we get a very entertaining game “ Four in a row ”, and a simple change in the victory condition (the player who had to build a series of three figures loses) gives us “Losing Tic-Tac-Toe”, win which is not easy.

In 2006, Allan Goff came up with another way to radically improve the game. He did this for a reason, but in order to illustrate such complex concepts of quantum mechanics as "superposition", "entanglement" and "convolution". In his proposed version of the game, each player, instead of putting his own cross or zero, makes two half-moves in different positions of the playing field. The figure added to the board is equally likely to be present in two positions at the same time. In the index information is stored on the sequence of moves of players, later used in the resolution of collisions.


As long as the figures are present on the board only in the form of half-moves, we cannot say exactly which of the positions each of them is in. Perhaps this is not the most successful metaphor of quantum mechanics, because within this model, each figure can be “smeared” by no more than two possible arrangements (there are also some difficulties with determining the winner, which I will discuss below). In 2010, JN Leaw and SA Cheong offered a more complex version of the game, in which each turn is a vector in nine-dimensional Hilbert space. A brief description can be found here .


In any case, the concept seemed interesting to me. Board games are basically simple. Figures are put on a board, move, turn, take away other figures - all this is very easy to implement. But there are "raisins", the complexity of which literally "rolls over." In Chess , these are the concepts of the Shah and the Mat , in Checkers - the “rule of the majority”, in Go - the mutual influence of the figures. The concept of "superposition" and related "entanglement" - one of these "highlights".

Unraveling confusion

If the case were limited to only half-moves, there would be nothing interesting in “Quantum Noughts and crosses”. To win, it is necessary to ensure the absolute presence of the figures in the given positions! How do semi-moves turn into full-fledged figures? It's time to figure it out. If you fill the board with semi-moves long enough, sooner or later a situation arises, like the following:


There was a conflict, a kind of paradox - a contradiction in the source data. In the end, the location of each figure must be precisely defined. All half-moves should be “rolled up”, but there are two fundamentally different possibilities of such a “bundle”. In one of these cases, the game ends.


The player who closes the cycle of interdependencies is guilty of the "paradox". For this reason, the choice of the convolution option is given to his opponent. In our case, the cycle was closed by “crosses”. This means that the "zeroes" will avoid defeat. They will simply choose "from two possible worlds" the one in which the "crosses" have not yet won. But there are situations in which nothing depends on the choice of the convolution option:


What you do not choose here, the final result for the "zeroes" is the same - they lost. Possible and degenerate situation. Any player can make two half-moves in the same area of ​​the board. This is the shortest possible collision. Since it implies a “choice” of two absolutely identical variants, such a sequence of half-moves is actually equivalent to a full run in this field:


Pay attention to how the “crosses” move is forced out from the selected field. Each cell of the board can contain the result of no more than one “full” move. Such “crowding out” can spread further along the chain (in fact, along the tree). In my opinion, such moves are somewhere on the verge of a foul. They are too strong. Such a "deterministic" move is equivalent to the usual move in "Noughts and crosses" and, in addition, allows you to "push out" the enemy from the selected position. In most of the variants of my implementation of “Quantum tic-tac-toes” (6 out of 10), I forbade the execution of “deterministic” moves.




There is still one not considered question. The game ends when one of the players manages to build a line of crosses or zeros (of course, this is rarely the case in the usual Tic-Tac-Toe), but in our crazy quantum world, crosses and zeros can build their lines at the same time! Who is the winner?


Allan Goff proposes to re-use the indices used to number the moves. For each line constructed, a maximum index must be found. The one who has this index was less, wins. Since, in his work, he uses the continuous numbering of moves (X1, O2, X3, ...), if there is a line, there will always be a winner. It is easy to see that I use a different numbering scheme and, in my case, draw again.

What made me move away from the canons? Two considerations. First, the through numbering scheme gives a very serious advantage to the first player. In my opinion, the game balance is much more important than the hypothetical possibility of getting a draw (seriously, in Quantum Noughts, a draw is a rare situation). More importantly, the continuous numbering (and the associated method for determining the winner) is completely unacceptable for Quantum Morris, which will be discussed below. There, each of the players, all in all three figures.

Everybody is dancing!

Morris Dance is the oldest English custom associated with fertility rituals. Those who wish to feel the spirit of this action are happy to recommend the “Winter Masters” by Terry Pratchett. About the dance itself there is told in passing, but from the heart! As part of our narration, the connection of this custom with a whole family of board games, incredibly popular in medieval Europe, is more important. The younger game of the family ("The Dance of Three Men ") is another way to "improve" the noughts and crosses. In fact, it is a link between them and later games with moving figures such as Fox and Geese or Alquerque .

The game is based on a very simple idea: if you could not build a row right away, you can still win by moving the already laid out chips in turn! To make it where to move, each player uses only three figures (this is enough to draw a line). In the older games of the family, such as " Dance of nine men ", the player who built the row ("the mill") has the right to irretrievably grind any opponent figure already put on the board. In our case, since there are only three figures on each side, the loss of any of them means an unconditional defeat. Two figures are not enough to build a series!

From here to "Quantum Morris" is just one step! Although the problem of “no one's death” is no longer so acute in “Quantum Noughts and Crosses”, the game itself remains too fleeting. Limiting the number of figures to three (on each side) and moving them after being put on the board will help to “stretch” the game, adding to it entertainment and surprises.



It is easy to see that only small “half-figures” move. It is also possible to “split” a complete figure into two half-figures, with one moving to another position. A large figure cannot be moved. As in the "Quantum noughts", there is the possibility of "deterministic" moves. In addition to “resetting” two half-moves into one cell, we can “merge” the half-shapes by moving one of them to the other. I still consider such moves too strong and prohibit them in terms of game variants.


"Quantum tic-tac-toe" is perhaps not an ideal, but a very good illustration of the ideas of quantum mechanics. This game attracts attention. It is used during programming competitions , questions on this topic appear periodically on StackExchange . Currently, it is not difficult to find its software implementation. It is designed for both Android and iOS . Particularly impatient can play directly through the Web-interface . Only one "Tic-Tac-Toe" set of "quantum" games is not limited. As a bonus, I can also recommend this game .

All with a Friday, Lord!