Anyone who’s ever tried to play Magic: The Gathering or listened to a friend explain it to them has had to reckon with the learning curve of all its intricate rules and even more confounding cards. Human players might not be alone in feeling overwhelmed: A new research paper argues that the game is so complex that there are even cases where a computer theoretically wouldn’t be able to figure out how to win.
A group of researchers argues that Magic: The Gathering is so complex there are cases in which it would be impossible for a computer to figure out a fool-proof way to win. “This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” they write.
The team, which includes Alex Churchill, a board game designer, Stella Biderman, a researcher at the Georgia Institute of Technology, and Austin Herrick, a senior analyst at the University of Pennsylvania’s Wharton Budget Model initiative, wanted to see just how complex the fantasy card game was from a computational standpoint. What they ended up finding was that Magic: The Gathering isn’t just more complex than most other games, it’s actually noncomputable in some cases. It’s yet unclear just how many of those cases there are, but there are currently conceivable matches where there’s no way an algorithm can figure out the optimal path to victory.
The research was based on coding two decks of legacy Magic: The Gathering cards, which span the entire history of the game excluding certain banned cards, and creating a mathematical model to interpret the cards within the context of the game’s rules to return future board states based on which cards are played and in which order. As you can see from the following deck list, the cards used are some of the more complex ones from the game’s history.
Cleansing Beam, for example, deals two damage to its target creature and each other creature that it shares a colour with it. Coalition Victory, meanwhile, automatically lets you win the game if you control a land of each basic land type and a creature of each colour. Then there’s Illusory Gains, an aura that automatically attaches to each new creature an opponent plays and brings it under your control. These card effects, combined with others, created enough alternative possible courses of action that the research team’s model was unable to return a result.
In chess it’s extremely resource intensive to compute how one side can win. After the first two moves in chess, there are 400 different possible outcomes. After the sixth, there are 121 million. It’s still theoretically possible to compute, though. Based on the noncomputable cases these researchers found, that’s not the case in Magic: The Gathering, despite the fact that it’s a two-player, zero-sum game using premade decks of cards, making it unique among all the other games currently studied in the field.
“This is the first result showing that there exists a real-world game for which determining the winning strategy is noncomputable,” the authors write.
Of course, this doesn’t apply to just any game of Magic: The Gathering. The researchers explored a very specific set of cards and starting hands based on certain requirements. For example, the decks “exclusively use cards with mandatory effects,” which means they don’t include cards where a player would choose from varied possible outcomes. But all of the cards used are tournament legal within the rules of the legacy format.
While the study has potential implications for game theory and computer science research, it also lays clear the sheer potential for discovery in Magic. “The full complexity of optimal strategic play remains an open question, as do many other computational aspects of Magic,” they authors write. “For example, a player appears to have infinitely many moves available to them from some board states of Magic…[which] has the potentially to highly impact the way we understand and model games as a form of computation.”
Ultimately it seems fitting for a game based in a multiverse whose rules are infinitely malleable.