How to Build a Computer from a Collectible Card Game
It is, in computer science parlance, “Turing complete”
Magic: The Gathering, or MTG, is famous for being complicated. I mean, not just for being complicated. It was the first of a genre known as Trading Card Games (TCGs), where players collect cards and assemble decks of those cards to play a dueling game.
In the game, the players are rival magicians controlling creatures, spells, and artifacts in an attempt to reduce the opponent’s life to 0, at which point, said opponent loses. Well, that’s usually how it’s played, at least. Magic cards, especially rare, valuable ones, can occasionally alter the entire game. Look at this one, for example:
Coalition Victory is a game-changer, quite literally. If you have that card in your deck, the goal is no longer to destroy your opponent, but rather, to assemble one of each basic land and a creature of each color.
And it isn’t the only card that acts like this.
Magic designers have had no qualms about releasing cards that change the entire game, and at times, that’s led to some serious shakeups.
There are over 20,000 cards in MTG’s total collection, and with so many rules attached to those cards, it’s no surprise that many complex things are possible. But a computer? That seems far-fetched.
What do we mean when we say “computer”?
Obviously, MTG isn’t going to give you a keyboard, mouse, and monitor. The cards may have pictures of magic on them, but in the end, they’re still just made from cardboard.
So, when we say computer, what we mean is this:
A complete Turing machine can be implemented in a regular game of MTG.
Alan Turing, a brilliant British mathematician whose work during the mid-20th century paved the way for modern computing, was the inventor of the machine that bears his name. He also played a major role in World War II; his advancements in cipher-breaking technologies were critical to the British victory.
Unfortunately, he was never recognized for his work and was prosecuted by the government due to his homosexuality, and it’s widely believed that he committed suicide as a result of this persecution, though it’s also possible that he died due to accidental cyanide poisoning. He was 41 when he died.
Though his career tragically ended far too soon, his contributions can be seen in all areas of computer science, and the theoretical machine he designed is one of those contributions that we’re going to use today.
The Turing machine has a few very simple functions: it can read a symbol, it can write a new symbol, it can move back-and-forth so as to see more symbols, and it can ‘change states’; changing its response to reading any given symbol.
The machine operates on a tape. Most Turing tapes are infinitely long. The tape contains symbols, which are the instructions for the program. The machine also has a ‘head’, which is the single symbol that can be read and replaced by the machine. The head can move left and right in response to what it reads.
The machine’s ‘states’ determine its response to various symbols. If the machine reads the same symbol in the same state, it will always have the same response. For example, reading symbol D in state 1 might cause it to replace symbol D with symbol E, move right, and change to state 2.
For each computational ‘step’ taken by the Turing machine, it does a few things:
- Read the symbol.
- Write a symbol in its place, based on what the state the machine is in and what symbol was previously read.
- Move left, move right, or remain stationary, based on what state the machine is in and what symbol was read.
- Change state or remain in the same state, based on what state the machine is in and what symbol was read.
I couldn’t give you the mathematical proof that it’s true, but those who can say that a Turing machine is functionally equivalent to a computer, given infinite tape and infinite time, and can do any computation a computer can.
How do we build a Turing machine in MTG?
Well, it’s quite a process. The deck itself, constructed from rare and even ‘mythic rare’ cards, is almost twice as expensive as my own personal computer, and it runs… a few quintillions of times slower, I’d guess.
Outlined in the excellent paper Magic: The Gathering is Turing Complete, there is a deck of Magic cards that is tournament legal under the Legacy ruleset (60 cards, among other restrictions), that can set up a Turing machine that will run until the program terminates.
Here are the steps:
- Gain infinite mana (energy, with which we can play cards), then draw your entire deck.
- Prepare the machine’s functions.
- Play some more spells that create ‘the tape’, an arbitrarily long line of creatures (more on that later).
- Play a few more enchantments on the field that set up the game state so that neither player ever has a choice about what to do in the game ever again.
- Set up your draw pile so that it contains only 4 cards, in a specific order.
Then, the machine begins to do its work.
This machine — compared to a regular, idealized Turing machine — has a few small limitations. Regular Turing machines could have arbitrarily many symbols; this machine only uses 18. Similarly, regular Turing machines usually have many states, while this machine only has 2.
However, a 2-state, 18-symbol Turing machine has been proven to be universal, meaning that it is capable of simulating a Turing machine of any complexity, meaning that these limitations, though they do exist, do not prevent it from being considered a complete Turing machine and thus, given enough time (and it would take a lot of time), a complete computer.
If you’re interested in how exactly all this works, I’m now going to go over it in a lot more detail, describing how the interactions between cards and rules let something like this be possible.
I’ll describe the setup, then describe how this machine runs, then, finally, explain what might happen if someone brought this deck to a tournament.
(Note: I’m doing my best to explain it, but I don’t fully understand all the inner workings of this machine, in either MTG or theoretical computer science. If you want, you can read the original paper that this concept came from here).
Setup Step 1: Gain infinite mana and draw your entire deck
This is the easy part, but you need to get pretty lucky in your opening hand for this to work.
The rest of this article will go into depth about specific rules of Magic, so we’re going to need to use a few terms that are specific to the game. I try to explain them, but if you’re ever confused, here’s a link to a basic guide that should help you out.
Magic allows players to play one ‘land’ card every turn. Land can be ‘tapped’ to give the player, usually, 1 mana. Once tapped, it stays untapped until that player’s next turn.
So, usually, you only have one mana to work with on your first turn, which means you can only cast a very weak spell. That’s…not what happens here.
The land we play is called Ancient Tomb. It gives 2 mana, a significant improvement over the usual 1, at the cost of dealing 2 damage to the player.
We also play three Lotus Petal, a card—not land, so we can play more than one—that can be sacrificed for even more mana. This takes us up to 5 available mana.
Then, we play Grim Monolith.
Grim Monolith (also not a land, but it does give you mana) doesn’t untap normally; you have to pay 4 mana to untap it. When you tap it, though, you gain 3 mana—essentially, you can think of it like a battery, saving mana for later, but you lose 1 mana every time you charge and discharge it.
That’s not enough on its own, though. We also attach to Grim Monolith a card called Power Artifact, which makes every ability on Grim Monolith two mana cheaper.
Because Grim Monolith costs 4 mana to untap, reducing the cost of its ability by 2 mana means that it only costs 2 to untap.
So we then tap it, taking our mana total to 3.
We untap it, paying 2 and taking our total to 1.
Then we tap it again, getting 3 more, taking our total to 4.
Then we untap it, paying 2 and taking our total to 2…
You can see that each time we tap and untap it we gain 1 mana. We can do this infinitely, and now have infinite mana.
(Magic allows players to skip tedious loops if everyone agrees about what happens at the end, so thankfully, we don’t have to do this hundreds, or thousands, of times by hand—we can just say ‘we’re gonna do this infinitely’, and everyone agrees that we now have as much mana as we want.)
Then, we play a card called Staff of Domination, which has an expensive ability that allows us to draw 1 card in exchange for 6 mana.
Thankfully, we have as much mana as we need. So we draw our entire deck.
Then, we play Gemstone Array, which converts our infinite colorless mana into infinite mana of all five colors. (Some spells want mana of a particular color to play, so now, we can cast any spell we want.)
Now that we have unlimited power and our entire deck in our hand, the real challenge begins.
Setup Step 2: Prepare the machine
This is where things get tricky.
The machine’s tape will be represented by creatures that you summon into being, but the tape needs to have data on it in order to function. This data is expressed by the ‘creature type’, where each creature on the tape is one of 18 types.
In order to read that data, though, our cards, which normally only refer to one type of creature, need to refer to all 18 of them.
So we use Artificial Evolution, which says “Change the text of target spell or permanent by replacing all instances of one creature type with another.” We also use Glamerdye, which changes the color words on a permanent in the same way.
The cards we’re editing are Rotlung Reanimator and Xathrid Necromancer. These cards both have a similar effect: any time a creature of type _____ dies, they summon a new creature of type _____, color _____.
Normally those blanks are filled with the same things on each card, turning Human creatures into Zombies with the color Black, which would make them not useful to us, but we’re editing them using Artificial Evolution and Glamerdye.
We’re also making 36 copies of those cards, so that each card can have a different symbol encoded into it, and each card can perform a different action in the Machine.
These edited Reanimators and Necromancers are the backbone of the Turing machine.
They will be the way the machine ‘reads’ what is on the tape (because one particular type of creature dying activates one particular card, and doesn’t activate any other card).
They also allow the machine to ‘write’ back to the tape (because it summons a new creature to replace the old one, and that new creature is of a different type depending on which card was triggered, encoding a different piece of data).
Finally, this also allows us to move the machine left or right, as it will move in a different direction depending on how the Reanimator/Necromancer was set.
Setup Step 3: Play some more spells that create ‘the tape’, an arbitrarily long line of creatures
The details of the spells are beyond me, but I don’t have any trouble believing that with infinite mana and the right cards, you can make infinite creatures. This is exactly what we do.
The creatures are set up in a very specific way. Their position on the tape is marked by two things: their color and their toughness.
Every creature to the left of the middle of the tape is colored ‘green’, while those to the right are ‘white’. This lets the machine know which side each creature is on.
Each creature is also given a toughness level. The creature that the machine’s ‘head’ is on has 2, those that are 1 away from it have 3, those that are 2 away have 4 and so on.
Setup Step 4: A few miscellaneous enchantments
We play:
Wheel of Sun and Moon on ourselves, which means that cards go to the bottom of our draw pile instead of being discarded. This lets the machine loop for as long as it needs to, rather than ending the game when there are no cards left in our draw pile.
Illusory Gains on ourselves, which gives us control of the most recent edited symbol in the tape.
Wild Evocation on ourselves, forcing us to play a card every turn, so that we cannot stop the machine.
Privileged Position on the opponent, so that we cannot target their creatures.
Vigor on both players, so that whenever their creatures take damage, they gain more toughness instead.
Recycle on our opponent, which forces them to skip their draw step, making it impossible for them to gain more cards that they could use to mess up the machine (and impossible for them to lose due to an empty deck).
Blazing Archon on both players, which makes it impossible for creatures to attack them. This means neither player can interfere with the machine by using the creatures that have been placed under their control.
This means that the opponent cannot do anything. For good measure, we also exile everything in their deck, hand, and anything that they might have played on their first turn.
Setup Step 5: Set up your draw pile
By playing cards in order, Wheel of Sun and Moon will let us select the order of the draw pile. This is critical for the machine to run correctly.
Set up your draw pile so that, top to bottom, the 3 cards are:
Cleansing Beam
Coalition Victory
Soul Snuffers
We also keep a copy of Infest in our hand, which we will be forced to play next turn, before drawing, by Wild Evocation.
How the machine works
The machine takes 1 ‘step’ of operation, reading, writing, moving, and sometimes changing state, over (usually) 4 turns of gameplay.
Turn 1:
On the first turn, you are forced to play Infest, which kills the creature at the head of the tape (with 2 toughness). Infest is then put at the bottom of your draw pile to restart the loop.
This allows the machine to read the symbol on the creature, because when it dies, a Rotlung Reanimator is triggered. Which one is triggered is based on what creature type it was.
This also allows the machine to write a new symbol. For example, the Reanimator might read: “Whenever a creature of type A dies, summon a 2/2 (2 power and 2 toughness) creature of type C, with color (white, green or blue.).”
If the creature summoned is white, the Machine will move to the left. If it’s green, the machine will move right. If it’s blue, the program will end.
This Rotlung Reanimator effect has now performed the function of a step of a Turing Machine, which might have a rule that says:
If symbol A is read, write symbol C, then move left.
Then, you draw Cleansing Beam, are unable to do anything, and end your turn, the second player is unable to do anything, and ends their turn, and it’s your turn again.
Turn 2:
You play Cleansing Beam, which deals 2 damage to whatever creature you choose, as well as any creature with the same color as that creature.
You are forced to play it, but you’re able to choose the target. Except you’re not—the only creature that’s legally targetable is the one that was just created, as all of the creatures controlled by the opponent are protected by the Privileged Position we gave them, and all of our own creatures have been protected by various other spells.
Except for the one that was just added to the tape, which was created on the opponent’s side, but moved over to our side due to the Illusory Gains card we played!
So now, 2 damage is being dealt to the just-created creature, right? Wrong—both players control a copy of Vigor, which means that instead of taking 2 damage, the creature gains 2 more toughness.
And Cleansing Beam impacts not just the creature that was just created, but every creature of its color as well. Remember that every creature on the left of the tape is green, and on the right, they’re white. If the just-created creature itself was green, this means that the tape is moving away from the left, and so, to keep the position accurate, those creatures must gain toughness, which is exactly what Cleansing Beam does, giving each creature on the left 2 more toughness in the same way.
(But don’t they only need to gain 1, since it’s only moving by 1? We’ll get to that.)
This action being done, then you draw the next card, Coalition Victory, and the second turn ends. The opponent is still unable to do anything and passes their turn.
Turn 3:
You play a Coalition Victory—remember that card from the beginning? It’s an alternate win condition: if you control a creature of all five colors and basic land of all five colors, you win.
We have all five basic lands, so that part’s done. We have green, red, black and white creatures in play, but we don’t have a blue creature, so the program doesn’t end.
Unless, of course, the special instruction was activated during turn 1, and a blue creature was generated. If that happened, the program has performed its “halt” instruction, because now, the game is ended by Coalition Victory.
Otherwise, nothing else happens, you draw Soul Snuffers, and the opponent passes their turn as usual.
Turn 4:
You play a Soul Snuffers, which decreases every creature’s life by 1. It immediately dies due to existing effects on the field, setting it back up for the cycle.
Now, the tape has been properly set.
This Soul Snuffers being played is why it was OK that Cleansing Beam gave the creatures 2 toughness, rather than one, because now, we have increased the life of every creature on the side it’s moving away from by 1, +2 from the Cleansing Beam and -1 from Soul Snuffers, meaning that each of those creatures are 1 further away from the middle—which is exactly as it’s supposed to be.
It has decreased the life of every creature it’s moving towards, though, because they weren’t hit by Cleansing Beam. Those creatures all lose 1 life, and the creature that was immediately adjacent to the 2-toughness creature that was killed this cycle, which was a 3-toughness creature, becomes a 2-toughness creature itself.
This means that when the cycle repeats again with Infest being played at the start of the next turn, that new creature will be killed, a new symbol will be read, a new set of instructions will be carried out, and the Machine will continue operation.
There are some more details—notably, the Machine has 2 ‘states’ it can be in, using the “phasing” ability, a few more spells, and two different sets of Reanimators and Necromancers to make this work—but they’re too complex to get into here. Check out the original paper, linked above, if you’re curious about that aspect of it.
Finally, as promised:
What would happen if you brought this deck to a tournament?
Well…that depends, technically, on the answer to an unanswerable question.
Let me explain.
A Turing machine has the ability to end, or ‘halt’, by performing a certain instruction: in our case, reading symbol 17 in state 1. In the case of our machine, that summons a blue creature, which triggers the Coalition Victory and ends the game in our favor.
Some ‘programs’, or starting states on the machine, do eventually halt. Others do not. And for many more, it’s unknown whether or not they halt, and the only way to find out is to let it play out until it does…if it ever does.
The question of how to determine if a program halts is known as the Halting Problem, and Alan Turing proved that there is no algorithm that can solve this problem for every possible input.
How does this impact the game? Well…
According to the Comprehensive Rules, 104.4b: If the game somehow enters a “loop” of mandatory actions, repeating a sequence of events with no way to stop, the game is a draw.
So if a program on this Turing machine could be proved to never halt, it would be a loop of that kind, and thus, the game would end in a draw.
But if the program did halt, that rule wouldn’t apply, and the game would be a win for us, the player who set it all up.
Except there’s no way to know whether or not it’s going to halt, so you can’t decide the outcome of the game.
In fact, the entire point of building this deck, from the researchers’ perspective, was to prove that the rules of Magic are so complex that determining the outcome of a game of Magic can be impossible, even when no player has a meaningful decision left to make.
They do this by making the answer to the question ‘who wins this game’ as hard as a question that is already known to be impossible, which is, I think, a very clever little trick.
This has serious implications for the models of games that are used by computer scientists, and goes against many assumptions previously held in that field. Again, you can read more about that in the original paper.
I hope you enjoyed learning about this as much as I did. I hadn’t really known very much about Turing machines or weird Magic decks before writing this piece, and it was really fun to take this little journey. I never knew that there was this much depth to what seemed like a simple little card game.
