Magic: The Gathering might be the most complicated game ever made, researchers suggest

Magic: The Gathering is too complex for computers to handle, according to a group of researchers who found high-powered machines struggle to analyse matches of Richard Garfield’s collectible card game.

The paper by researchers from the UK and US declares that “Magic: The Gathering is Turing-complete”, stating that certain two-player games of Magic simply can’t be computed in a way that could ever predict a winner due to the vast number of possibilities available.

This supposedly makes Magic more complicated than chess, which can have millions upon millions of potential outcomes but can ultimately be calculated.

The researchers used standard-size 60-card decks built in Magic’s Legacy format, which allows cards from any era of the game to be used. If you’re interested in recreating their computer-busting decklist, the whole thing is detailed in the paper and showcases some of Magic’s more mechanically complicated rules. 

Among the cards mentioned by name in the paper is Menacing Ogre from the Planechase expansion, the effect of which requires both players to secretly choose a number, before revealing their numbers at the same time – the person who picked the higher number gains extra strength and defence at the cost of health points. That rule alone can make predicting the state of the game impossible.

Other examples include instant-win cases such as Coalition Victory, which grants immediate victory if the player has a basic land of every type and creature of every mana colour on the field – if that happens and doesn’t ‘halt’ the Turing machine running the game, the computer will enter an “unbreakable deterministic infinite loop” and run forever.

“This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” the researchers summarised. “In addition to showing that optimal strategic play in Magic is non-computable, it also shows that merely evaluating the deterministic consequences of past moves in Magic is non-computable.”

The team added their belief that Magic: The Gathering is the first example of a ‘real-world’ game where a winning strategy cannot be calculated, and said that exactly how complicated Magic is remains unknown.

“The full complexity of optimal strategic play remains an open question, as do many other computational aspects of Magic,” they said. “For example, a player appears to have infinitely many moves available to them from some board states of Magic. Whether or not there exists a real-world game of Magic in which a player has infinitely many meaningfully different moves available to them has the potentially to highly impact the way we understand and model games as a form of computation.”

In fact, Magic might never be able to be solved by a computer, with the researchers saying that its non-computable difficulty may be the ultimate example of complexity in games.

“Whether or not it is possible for there to be a real-world game whose computational complexity is strictly harder than [Magic] is an interesting philosophical question,” they concluded.

“If not, then this conjecture would imply that Magic: The Gathering is as hard as it is possible for a real-world game to be.”