Shuffling the cards

It’s possible to build a Turing machine within Magic: The Gathering

Just arrange a series of cascading triggers so players no longer have any choice.

Jennifer Ouellette – Jun 23, 2019 9:00 am | 99

Assemble just the right deck, and draw just the right cards, and you'll get the equivalent of a universal Turing machine within the game, a new study finds. That makes it the most computationally complex real-world game yet known. Credit: Gordon Chibroski/Portland Press Herald/Getty Images

Consider this hypothetical scenario: Bob and Alice are playing a game of Magic: The Gathering. It's normal game play at first, as, say, Filigree robots from Kaladesh face off against werewolves and vampires from Innistrad. But then Alice draws just the right card from her customized deck, and suddenly Bob finds himself caught in the equivalent of a Turing machine, the famed abstract device that can simulate any computer algorithm. Thanks to the peculiarities of the rules of Magic, Bob can now only finish the game when he meets whatever condition Alice has programmed her in-game algorithm to accomplish—for example, to find a pair of twin primes greater than one million.

It may be a highly unlikely scenario, but a recent paper posted on the physics arXiv proves that it's possible in principle to build a simple computer within this massively popular tabletop game using just the right combination of Magic cards. While the inputs must be pre-programmed, "Literally any function that can be computed by any computer can be computed within a game of Magic," said co-author Alex Churchill, a longtime Magic fan who has been working on the problem for several years.

Furthermore, he and his co-authors—Stella Biderman of the Georgia Institute of Technology and Austin Herrick of the University of Pennsylvania—have concluded that Magic might be as computationally complex as it's possible for any tabletop game to be. In other words, "This is the first result showing that there exists a real-world game [of Magic] for which determining the winning strategy is non-computable," the authors write.

Model of a basic Turing machine, part of the Go Ask Alice exhibit at the Harvard Collection of Historical Scientific Instruments. Credit: GabrielF/Wikimedia Commons

A touch of Magic

For the uninitiated, Magic: The Gathering is a tabletop trading card game, invented in 1993 by mathematician Richard Garfield while he was completing his PhD. Players can build customized decks of 60 cards chosen from the massive collection available. They then use those cards to cast spells, use artifacts, and summon various magical creatures to defeat their opponents by draining them of "life points."

Magic shares some thematic similarities to tabletop games like Dungeons and Dragons—except, of course, Magic relies on thousands of cards (some 20 billion Magic cards were produced between 2008 and 2016 alone) and a dizzying array of rules governing game play. The authors of this latest paper prefer to think of it as a "two-player, zero-sum stochastic card game with imperfect information, putting it in the same category as games like poker and hearts."

Based in Cambridge, England, Churchill is a software engineer by day and an avid designer of games on the side. He grew up playing canasta, bridge, mahjong, and Scrabble, among others, and has well over 250 board games on his home shelves. He first discovered Magic: The Gathering while at college some 20 years ago. He's been an avid player ever since, one of the more than 20 million ardent players drawn to the expansive world-building within the game. (It's so popular that regular World Cup competitions have been held; as you'll see below, Ars UK attended the 2016 edition in Barcelona.)

"It's so many things to so many people," Churchill said of the game's enduring appeal. "Some people love to play to prove themselves the best; some love to play as a social experience; some love to play the game for the swinging with giant dragons and angels. It's got a vast amount of lore and storyline, and the artwork is incredible." It's the creative element of building one's own deck that most appeals to Churchill. "There's a lot of strategic and tactical depth, of course, but there's also a self-expression element in choosing which cards to put together," he said.

Churchill proposed the possibility of assembling a universal Turing machine from Magic cards several years ago as a means of proving that the game is "Turing complete." (You can read all the gory details at his website.) This latest work is a culmination of those earlier findings.

First proposed by Alan Turing in the 1930s, a Turing machine is an abstract concept, as opposed to a physical object, that laid the conceptual groundwork for the invention of the modern computer and basic programming techniques. As Matt Ford wrote for Ars back in 2007,

Turing machines are simple logic devices that can be made to simulate the logic of any standard computer that could be constructed. They consist of an infinite number of cells on a tape (the memory) and an active cell that is referred to as the "head." Each cell can be one of a set number of colors, and the head can have a fixed number of states. A set of rules determine how the combination of cell color and head state dictates what color should be written to the tape, what state the head should be placed in, and what direction it should move (left or right).

A universal Turing machine is one capable of running any algorithm, while "Turing completeness" is a term "used to indicate that a system has a particular degree of complexity," said Churchill. "Any Turing-complete system is theoretically able to emulate any other." Being able to determine whether a given problem can be solved in principle is a key task in computer science. If Magic is Turing complete, then there should exist within the game a scenario where it's impossible to determine a winning strategy—equivalent to the famous "halting problem" in computer science.

One way to demonstrate that a system is Turing complete is to create a Turing machine within it, and that's just what Churchill et al. have done with their work. There are three fundamental elements needed: a tape that encodes the computation; a controller to determine what action to take next based on the current state of play; and a read/write head under the control of the controller.

The odds of the precise combination of cards needed to create the Turing machine popping up in a real tournament are extremely unlikely. Credit: Flickr user: Max Mayorov

Building a deck, er, Turing machine

First, Churchill and his team encoded the various powers and properties of each Magic card into a set of steps. They used creature tokens to "encode" the "tape," color-coded (green or white) and carefully controlled for power and toughness properties, per the descriptions on the cards. Next they played out a game involving two players (Alice and Bob) within this in-game equivalent of a Turing machine.

In order to find a scenario where one couldn't predict the winner, they essentially created a rare situation where two players are forced to play specific cards. This would be perfectly legal game play, it's just highly unusual—and no easy feat. It's common in normal Magic matches to draw a forced-choice sequence of cards three or four times in a row. Churchill et al.'s in-game Turing machine merely extends that to millions of forced choices in a row. "We put in quite a lot of effort to remove all the different ways that both players in the end are normally able to interact in the game," said Churchill. "We arranged a series of cascading triggers, such that neither player ever has any choice about how to proceed."

Typically, players would have many more strategic and tactical choices over the course of the game, along with a degree of randomness—a literal luck of the draw. But once the Turing machine is set up, it's no longer the humans playing the game. "The human setting up the Turing machine needs to get things right, but once it's set up, the humans playing the game have no choice but to follow the computation where it leads," said Churchill.

"I don't think anyone in a tournament ever has assembled a combination of 36 Rotlung Reanimator creature tokens."

That said, the odds of that precise combination of cards popping up in a real tournament are extremely unlikely. "I don't think anyone in a tournament ever has assembled a combination of 36 Rotlung Reanimator creature tokens," said Churchill. Even if he deliberately built his own deck with the specific 60 cards used in the paper and took it to a tournament, the odds are still about 1 in 50,000. "So I'd need to play about 50,000 games with the deck before I'd draw the perfect hand that allows me to set up the Turing machine," he said. "But if I do, wouldn't that be a story to tell?"

Of course, achieving just the right balance between player choice and constraints is part of what makes a good game. If players can just wave their wands to accomplish anything they desire, it's a less satisfying story and overall experience. Magic seems to hit a sweet spot between too much choice and too many constraints, because there are actually two stages to playing the game. The first is building your deck, which is where newcomers especially can feel overwhelmed by the sheer wealth of options to choose from. That's why Wizards of the Coasts encourages beginners to use pre-built decks at first and then move on to building their own decks once they've gained some experience, according to Churchill.

The second stage is playing your cards against other players, and here, there are a lot of rules dictating how the game play progresses. This is also where a certain degree of randomness kicks in. "Each game is likely to feel different enough that if you lose a game, you can blame it on the cards you drew," said Churchill. "That makes people want to keep playing. It's like, 'I know my deck could do this if I draw both those cards together.'"

You complete me

So Churchill et al. have successfully demonstrated that Magic is accidentally Turing complete. Programming languages are Turing complete, along with HTML/CSS, PostScript, and PowerPoint. "Various computer games provide ways for players to implement logic gates, so it's possible to build computers in them as well," said Churchill. "But it's much, much rarer to find anything offline that's Turing complete, and it's quite possible that Magic is the only tabletop game that's Turing complete." That feat alone could make it the most complex game known so far.

When Churchill et al. talk about the "complexity" of Magic, they are not referring to the incredibly long rule book and massive collection of cards. Nor do they mean "complexity" in the sense of determining how hard it would be for an AI to defeat a human player at Magic. It's entirely possible to build an AI capable of playing a convincing game of Magic, according to Churchill. Someone could train a neural network capable of beating between 50% and 80% of players, 80% of the time. But that question has nothing to do with the current paper.

"Complexity" in this case refers to how it is understood in mathematics and computer science: namely, how difficult is it to assess a board state and determine who is going to win, or even if a winning move exists for a player? "What we've proven is that the operation of 'finding the best move in a game of Magic,' in the worst case, cannot be computed," said Churchill. "There are certain circumstances, even though they're very contrived, where it's proven that no algorithm can find whether there exists a winning move."

In fact, the elimination of all player choice in those special circumstances allows Churchill et al. to make an even stronger statement: "It's impossible in the general case for an algorithm to look at a board state and see whether it's possible for the game to end at all," he said.

The work is most useful for potential AI designers, according to Churchill, since it demonstrates that the brute force approach of exhaustively computing all possible consequences of a given board state won't work—not that an experienced AI designer would choose to do so anyway. "They'd do it using heuristics, rules of thumb that give a best guess about how to play," said Churchill. "Our paper proves that the exhaustive computation approach is definitely not the way to go, because it's actually impossible, in some cases."

"The operation of 'finding the best move in a game of Magic,' in the worst case, cannot be computed."

Might it be possible to do something similar for other tabletop games besides Magic? Churchill thinks it's an interesting question with no easy answer. Accidental Turing completeness does show up in some video games, such as Super Mario World. However, "It's easy to rule out 95% of the games on my shelves," he said. "Either there's no way for those games to process large numbers, or there's no way to restrict player actions."

Churchill is toying with the idea of simulating chess within Magic by setting up a scenario where the number of choices available to a player on a given turn corresponds to a moving chess piece. (Apparently, someone has already managed to simulate a game of UNO within Magic in a similar fashion.) [corrected link] "That just goes to show the delightful space that Magic has for technical interest, let alone all the social entertaining aspects," said Churchill.

For now, he and his co-authors are more interested in seeing what else they can do within the world of Magic. For instance, could you find a board state that could compute 2 + 2 = 4 in one of the online game forums? "Sadly, the answer is no," said Churchill. "To take a function and translate it into source code for this universal Turing machine is really tricky. Even the 1996 paper by the researcher whose machine I'm using didn't give all the instructions on how to do that."

Churchill would like to set up something within the game space of Magic that is more analogous to a computer. "Maybe it's possible to find a combo of Magic cards where, rather than Alice creating all these white and green creature tokens that end up being the Turing machine tape, she actually gets to create something that encodes the computational instructions of an algorithm," he said. "I'm very confident Magic could simulate that, because we've shown it can simulate anything."

Listing image: Gordon Chibroski/Portland Press Herald/Getty Images

Jennifer Ouellette Senior Writer

Jennifer is a senior writer at Ars Technica with a particular focus on where science meets culture, covering everything from physics and related interdisciplinary topics to her favorite films and TV series. Jennifer lives in Baltimore with her spouse, physicist Sean M. Carroll, and their two cats, Ariel and Caliban.

99 Comments