Message Boards Message Boards

7 Replies
9 Total Likes
View groups...
Share this post:

Searching for hamiltonian cycles in magic the gathering

Posted 9 years ago

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

  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.

POSTED BY: Adam Martinek
7 Replies

Adam, have you made much progress with this since posting?

I found this very interesting, and have done some relevant data work I will write up soon.

POSTED BY: David Gathercole

Your goal is to determine whether and where there are infinite loops in mtg.

This can't be done. Mtg is turing complete. [Proof by Googling].

So there are infinite loops and no algorithm exists which can tell you whether any particular configuration is actually an infinite loop.

POSTED BY: Sean Clarke

I disagree with you on this Sean. I have described a computationally sound (so long as you reasonably restrict the depth of the search) way of figuring this out.

Furthermore I would like to point out that my goal is not actually to find all infinite loops in magic. I am ignoring activated abilities and also making the assumption that all triggered abilities have targets and that the proper board state change has happened so that the first triggered ability can be triggered.

So there are a lot of assumptions being made and I have restricted this back quite a bit, but I am also not naively creating some combinatorial explosion by looking at all combinations of cards or board state, because I am strictly looking at the abilities and then doing a backwards lookup based on the abilities.

POSTED BY: Adam Martinek

How are you proposing to use WL to attack this? (I'm not sure I understand the question, but I would guess some readers do. So what do you have by way of code to get people started?)

POSTED BY: Daniel Lichtblau

When I created the post I had marked it as sharing an idea. So there really isn't a question here.

allCards = Import[""];
$TriggeredAbilityDictionary = {"*when*", "*whenever*", "*at*"} (* as per magic the gathering documentation these keywords indicate a triggered ability *)
ParseTriggeredAbilities[abilities_List, cardTitle_String] := Module[{temp, titleReplacedAbilities}, 
    titleReplacedAbilities = StringReplace[abilities, cardTitle->$cardTitle];
    temp = Map[StringSplit[#, ","]&, titleReplacedAbilities];
    temp = Map[DeleteStopwords, temp];

I obviously have more work than this but this is the basis thus far and DeleteStopwords has been nice because I really didn't feel like taking the time to create my own list. Although it is creating some issues because of the fact that it is deleting some words that are needed. The StringReplace above will also do some more preprocessing of the rules text of the cards as necessary because as I look for state changes there are a few rare cases that the state change is a phrase.

POSTED BY: Adam Martinek

Adam, that's an interesting idea. Have you made any progress?

I was an avid MtG player when in my teens, so I've decided to take a look at this API.

Here is how I converted the whole set of cards into a Dataset:

allCards = Dataset[Association /@ Import[""][[All, 2]]]

All MtG cards

And here is how I obtained some insights about the types of cards, their names, and their text:

counts = Take[Counts[Part[allCards, All, "types"]], 5];
PieChart[counts, LabelingFunction -> "RadialCenter", ChartLabels -> Placed[Flatten[Normal[Keys[counts]]], "RadialCallout"]]

PieChart of Types

WordCloud[ DeleteStopwords@ StringJoin[Riffle[Normal[Part[allCards, All, "name"]], " "]]]

Names Cloud

WordCloud[ DeleteStopwords@ StringJoin[ Riffle[DeleteMissing[Normal[Part[allCards, All, "text"]]], " "]]]

Text Cloud

POSTED BY: Bernat Espigulé

I have not made progress from where I was. I was going to use DeleteStopWords to help with the string processing but it doesn't clarify what list it is using nor does it allow you to create an exclusion list, so it is not useful at all for me.

So what I really need to do is get the unique list of words used in mtg cards (ignoring card names), and create my own list of stop words that I can use. Then I can curate the unique list of board state changes and the hierarchies.

Also that is really interesting that Goblin is the most common word in a cards name. Assuming I am correctly remembering how WordCloud works.

POSTED BY: Adam Martinek
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract