Message Boards Message Boards

3
|
13883 Views
|
7 Replies
|
9 Total Likes
View groups...
Share
Share this post:

Searching for hamiltonian cycles in magic the gathering

Posted 9 years ago
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["http://mtgjson.com/json/AllCards.json"];
$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];
    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["http://mtgjson.com/json/AllCards.json"][[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
Attachments
Remove
or Discard

Group Abstract Group Abstract