Magic: The Gathering is a card game in which wizards cast spells, summon creatures and use magical objects to defeat their opponents. During the game, two or more players collect a deck of 60 cards with different forces. Decks are collected from a pool of over 20,000 cards created as the game progresses. Although Magic: The Gathering is similar to role-playing fantasy games like Dungeons and Dragons, it has many more cards and more complex rules than other card games.

Which leads to an interesting question: How difficult is MTG, if you compare it with other real games (that is, those in which people actually play, and not some theoretical ones)? Immediately make a reservation, the complexity here means not the complexity of understanding the gameplay, but complexity as the depth and versatility of the game.

How complicated is Magic: The Gathering? More difficult

The answer was given by the work of Alex Churchill, an independentboard games researcher and designer from Cambridge, UK; Stella Biederman from the Georgia Institute of Technology and Austin Herrick from the University of Pennsylvania.

His team measured the computational complexitygames, encoded it so that it can be played on a computer or Turing machine. "This design has established that Magic: The Gathering is the most computationally challenging 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 a problem can be solved in principle. For example, deciding whether two numbers are relatively simple (in other words, their greatest common divisor should be greater than one) is a task that can be completed in a finite number of well-defined steps and, therefore, calculated.

In the usual game of chess, you can alsocomputing find a solution to whether whites have a winning strategy. The process involves checking every possible sequence of moves to see if White can win.

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

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

In this case, the decision whether twonumbers are relatively simple, can be found in several steps that are proportional to the polynomial function of the input numbers. If the input value is x, the most important member of the polynomial function will be in the form Cx ^ n, where C and n are constants. This is class P, which means polynomial time.

On the contrary, the chess problem must be solvedby 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 Cn ^ x, where C and n are 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 tasks for which there are no algorithms. They are called noncomputable.

Find out which category of difficultygames are not easy. Most real-world games have limited difficulty limits, such as the size of the playing field. And this makes many of them trivial in terms of complexity. “Most of the research in the field of algorithmic theory of real games mainly concerned generalizations of popular games, not real versions,” Churchill said.

Thus, only a few real games have a non-trivial complexity. These include “Sticks” (or “Points and Squares”), jenga and tetris.

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

They then played the game between two players.by Turing machine. And, finally, they showed that determining which player has a winning strategy is equivalent to the “stop problem” known in computer science.

This is the problem of determining whetherA computer program with a specific input job or will work forever. In 1936, Alan Turing proved that no algorithm can determine the answer. In other words, this task is not computable.

Therefore, the result of Churchill shows thatThe outcome of the Magic: the Gathering game is incalculable. “This is the first result that shows that there is a real game for which the definition of a winning strategy cannot be calculated,” scientists say. This is an interesting paper that raises important fundamental questions of game theory. For example, Churchill and co-authors say that the leading formal game theory assumes that any game must be computable. Magic: the Gathering does not meet the assumptions that computer scientists usually make when modeling games.

Have you played this game? Tell us in our chat in Telegram.