# Magic: The Gathering officially recognized the most difficult game in the world

Magic: The Gathering - is a card game in which the sorcerers Affected spells, summon creatures and use magic items to defeat your opponents. During the game, two or more players gather on the deck of 60 cards with different forces. Deck assembled from a pool of more than 20 000 cards, created with the development of the game. Although the Magic: The Gathering is similar to the role-playing fantasy games such as Dungeons and Dragons, it is much more cards and more complex rules than other card games.

Which leads to an interesting question: how complex of MTG, if we compare it with other real games (ie those in which people actually play, rather than what some theoretical)? Just specify a complexity here means not understanding the complexity of the gameplay, and the complexity of the depth and complexity of the game.

## How difficult is Magic: The Gathering? Harder does not happen

Answer given work Alex Churchill, independent researcher and designer of board games from Cambridge, UK, Stella Biederman Georgia Institute of Technology and Austin Herrick of the University of Pennsylvania.

His team measured the computational complexity of the game, encode it so that it can be played back on a computer or Turing machine. "This design is found that Magic: The Gathering - the most computationally complex real-world game, known in the literature," the scientists said. But first, a little background. A very important task in computer science is to determine whether the problem can be solved in principle. For example, the decision whether the two numbers are relatively simple (in other words, their greatest common divisor is to be more than one) - a task that can be completed in a finite number of well-defined steps and, consequently, to calculate.

In a normal game of chess can also be the method of calculation to find a solution if they have white winning strategy. The process involves checking every possible sequence of moves, to see whether the white to win.

But although both of these problems are computable, the resources needed to address them, vary widely.

That's where the concept of computational complexity appears. This ranking is based on the resources needed to solve problems.

In this case, the decision on whether the two numbers are relatively simple, can be found in a few steps, which are proportional to a polynomial function of the input numbers. If the input value is x, the most important member of a polynomial function will be in the form Cx ^ n, where C and n - constants. It belongs to the class P, which is polynomial time.

On the contrary, a chess problem should be solved by brute force and the number of steps required increases in proportion to the exponential function of the input data. If the input is x, the most important member of the exponential function is given by Cn ^ x, where C and n - constants. Here we are dealing with a category of greater complexity EXP, or exponential time. In addition there are various other categories with different complexity, as well as the tasks for which there are no algorithms. They are called uncomputable.

To find out which category includes the complexity of the game - not a simple matter. Most real games have limited complexity limits such as the size of the playing field. And it makes many of them trivial in terms of complexity. "Most of the research in the field of algorithmic theory of real games are mainly concerned generalizations of popular games and not the real version," Churchill said.

Thus, only a few real games are non-trivial complexity. This includes the "sticks" (or "Dots and Squares"), Jenga and Tetris.

The work of scientists has shown that the Magic: the Gathering is much more complex than these three. counting method, in principle, is simple. Churchill and his company began to transform the forces and properties of each card in a set of steps that can be encoded.

Then they played a game between two players on a Turing machine. And finally, we have shown that the definition of any of the players have a winning strategy, is equivalent in computer science known "problem stopping."

This is the problem of determining whether a computer program finishes with a certain input work or will work forever. In 1936, Alan Turing proved that no algorithm can not determine the answer. In other words, this problem is not computable. Therefore Churchill result shows that the determination of the outcome of the game in Magic: the Gathering can not be calculated. "This is the first result, which shows that there is a real game, for which the definition of a winning strategy defies calculation," the scientists say. This is an interesting work that raises important fundamental questions of the theory of games. For example, Churchill et al say that the leading formal game theory assumes that every game has to be computable. Magic: the Gathering does not correspond to assumptions that usually do computer scientists at the game simulation.

Have you played the game? Tell us in our chat in the telegram.