"The Theory and Design of Magic: The Gathering" Class Page

Yay lunch break!

One of the topics I had decided to put into the syllabus was AI, mostly because I like it myself and have a decent enough fundamental breadth in the field to talk about it. I was thinking I would need to pull from a lot of other games and try to work it into Magic, but coincidentally, Wizards has just a game for the XBox Live Arcade called “Duels of the Planeswalker,” a mini Magic simulator for XBox, including a computer player. At first, it seems really lucky because it now gives me something concrete to talk about. On the other hand, I feel like some of my thunder has been stolen. Alas.

Anyways, just yesterday, the feature article of the week on the Wizards site was posted, and it’s all about the AI in “Duels of the Planeswalker.” I first thought about just writing briefly about what he says, but I don’t know if I have a lot to say. It’s very well written and takes some very complicated stuff and reduces it into very simple terms (which is somewhat necessary because it’s a Magic site, not an AI site). I guess what I can do is take what he says and give a little more depth about how it works in a less hand-wavy manner.

He starts out talking about how the game is really just a tree of possibilities. This is pretty much what it sounds like: game trees are directed graphs that connect a bunch of game positions with various transitions. Any position is the exact, parameterized explanation of the game, including everything like life totals, which creatures are on the table, cards in hand, whether lands are tapped, etc. The transitions are the various actions you can take, which are exactly the actions that you can take in the game, such as playing a card, tapping a land, etc, and also any game changes, such as going from one phase to another. Together, these are supposed to represent all possible Magic games at all positions. So somewhere, there’s a massive, massive tree that has all of these. Fortunately, most of them aren’t considered, since a given game where the AI needs to run doesn’t have to worry about a lot of positions where certain cards aren’t in the game and such, but know that they exist.

In case that didn’t make a lot of sense, take a Rubik’s cube as an analogy. At this level, these 2 games are pretty similar; you have a starting position to the game, many possible positions in-between you and a win, and ways to move from position to position. The trick to be smart (either solving the cube or winning the magic game) is to find a way to get from your starting position to the win position without getting stuck in a non-winning position (such as losing the magic game) and hopefully in a fast way. So the various positions correspond to all the permutations of the Rubik’s cube. You can link together all of the various positions by considering the transition actions of spinning various faces of the cube. When you do that, you end up in a new position, which is an arrow from the previous position to the new one.

So I realize I actually have a lot more to say about this than I want to write in one post. What I guess I can leave you with is a funny point about magic. Often, you here people talk about how complicated games like chess are. I have no idea whether it’s immediately apparent or not, but Magic is so much more complicated than that. As a point of scale, first think about the Rubik’s cube. The concept of the toy is relatively simple, but there are so many possible positions it can be in. According to wikipedia, there are 43,252,003,274,489,856,000 possible positions. That’s a huge tree.

Now let’s take Magic.  According to Gatherer, there are about 9000 created so far (I tried to wolfram alpha that, but it failed miserably. Too bad for hardcoding + mathematica). The normal magic deck has 60 cards. If you just get combinations of 60 cards for a normal deck like that, then there are apparently on the order of 10^155 possible deck builds. Granted, most of those are very unfeasible (you probably wouldn’t have enough lands). But you have to take that and multiply for having multiples of certain cards, having 2 players, and then the number of possible positions in a game with a given deck. That’s a lot. Again, for comparison, according to wolfram alpha, there are only 10^80 atoms in the universe. That’s a lot.

Look out for more on this topic.

(edit: from a few sources, it looks like the proper term for the nodes in the search tree is “positions” not “states”. I’ve edited all of these, because it’s early enough and I should try to be consistent with the literature in my writing)

This entry was posted on Tuesday, June 23rd, 2009 at 12:38 pm and is filed under AI. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.