[Best of 2019] Why ‘Magic: The Gathering’ is AI’s toughest challenge

Games make the perfect teaching environment for developers to train machine learning models in, but which game produces the strongest AI? You can put your money on DeepMind’s AlphaGo or OpenAI’s DotA 2-playing machine, but we’ll take whichever one is the first to master Magic: The Gathering – humanity’s hardest game.

A trio of scientists led by independent researcher Alex Churchill recently published research in pre-print archive arXiv that appears to establish that Magic: The Gathering, a collectible card game, is “the most computationally complex real-world game known” in scientific literature. While anyone whose ever tried to casually get into tournament Magic can anecdotally attest to the truth in that statement, the scientists used science to come to their conclusions. And in the coolest way possible: they created a Turing Machine out of Magic: The Gathering cards.

A Turing Machine is a device that can universally compute – in other words it’s a method for triggering the kinds of classical mathematics involved in performing computations. In the case of Magic: The Gathering, the researchers appear to have adapted and built upon Churchill’s earlier work. The essence of the card-based Turing Machine is that, with some specific setup, you can make it perform a Magic: The Gathering rules-legal function similar to that of a PC computing with ones and zeroes.

The Turing Machine made of Magic cards is actually a tournament-legal, playable strategy. The researchers wrote:

While there are practical difficulties involved with correctly setting up the necessary board state, such as running out of space on your table, a sufficiently tenacious player could set up and execute this construction in a real-world tournament.

The following table shows a possible 60-card deck that could trigger the construction.

But, as it turns out, this particular setup results in a potential outcome (at scale) that is ‘undecideable.’ It can’t be computed accurately.

According to the researchers:

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.

While it’s obvious that not every Magic: The Gathering game results in a non-computable outcome, the fact remains that it may be the only real-world game in which the possibility exists within the framework of the rules.

What does this mean for the fields of game theory and artificial intelligence? Like Magic: The Gathering itself, there are no easy answers. The researchers concluded:

Magic: The Gathering does not fit assumptions commonly made by computer scientists while modeling games. 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 implications of the fantasy card game’s difficulty could turn out to be pretty big. How do you program an AI to solve a problem when there’s no way to compute the optimum strategy accurately? Magic: The Gathering may hold the answers.

TNW Conference 2019 is coming! Check out our glorious new location, an inspiring lineup of speakers and activities, and how to be a part of this annual tech bonanza by clicking here.