A number of months ago I got back into playing the card game Magic the Gathering (henceforth called mtg) and while playing someone in the game shop they got a combo out and were able to win by attacking me for a finite infinite amount of damage (their creature had trample). My immediate response was "That's a Hamiltonian cycle!!! It shouldn't be to difficult for Wizards of the Coast to test for infinite loops like this."

So I decided to start work on a project to search for infinite loops in mtg. Breaking apart this project into the steps I am taking is as follows

1. get a list of magic cards in a good computer friendly format (easily found here http://mtgjson.com/)

2. Read the mtg rules to understand formatting of rules on cards (also easily found here triggered abilities. Note that this is specific to triggered abilities, but other abilities follow a similar format and latter explanation can show that to a certain extent we can even ignore them)

3. parse the natural language of the rules (I will break this part into two substeps)

   • Curate game state changes [currently in progress]
   • Separate abilities into distinct lists (explained in greater detail later. This is one of the more important steps here)

4. With the set of state changes (must be constructed as a tree to include hierarchies because there is a difference between "leaves battlefield", "goes to graveyard", "is sacrificed", and "exiled") and the distinct list of abilities the triggers and effects can feed into each other to look for our search for loops that end with the first ability (we should also state that we only search to a certain depth for infinite loops).

Since the game mtg is a list of rules and the cards you play add new rules to the game the game itself can be viewed as a Markov algorithm for those not familiar with the game.

For those familiar with the game you might be saying something along the lines of "But Adam you are making ridiculous statements because searching for infinite loops is certainly a factorial operation and there are ~15,000 mtg cards." And you are absolutely correct and I am glad you brought that up because while it is a factorial operation, through some clever manipulation of how we are operating on the data we can drastically limit that number. Firstly we can state that we don't actually care about the cards themselves, all we care about are the unique triggers, and effects. Now instead of having 15000! * d where d is the depth of the search we instead have a much harder to pin down O(n). To be honest I don't know what the time complexity is for this in a mathematical sense. Here is what I know: We assume that a trigger triggers an effect e. e can can then feed in to be the catalyst for some set of triggers t. Each trigger in the set t has some set of effects E and we continue to do this till we get to the depth of our search or until we get to some trigger ti that contains effect e. The take away here is that we don't have to look at each card, just unique abilities.

So we have simplified this whole thing by only looking at unique triggered abilities. What about activated abilities? This turns out to be something that we can actually ignore for the most part. Since activated abilities come with some cost we only have to look for something that counteracts that cost (ie infinite mana, infinitely untapping creatures). So we can still use the effects in our search for infinite loops but we would then need to look for infinite loops that let us infinitely activate them.