Wonderful figurines
The legendary Tetris was created in the 80s of the last century by Alexey Pajitnov. Mathematician
Pajitnov released one of the first versions of the game on the Soviet microcomputer "Electronics-60"
The goal of Tetris is to move and rotate fallinggeometric shapes to form complete rows at the bottom of the playing field, scoring points. From a practical point of view, this is a game of reaction speed and concentration, but mathematicians look at it from a different angle. Scientists analyzed the computational complexity of the Tetris algorithm and determined that it belongs to the class of NP-complete - non-deterministic polynomial; there are no effective solution algorithms for such things.
The key problem is that the amount offor finding a solution to the computation grows exponentially with an increase in the number of variables (problem size). For example, if there are four parameters, then 16 iterations are needed, and if 100, then 2 ^ 100, which is more than atoms in the Universe (!). A typical computer, when properly tuned, can do several billion of these iterations per second. Accordingly, he can easily solve small NP-problems by enumeration, and when the variables become noticeably more than 15, he will stop solving.
As for Tetris.The task size of the classic game is small: at a separate step, there is a current landscape in the glass (playing field) - this is a parameter, it does not significantly affect the amount of calculations. There is information about the current and next figure - these are two groups of variables: for each figure there are a maximum of four (although for a square - only one) orientations in space and a maximum of 10 coordinates of the "landing" of the figures. Each move has 40 states, two have 1,600, there is no more information, this is a small NP problem. Although Tetris can be complicated: increase the number of cells to 100 and make sure that the player knows not only what the next figure will be, but also a hundred of the next ones, then there would be problems.
You don't know other NP-complete games eitherfrom hearsay: minesweeper, sudoku, tag and even a non-commercial version of Super Mario. Despite the simplicity of their rules, under certain conditions their dimension increases, the computer cannot offer an ideal solution. Why do mathematicians care? Because choosing the best route, optimizing a process or schedule are also NP class problems.
Classic "Mario" looked like this
Logic games are an extremely convenient testing ground fortesting algorithms and their software implementation. Puzzles are most often “pure”, without various kinds of exceptions to the rules that are inherent in practical problems. The state space of such problems has an adjustable dimension, and the properties do not change when scaling (for example, tags 2x2, 4x4, 3x6). All states are described in the same way. The mathematical description of puzzles, as a rule, is also not as complex as those of life problems.
The time of "quantum" toys
The same problem about a backpack (how to fit more thingsin a limited space) is quite reminiscent of a game of Tetris, and the effective result will be useful for logistics companies, because it will allow them not to waste resources. If a “polynomially fast” algorithm is found for any of these problems or games, then any other problem from the NP class can be solved just as “fast”. In theory, quantum computers will help with this, but so far there are only prototypes of these computers of the future. In 2018, a new concept was even invented to describe the current state of production of quantum processors - the era of NISQ (noisy intermediate-scale quantum era), or the time of sub-quantum technologies.
While scientists are working to improve quantumprocesses, company executives are looking for modern analogues that help optimize the work of production. Such a “substitute” has become quantum-inspired algorithms that find a 95-99% optimal solution on conventional computers. In Russia, QuSolve is doing this - the tasks the company is working on belong to the NP class, and mathematicians develop and improve algorithms for solving business problems. In QuSolve, to test their own solver (solver), they used tags, which helped to find a couple of errors in the algorithm and make additions to the interface of the software package.
Are modern scientists really doing nothing butAre you thinking about how to improve and optimize everything? Of course not. In their free time, they continue to invent games. The developers have already been able to turn most games into NP, adding a little magic of quantum physical phenomena.
This is how quantum technologies have appeared over the past 10 years.checkers, quantum sea battle and quantum tic-tac-toe. Quantum chess has gained particular popularity, in which tournaments are even held, and the champion is awarded the title of grandmaster. Most of the new "quantum games" are built on the fundamental principle of quantum mechanics - superposition.
For example, chess pieces can be inseveral places on the board at the same time, which means it is more difficult to defend and attack - this makes the game unpredictable and spectacular. In 2016, they even filmed a short film that showed a game of quantum chess between Stephen Hawking and Paul Rudd, an actor known for his role as Ant-Man in the Marvel Cinematic Universe.
Game screenshot. This is what the online board looked like in the game between Hawking and Rudd. Then the actor beat the legendary physicist
We don't know if these games will be like this in the futureas commonplace as ordinary tic-tac-toe, tetris and tag, but they will definitely inspire mathematicians to create unique algorithms for solving practical business problems and developing technology. There is no doubt about it.
Read more:
The shape of the Milky Way is not at all what we thought all along, scientists have found
Two super-Earths found on the edge of the habitable zone: one of them has a comfortable temperature
Found a black hole that destroys a star record close to Earth