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?!
