This post will show how Magic is Turing complete, and what happens if you unleash a neural network on the full Magic card set.

You probably already know of Magic: The Gathering (shortened in mtg) A collectible card games out there since 1993 and still going strong. I have been introduced to mtg by my coworkers at my previous $work, and enjoyed many lunch breaks and evening tournaments building and using decks, figuring out fun and efficient interaction while trying to understand how our inhouse expert could consistently kill me in 2 turns.

Anyway, mtg is a complex game. You can get started quite fast and have fun very quickly by following the basic rules, but the comprehensive rules form a nice 209 pages pdf. This is mostly because each card can override the basic rules, creating new, fun, unexpected and efficient interactions (I still remember a game where I ended up having a zillion zombies on the battlefield. I still lost though, as I could not block my opponent flying creatures). The comprehensive rules sets up the framework to deal with all possible interactions, and is in practice referred to in very rare cases.

Magic: The Gathering is Turing complete

This complexity allows us to create a full Turing machine.

To quote wikipedia:

A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer.

A Turing machine informally consists of 4 elements:

• A tape, which is of an infinite length and is divided in cells containing a symbol from a specified, finite alphabet. This tape is a one dimension tape, with cells being adjacent.
• A head, which can move along the tape, and read the content of a cell.
• A state register, which remembers in which state the machine currently is.
• A set of instruction, which depending on the state and the content of the cell under the head, gives the machine instructions. Those instructions depend on the type of Turing machine you are using, but you can think of moving the head, changing the state or changing the content of a cell.

With only those 4 elements, you can colloquially simulate any computer. The formal definition is of course a tad more complex.

How can mtg be Turing complete? You can find the whole explanation on Alex Churchil‘s site, including the full list of cards and a more detailed how it works.

The set of instructions is defined by what is written on the cards. As you can see, they are well chosen, and have been “hacked” by spells like Artificial Evolution to update the wording of the rules. All creatures have 2 types, one being part of the alphabet, the other defining the ordering on the battlefield.

The tape is the battlefield. To get an ordered tape, the game basically creates token, where the toughness defines the distance to the head. A toughness of 42 is one step further than a toughness of 41. Left and right are defined by creature types, Yeti and Zombie respectively. So moving to the right is represented in this machine by creating a new Yeti token (just to the left of where the head was), growing all Yetis by 1 toughness, and shrinking all Zombies by 1 toughness, effectively killing one.

Once your tokens have their toughness properly set, the head is a hacked Rotlung Reanimator, which can be visualised being between the 1/1 Yeti and the 1/1/ zombie.

The state is handled by phasing, time and tide doing the phasing in and out.

The start state is actually a 4 player games, with some cards already played. Once all is setup properly, the Turing machine can run automatically. Although mtg is a lot about player choice (keyword may), the choice of cards actually use deterministic triggers as Whenever ~this~ or another Zombie enters the battlefield, all non-Zombie creatures get -1/-1 until end of turn except in one case, where the 1st player has to repeatedly say yes to a may choice (you may put a +1/+1 counter on each Yeti creature you control and you may put a +1/+1 counter on each Zombie creature you control).

How useful is this? Well, absolutely not, but it is utterly cool to mtg player into Turing machines.

Neural network and Magic

A PhD student from Birmingham, fan of mtg, decided to see if a neural network could generate new magic cards. If you do not want to read further, the answer is yes, the results are hilarious, and scroll down to the end to see examples.

The code used to generate this set is an implementation of a recurrent neural network (RNN).

I should not explain too much about neural network, as I would probably get it wrong. Basically, a neural network can be seen as a black box, to which you give inputs and which will yield outputs. These outputs are generated in multiple sequential steps (layers) and are based on the whole history of what the RNN already processed. You can give it a few parameters (temperature for instance. Low temperature means more confidence and less creativity). To steer it in some direction, you give it a training set, which is basically what you would expect in the output based on the input you give. Once the RNN is trained, it can generate its own original results.

The data set used is a json collection of all magic cards, which is actually a pretty neat data set.

The RNN generates cards which are sometimes plain hilarious, specially when it makes its own keywords up. Some seem to almost make sense but not quite, some are just nonsensical.

Without further ado, here are some of the generated cards (the image is not generated, the rest is). You can follow the best ones on twitter.