Magic the Gathering is the most complex game of all

Spektrum der Wissenschaft

2.3.2020

Translation: machine translated

Surprise for algorithmic game theorists: they would never have dreamed that a game could be so complex. However, "Magic" can sometimes overwhelm computers, as a recent research paper shows.

Whoever was in Las Vegas in September 2018 could easily feel transported to the popular TV series "The Big Bang Theory": In one room, 24 grown men were battling each other with colourful fantasy playing cards depicting magical creatures and spells. It was actually the annual "Magic: The Gathering" world championship, in which players compete for prize money totalling 300,000 dollars.

In the meantime, the card game has also captivated many people from a scientific point of view, as it seems to be overturning decades-old beliefs of game theorists: Apparently Magic, with its many cards, complicated rules and ingenious strategies, is more of a challenge for computers than computer scientists thought possible.

The main interest of algorithmic game theorists is to calculate winning strategies for ongoing games. The more difficult it is for a computer to predict the outcome of a game, the more complex computer scientists categorise a game. Magic seems to stand out in a special way compared to other games: As the independent researcher Alex Churchill from Cambridge in the UK has now published with Stella Biderman from the Georgia Institute of Technology in Atlanta and Austin Herrick from the University of Pennsylvania in Philadelphia in a paper published on the preprint document server ArXiv work, the outcome of a Magic duel cannot always be predicted - making it the most complex of all known games to date.

In order to distinguish between different levels of difficulty, theoretical computer scientists categorise problems into so-called complexity classes. The decisive factor here is how long a computer needs - if it can manage it at all - to solve a task. For example, if you want to break down a number into its prime factors, the computing time required increases exponentially with its size. The opposite operation, i.e. multiplying two prime factors, is much simpler: according to the latest investigations, the computing time increases with n log(n), where n is the length of both factors.

For extremely large numbers, there is therefore no efficient way to decompose them into their prime factors, while it is very easy to check the result. Such problems are known in computer science as NP problems.

The scheme can also be used to evaluate the complexity of a game. For example, during a game of chess that is about to end, a computer can calculate whether and how the colour white can still win. All it has to do is go through all the possible moves. This may sound rather complicated, but the limited playing board means that a computer can complete this task in a short time. Because most real games (i.e. those that people actually play and are not just artificially constructed) are not really complex, computer scientists have hardly been interested in them. In fact, experts previously assumed that there is no real game whose complexity reaches the NP class.

Surprise for game theorists

However, as Churchill and his two colleagues have now shown, this is the case with Magic. They even suspect that the trading card game could be even more complex. To come to these conclusions, the researchers used a common concept in theoretical computer science: a so-called Turing machine. This computer model, introduced in 1936 by British scientist Alan Turing, simulates the way classical computers work.

It consists of a tape that is divided into individual fields and a head that reads the fields and describes them if necessary. The machine can move the tape to the left or right to reach the desired fields. It thus represents what mathematicians call a function: It converts numbers into other numbers according to a specific, unambiguous rule. A typical excerpt from a programme for a Turing machine, for example, reads: "If the machine is in state 3 and the field contains the number 0, then overwrite it with a 1, move to state 5 and move 4 fields to the right."

A classic question in the discussion of Turing machines is whether a machine ever reaches the end of the calculation of a problem or continues to run endlessly. As early as 1936, Turing showed that there is no way to answer this question in general for all possible algorithms.

Churchill and his team have now succeeded in proving that the question of the outcome of a Magic duel corresponds to the halting problem: this means that there are game situations in which a computer cannot calculate who will win.

The scientists arrived at the surprising result by showing that Magic: The Gathering has the same functions as a Turing machine, or "Turing-complete", as experts say. In other words, Magic can be used to simulate a Turing machine and vice versa.

To this end, Churchill, Biderman and Herrick constructed a special starting situation between two Magic players and identified the possible moves with the essential functions of a Turing machine: reading, writing and moving the tape. As a result, the game has all the properties of the theoretical computer model and can be analysed using the tools of theoretical computer science.

A game as a computer

Choosing the right game situation for Magic: The Gathering proved difficult, however. On the one hand, it had to contain enough complicated elements of the game to simulate a Turing machine, but on the other hand, it had to remain simple enough for the player to still have an overview of the possible moves. After all, there are more than 20,000 different Magic cards, each with different functions. In addition, some of them contain voluntary actions that give the player strategic freedom, which is difficult to simulate. Churchill and his colleagues therefore only included cards that have a clear effect. In their created game situation - which can certainly arise in a realistic tournament - there are therefore only forced moves; the players have no freedom of choice whatsoever.

Before the start of a Magic game, a player selects 60 cards from their collection - this selection from the huge pool of available cards and the resulting combination possibilities lead to the extraordinary complexity of the game. Once the player has made a selection, he carefully shuffles his cards and then takes seven of them into his hand. The remaining cards form their draw pile.

The cards include creatures that attack the opponent, as well as spells and artefacts. One card is drawn at the start of each round. As soon as a player has to pick up a card from an empty draw pile, they lose. Otherwise, you defeat your opponent by reducing their life points to zero or lower with targeted attacks.

In the game designed by Churchill and his colleagues, Alice and Bob compete against each other. Bob is in a situation where he has no cards in his hand and his draw pile is empty - so he is on the brink of defeat. However, he controls all the creatures on the table. Alice can therefore only try to attack Bob's creatures with the cards from her deck.

This initial situation allows the researchers to identify the game with a Turing machine. In this model, the creatures on the table correspond to the band: there is a creature on each square, with its power and toughness values indicating how much damage it does and what it can take. Magic also has five different "magic" colours that characterise a card. In the game devised by Churchill and his colleagues, white or green creatures appear with the same strength and resistance values (for example 2/2 or 3/3).

In the initial state, the tape is arranged so that the read head rests on the weakest creature (2/2); to the right of it are all white creatures in order of strength and, similarly, all green creatures to the left. A white creature with the values 5/5 is therefore on the third space to the right of the head. The type of creature is indicated by a symbol on the square.

The various functions of the Turing machine are initiated by playing Alice's cards: To move the ribbon to the right or left, Alice must play a card that deals damage to all creatures of a certain colour. But what if a creature dies in the process? Churchill and his colleagues have made private pension provision for this eventuality: one of Bob's cards is the Moderlungen Reviver, which replaces a dead creature with a new one of the same strength. This also explains how the head of the Turing Machine reads and rewrites a field: namely by Alice killing a creature and Bob then reviving it.

Crucial to the whole process is the Artificial Evolution card, which allows a player to modify the actions of other cards. For example, while the Fashion Lung Resurrector only resurrects clerics as zombies, Artificial Evolution allows you to replace the zombie with any other creature. According to Churchill, it is precisely this ability that characterises Magic: The Gathering: "For a game to have the same complexity as Magic, a player needs to be able to control or programme it during a game in the way that Artificial Evolution allows," he shares.

With this card selection, the game between Alice and Bob has all the capabilities of a Turing machine. "If you choose your favourite maths problem, you can create a Magic game situation that calculates this problem by choosing the right cards," explains Stella Biderman, co-author of the paper. However, this is very time-consuming: First you have to translate the task into the language of a Turing machine, which is already quite complicated, and then find the right selection and arrangement of Magic cards that corresponds to the problem. However, once you have found the right starting situation, all you have to do is let Alice and Bob get started; their forced moves then correspond to the individual calculation steps. As soon as the game between them is over, the solution to the problem can be read out.

Churchill and his team have designed the game in such a way that Bob cannot win. Therefore, the Turing machine only stops when Alice wins, otherwise it continues to run forever. Such situations can actually arise in real Magic games. There is even a rule according to which a game ends in a draw if moves are repeated over and over again.

In total, three situations can occur in the game between Alice and Bob: The cards correspond to a problem that a Turing machine can solve, such as the task of calculating "2 + 2". In such a case, Alice will win the game. On the other hand, the game could represent an unsolvable problem, such as "calculate the natural number x for which x2 = 2". Since such a number does not exist, the Turing machine will continue to run forever, so the game will end in a draw. However, there is also a third possibility: The cards could represent something that you don't know whether it can be solved or not. An example of this would be "Calculate a pair of prime twins (i.e. two prime numbers with a difference of 2) that are greater than 10500,000". Because mathematicians do not yet know whether prime twins of this size exist, it is also uncertain whether the Turing machine will ever hold.

If a computer is to predict the outcome of the game between Alice and Bob, it must solve the halting problem for Turing machines. For many situations, as in the first two examples mentioned above, this is not a problem. However, there are also games in which the outcome is unclear, as in the last case. Overall, therefore, no algorithm can predict how, whether and when the game between Alice and Bob will end for any given duel - even though every move made by both players is forced. The outcome of a game therefore only depends on which creatures Bob controls at the beginning and in which order Alice draws her cards.

The researchers were able to show that their imagined game situation can actually occur in a realistic duel - and is not just an artificial construct. They also assume that other game situations can lead to similar dead ends. The authors write that the game therefore reaches at least complexity level NP. However, to check whether it is perhaps even more complex, a different approach must be taken.

However, the result remains astonishing from a game theory perspective, even if it may come as less of a surprise to Magic players: some of them have long boasted that they have mastered an extremely complicated game. Now they can officially claim to play the most complex game in the world.

Try it out now

Spectrum of science

We are a partner of Spektrum der Wissenschaft and want to make scientifically sound information more accessible. Do you like the articles from Spektrum? Then follow Spektrum der Wissenschaft or subscribe to the magazine and support scientific journalism.

[[small:]]

Spektrum der Wissenschaft

Wissenschaft aus erster Hand

dirdjaja@spektrum.de

Experts from science and research report on the latest findings in their fields – competent, authentic and comprehensible.

Follow

---

Toys

Follow topics and stay updated on your areas of interest

Follow topic

These articles might also interest you