Monday, April 13, 2015

Getting Your Computer to Make an Awesome New Magic the Gathering Deck

In my last post, I wrote about the Magic: The Gathering article over at Channel Fireball,

Magic Math – A New Way to Determine an Aggregate Deck List: RG Dragons by Frank Karsten.

Although I thought Frank's article was great, I'm not the biggest fan of the idea of building aggregate decks.  It's not that I don't like them as a possible tool for making a better deck, but rather that I don't find them terribly interesting.  They aren't new or different, just refinements on decks that have already been created.

What really excites me is the idea that we can use automation to plow new ground and discover great decks that no one has seen before.

I've done a little thinking on trying to use a computer to make a better deck that is also original. It's a Search Problem: you have many combinations of 60 cards, with the goal to find the optimal set of 60 cards.

Constructing a deck through computer automation is not a difficult problem.

The big problem is evaluating it.

How to evaluate a deck in an automated fashion? The best way is to play it a crap-ton of times against all the best decks currently in the format (including some tier-two decks, to suss out any sort of rock-paper-scissors type relationships between multiple decks). To best do that, you would want a good automated agent ... or to hire millions of MTG players.

To some extent, millions of MTG players are already doing this, which is how we find our tier one decks.  However, I think there are areas in the search space of all possible decks that are not being explored, and are in effect getting missed by our human blind spots.  We see the obvious synergies between certain cards, but there have to be some that we miss.  That's why I think this is so interesting.

No one wants to pay for a million MTG players to test thousands of computer-generated decks, some of which are bound to be losers.  We need an automated way to do it.

Possible Automated Solutions


1.  Find a heuristic or set of heuristics to evaluate the deck

"Heuristic" is just a fancy computer science word that means, "A simple rule to find an answer that is close enough, because doing it the correct, hard way would be too slow."

I love heuristics as much as the next guy, and I think developing a few simple ones could be useful for weeding out bad decks.  I'm thinking of things like checking the mana costs of your cards and comparing them to the land composition in your deck.  However, some of this stuff can just be programmed into your process in the first place.

Ultimately, I believe this approach fails because MTG rules are too complex.  When every card can have its own rules text, heuristics are going to miss too many opportunities for deck synergy.  In effect, I'm saying, "You can't simplify and expect to get a good deck."  Maybe you could get a good basic aggro or control deck, but I don't think you need a computer for that.

Also, you really just don't know how good a deck is unless you play that deck and get an actual win or loss out of it.

2.  Make an automated MTG game-playing agent

Making a good automated Magic player agent would be hard, but do-able.  You could write it to interface with Magic: The Gathering Online (MTGO) or another system.  You could even rig up some fancy learning Artificial Intelligence, or basic game-playing logic.

The hardest part would be coding up all of the game rules, and that would be a big task.  Your early attempts would surely infuriate many players with how badly they sucked (And I don't just mean sucks as in "loses the game," but sucks as in "stops playing altogether when it can't figure out Chains of Mephistopheles."

The second hardest part would be making it good, because MTG strategy ain't easy, especially when the number of different cards available is as large as it is.  This is somewhat mitigated if you choose a format with a reduced card pool, like Standard, but it's still hard.  Also, with so much hidden info, writing a piece of software to guess at card-draw probabilities, know about different deck archetypes (including the possible new territory that it is forging itself!) would be a real pain.

With much work, you could probably get something that approximated a human player, maybe even a pro.

However, even if you went to all that trouble, it's not the best (and by that I mean easiest) solution, even if it would be an interesting and worthwhile project.

3.  Make an automated agent THAT CHEATS!

An automated agent that can see all parts of the game state (thus being a big Cheatyface) would allow us an easier avenue to simulate absoluate perfect play.  Now when I write "all parts of the game state," I mean:

  • Hand contents of both players
  • Composition and ordering of both decks

Furthermore, if you wanted to simulate slightly more realistic play, you could hide some state, such as the deck contents of one or both decks.  This would help make the problem easier to solve (i.e. "tractable" in computer-ese), as opposed to trying to program in knowledge of deck archetypes, or something else that is inherently harder.  You could generate different sets of win-loss data based on how much cheaty knowledge was allowed, and this could enhance your analysis, including possibly informing you how "hard" a deck was to play (the more psychic knowledge it requires to consistently win, the harder it is to play).

And you could play two such agents against each other!

A large part of the effort would be implementing the MTG rules engine, and including the custom rules for all the cards in a given format. This is important, but not because you want the agent to be able to play the game.  It's important because you want the agent to be able to look ahead at future states of the game (life totals, permanents on the board, etc.), and pick the best one (i.e. the one that scores the best, based on optimal play by your opponent, and the resulting possible future game state).  Of course, choosing how to score a game state is another challenge, but not a terribly tough one.

Now, if I can just get Wizards of the Coast to give me programmatic access to their rules engine for Magic: The Gathering Online, I'll be most of the way there!

Hey Wizards, what do you say?!

Sunday, April 12, 2015

Magic: the Gathering and Computer Automation

I am an avid Magic: The Gathering (MTG) player.  A few days ago, a friend pointed me to an interesting article that combines MTG and math, and relatedly computers, which is what really interests me.

The article describes a process for generating a deck list based on all the best deck lists of a given type.  The idea is to use the crowd of the best examples to make a deck that is even better.  Check it out if you're into that sort of thing:

Magic Math – A New Way to Determine an Aggregate Deck List: RG Dragons by Frank Karsten

One cool thing about Frank's process is that it can be automated, and that's the part that really gets me going (and some people in the comments of the article have already done so, in fact).  That's because although I think his process is a neat idea, as with anything new, it can be refined and made better.

Automation can help with this refining.  Once automated, you can play with some of the rules of Frank's process (let's call it Process #1).  One such rule is a rule for breaking ties if you have two cards competing for a spot in the deck.  Frank states in his article that he just picked something easy to break these ties, which is to choose the card that comes first alphabetically.  Changing this rule is a refinement to the process, and creates Process #2.  For example, say you change the tie-break condition to be whichever card has a lower casting cost.  It's an arbitrary rule, and probably not a great one, but possibly better than the alphabetical rule.

And now we have a new process, Process #2, to compare against Process #1.  Since both are automated, we can use them to quickly make many new decks to compare and contrast against each other.  All that's left is to figure out which one is better, admittedly not always an easy task, but still we're one step closer to the best deck in the land (cue evil laugh)!

Automation is so great.