It’s so complicated that even if you have all the information beforehand, you can’t really know who will win.
Magic the Gathering is a popular and famously complicated trading card game about magical combat. Essentially, you have cards with creatures, spells, and other resources that you use to defeat your opponent. Formally, it is a two-player zero-sum stochastic card game with imperfect information — which puts it in the same category as games like poker and hearts.
For computer scientists, a matter of interest is figuring out whether problems can be computable or not — and this includes games. Take tic-tac-toe for instance: it’s a really simple, computable game. Have two algorithms go at it for a bazillion games, and they will come up with a bazillion draws. But let’s move on to something more complicated, like chess. In theory, chess is computable; you can solve it. However, actually having the resources to do that is a whole new problem. While chess algorithms can handily defeat the best human players in the world, we’re still very, very far from actually solving chess.
Nevertheless, from a complexity point of view, chess has a solid limit on its complexity, given by the size of the boards and the pieces. Most real-world games have finite limits on their complexity, but a few real-world games have
been found to have non-trivial complexity, including Dots-and-Boxes, Jenga, and Tetris. Magic the Gathering, as it turns out, is more complex than all of them.
To prove this, researchers first translated the powers and properties of all 20,000 Magic cards. The mechanics of some of the cards require input from the player — such as naming a number or choosing whether or not to play an action. At some point the study reads:
”For example, Kazuul Warlord reads “Whenever Kazuul Warlord or another Ally enters the battlefield under your control, you may put a +1/ + 1 counter on each Ally you control.”
This makes things very weird, since researchers’ goal was to essentially load the game on a Turing machine — essentially, create a Magic the Gathering playing engine. So for the purpose of this study, these cards were eliminated. Even so, the game remained incredibly complex.
The team showed not only that Magic is the most complex real-world game we know of, but also that is non-computable, unlike games such as chess.
[panel style=”panel-default” title=”Turing Machine and the Halting Problem” footer=””] In 1936, Alan Turing attacked the so-called Halting problem. The Halting problem asks: given an input and an arbitrary computer program, will the program stop (halt), or will it run forever? Turing proved that algorithms can’t determine the answer, making the problem non-computable.[/panel]
“This construction establishes that Magic: The Gathering is the most computationally complex real-world game known in the literature,” researchers write. Simply put, there is no one winning strategy,” researchers continue.
“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 full complexity of optimal strategic play remains an open question, as do many other computational aspects of Magic. For example, a player appears to have infinitely many moves available to them from some board states of Magic,” the study continues. It’s not entirely clear whether a real-world game can have infinitely meaningful moves, but it indicates tremendous computational complexity.
In addition to giving Magic the Gathering players boasting rights, the work itself is significant for a number of reasons. For starters, having a card game where there is no clearly defined winning strategy is impressive. Also, this gives a signal to all computer scientists attempting to model games: Magic is a tough nut to crack and does not seem to behave according to common assumptions.
“This is the first result showing that there exists a real-world game for which determining the winning strategy is non-computable.”
“We conjecture that optimal play in Magic is far harder than this result alone
implies, and leave the true complexity of Magic and the reconciliation of Magic with existing theories of games for future research,” the study concludes.
The study has been published in arXiv.
