Archive for June, 2009

Rearranging the Syllabus

Sunday, June 28th, 2009

So I posted a description of the class on both the mtgsalvation and wizards forums, to enthusiastic response and great feedback. I just got off the phone with Tom, and we did some rearranging of the syllabus based on feedback from everyone on that topic. Here’s a quick list of some of the people to thank (sorry if I miss you):

tcg_researcher, stsung, zombiefl12, tanishalf, drworm, sacrificial23

So based on that, we rearranged to the following order

  • Week 1 – Overview of topics and the rules of Magic
  • Week 2 – Deckbuilding Basics and “Card Advantage”
  • Week 3 – Game Theory in Multiplayer games
  • Week 4 – Game Design
  • Week 5 – Statistics and Simulation in Deckbuilding
  • Week 6 – Epistemic Logic and Limited
  • Week 7 – Metagame and Applications of Graph Theory
  • Week 8 – Magic-playing Artificial Intelligence
  • Week 9 – Presentations

So a little commentary on the changes is in order as well.

We talked a lot about what we wanted to put in week 2, and we ultimately decided on deckbuilding and card advantage. When we think back to teaching some of our friends, it honestly didn’t take them long to start building their own decks. And that was unguided. Since we’re hoping that students will take us up on open office hours that first week, they should be familiar enough with the game to be ready to at least understand why decks are built as they are and what to look for. Obviously, deckbuilding takes a lot more skill than one can have in week 2, but it makes more sense to lay the ground early then hit harder later.

Card advantage also got lopped in there because we figured that although it’s considered an advanced magic topic, it really isn’t that surprising or rigorous when explained. It doesn’t really fit with any of the academic topics anyways, and works best when talking a little about card selection for deckbuilding.

Game theory and multiplayer is in week 3. We pushed it back a little because of the response, but in the end, we couldn’t see it being in the 2nd half. I think the pull for game theory early is greater than the pull for multiplayer late. The reason why I want these connected is because a lot of game theory deals with cooperative games, and it doesn’t make sense that players should cooperate in a duel (unless they’re trying to draw into the top 8, but whatever). And the reason why it’s in week 3 is because we feel like by this point, in a 10 week quarter, we need to talk about something real.

Week 4 is game design because zendikar is being released on october 2nd, and this class is on the 13th. That gives us  a week and a half to talk about it and read up and put together a presentation on it. We felt like game design could be either 3 or 4, but it goes 4 because game theory is 3 (for the reason above). Although we certainly mean to talk about game design in a larger sense, zendikar at least gives us the grounding in one set so that we can make sense for awhile before explaining the bigger picture.

Week 5 is uninteresting, and week 6 is epistemic logic and limited. When I thought of my examples, a lot dealt with limited formats, and since we moved it out of the first half and away from deckbuilding, we figured it still deserved a lecture slot.

Which means that something had to give, which was metagame. That’s now paired with graph theory. This happened because although tournaments are interesting, they’re not academic. And honestly, my understanding of metagame analysis showed that it maybe wasn’t the same “metagame” that we mean in magic. I think it came up as filler in the original syllabus anyways, so this is a way to put it back in its rightful place.

And AI finishes the course out because it’s my pet lecture that doesn’t really matter for the presentations. That way, we can kill a week on a very academic and very interesting topic that doesn’t really matter. It’s dead week type material.

Comments on the changes?

Posted in Logistics | 1 Comment »

Functional Reprints in M2010

Saturday, June 27th, 2009

Of course, warning for spoilers about cards in Magic 2010, so read no further if you don’t want to know yet.

MTGSalvation does a great job getting spoilers on new sets, which they post here. There’s a mix of new and old cards, exciting and boring, believable and shocking. What I’ve been most surprised by is the number of functional reprints in this set. Compare:

And more that I’m too lazy to go through right now. MaRo wrote an article about reprints relatively recently, where he explains why they do do reprints. That becomes a lot more interesting now that we see the contents of 2010 and perhaps gives some justification for why this is happening. Naturally, it is not the way of magic players to immediately react to change by embracing. Instead, we panic (I’m generalizing from myself, of course). Functional reprints of grizzly bears, terror, and remove soul are seen as:

– A way to suck money out of us. Instead of letting us use our cards from the past, they’re forcing us to buy new cards for no reason than because the card has a new name. One of the things wizards mentioned was that they wanted to make the core sets something that both new and expert players would buy, and this is how they force that.

– A way for players to play 8 copies of a card in some decks. With extended and bigger formats, players will have access to both 2010 cards and older cards, so doing functional reprints allows a player to have 8 copies of goblin lords (goblin king and goblin chieftain)

But given some time to cool down, it’s really not that bad. Let’s re-evaluate those points, and then look at what MaRo has to say

– They’re going to suck our money anyways. A lot of the changed cards aren’t rares, and there are enough good cards in the set that we’ll buy lots of packs anyways, and end up with full sets of the cards we want anyways. This is, of course, from the perspective of college Kevin who has disposable income for this. Take me back 4 years, and I would be irritated. Then, I’d have to mine the 10 cent bin and hope I could update my collection with just a couple dollars to continue to play standard. I’ll skip the familiar rant, though, that magic doesn’t understand casual players for what they are (being neither new players nor pros)

– A lot of the cards that they’re changing aren’t going to matter. No one plays 4 master decoys, much less 8. Savannah lions was once awesome, but power creep means that it’s not so special anymore that 8 in a zoo deck is going to break open any format (I think). I’m not honestly scared about any of the reprints individually, and will only be when someone breaks it

– MaRo’s point #4 about getting clean cards to fill holes. 2010 is going to be a major change to magic, both in cards and rules. In some sense, it’s major housekeeping. Magic rules haven’t gotten bent out of shape. Some cards exist that aren’t quite what they should be, whether that’s having the wrong creature type or being flavored specifically for a block when it should be more general for a core set. What 2010 does is give players a complete, simple, usable toolkit of cards without a lot of cruft, and that’s what a core set should give.

– And then there’s point $5 – simplicity. A lot of these cards are very simple, which is good. It’s made to introduce new players to the game. And the name of cards conveys what they are. I remember reading an article where someone (maybe forsythe?) talked about how card names and that flavor should reflect functionality. That’s what makes magic so clean.

In any case, I’m sure dailymtg will address this point. I wouldn’t be surprised if MaRo wrote about it for tomorrow’s article, but at least this way, I seem original in my critique and analysis instead of just responding to an article.

Posted in Game Design | No Comments »

Search in a Search Tree and “Decision-Point Theory”

Wednesday, June 24th, 2009

Just this morning, I figured I should pick up the starcitygames feed to make sure that I was seeking more important articles. That was a great decision, because I already have an article to write about.

In my last post, I was talking about how a Magic game can be formalized into a series of positions, each with its own set of values representing the entirety of the game. We can take all these positions and put them into a search tree, where each position is linked to others depending on what actions can lead from one to another. With this, we can now talk a little more formally about how search through that works (if you’re trying to follow in the original dailymtg article, we’re still in first section, “Basic Concept”).

So the search algorithm that a computer would use on a search tree like this would be to find the best (ambiguity in defining best because I’ll address it later) path of transitions between positions that lead from the current position to a winning position. All that really means is that the computer’s algorithm for winning is to determine each step it needs to make that gives it the best chance of winning from where it is now. That doesn’t sound nearly as nerdy.

Because that’s exactly what we as humans do, and Gavin Verhey just posted 2 articles* on starcitygames discussing that exact topic. Basically, he says that magic is a series of “decision points,” and at each, you have new choices and decisions to make and you can make the right decision by looking ahead on that road and seeing what options are there. This shouldn’t sound surprising; this is both intuitive, and very similar to what Patrick Buckland had to say in the dailymtg article.

I guess the real trick here is determining which choice is the best and doing that relatively quickly. There are obviously tradeoffs between these two goals, but I’ll see if I can walk through the intuition for how this is done step by step.

So let’s temporarily assume that we have infinite time. You’re, say, trying to figure out whether you should chump block a shambling remains with a mogg fanatic now, or wait and hope that you don’t die before you can use the mogg fanatic more effectively when you can deal 1 more point of damage to the shambling remains. Since we have infinite time, we can just see exactly where both of these decisions would lead. Even though the trees below both are still huge, they’re finite, so it can be done in infinite time (maybe think 5 monkeys with typewriters and infinite time writing the entire works of shakespeare?). This way, you can determine which is better by, say, taking the ratio of wins versus losses in each sub-tree and picking the more favorable one. So if blocking results in 1 million wins to 500,000 losses and not blocking is 2 million wins to 1.9 million losses, let the fanatic die now.

So your first instinct here is that just taking the ratio isn’t a good way to determine which path is better. Certain paths are more likely (have a greater probability) of happening. Which is true. And maybe not all of those options are equal. In that case, maybe we can weight each outcome by the probability that it would occur. But in the end, it seems like our best method is to somehow quantify (probably numerically, since this is going to be a computer algorithm) the value of various paths and pick the option that has the better summed up value in its sub-tree.

Unfortunately, we don’t have infinite time. Because our finite time is probably significantly less than the size of the tree, we can only look a few decisions and positions ahead (perhaps even as few as 1). In this case, we take shortcuts, or heuristics. One of these is to evaluate the goodness of any position and compare those. We can do that using an evaluation function, which is just a fancy word for taking a bunch of important factors, weighing them, and getting an end value. For example, our 2 choices may result in something like:

2 * 1 (for having the mogg fanatic) + .1 * 16 (being at 16 life) + .1 * 1 (for having just dealt 1 dmg to your opponent with the fanatic’s ability) + …other stuff = 5

2 * 0 (no mogg fanatic) + .1 * 20 (20 life) + .1 * 0 (didn’t pop the fanatic) + …other stuff = something less than 5

(Ignore the 2 most obvious faults that popping the fanatic is another decision and that there isn’t a linear value to life)

So it seems like in the position immediately resulting from blocking or not blocking, it’s more valuable to block. This, however, is obviously short-sighted. Maybe, your opponent can immediately do something else (like, say, play a figure of destiny that you now no longer have a mogg fanatic to kill before it pumps). So what you really want to do is look as far as you can in the future and evaluate that position, assuming that your opponent made intelligent decisions all along the way. What actually ends up happening is that you need to alternately need to look through states where your evaluation function is maximized (for when you made the best choice) and then a state where your evaluation function is minimized (for when your opponent made a choice and tried to screw you). This is a rule in game theory called “minimax”  where you’re trying to maximize your own evaluation function in a game with some adversary.

These are getting really long. Anyways, I’ll continue to talk more about this in another post. In that, hopefully I’ll finally get to talking about alpha-beta pruning and more exciting, AI-y sorts of things.

* I should make a couple comments about these articles. 1) I honestly thought they were kind of dumb, but clearly, I appreciated them enough to link to them. In some sense, he’s doing exactly what I’m doing, and taking a more complex idea and explaining it simply. So maybe I should like them more? 2) Decision-point theory, I’m pretty sure, is a term he came up with. I’ve never heard of it before, and it doesn’t really mean anything. It can either be part of game theory or ai, but it definitely isn’t legit on its own. 3) The best point I thought he made was that pros often play complex decks that require a lot of decisions, and good playskill often shows that they choose options that give them more options down the road. This actually deals with another part of search algorithms called “constraint-satisfaction problems”. In that, “forward checking” is something of a way of doing lookahead, and “least-constraining variable” is a heuristic for making choices. But that’s all another post, if it comes up again.

Posted in AI, Game Theory | 2 Comments »

Position space of Magic

Tuesday, June 23rd, 2009

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)

Posted in AI | 3 Comments »

Assigning Damage with Steve Sadin

Tuesday, June 23rd, 2009

Steve Sadin put up an interesting article on the wizards site this morning. If you aren’t aware of recent rule changes, by the old rules, an attacker could assign damage to blockers in any way they wanted to. That’s not the case now. New rules in magic say you need to order blockers and damage is assigned so that there’s enough to kill each one in a row. It’s an interesting article to me because he talks a lot about what you think your opponent has in their hand. Moreover, there’s implicit signaling going on between the two players here: because the other player double-blocked with the elf and minotaur, then you know something more about what they know to have made that choice.

This fits into a topic in epistemic logic related to public knowledge. So a classic example of how this sort of thing matters is the puzzle of dirty children. I have very limited time, so you can go read on your own. Anyways, it gets interesting because the children learn from each other’s responses (in theory; real college students weren’t smart enough to figure this out, so I don’t think the toddlers could either). When one announces something, it becomes public knowledge so everyone knows what they know (or they at least know that the speaker knows something).

I’m a little sad Zvi isn’t still writing “The Play’s the Thing,” but I know he got a lot of crap for what he wrote, so I don’t blame him. Still, I think this is going to be very helpful for the class.

Posted in Epistemic Logic | No Comments »

What this is all about

Tuesday, June 16th, 2009

I seem to have an obsession with making new blogs. I think it has something to do with my belief that someone might care?

So what this is all about. This blog is going to chronicle the design of a course. Particularly, the course is about Magic: the Gathering, the card game. I’m thinking it might one day turn into the class page as well. So a little history about this.

At the end of winter quarter my freshmen year, Tom, the guy next door, brought his Magic cards from home to sell. I myself had played for 2-3 years until quitting mid-senior year in high school. I was very excited and soon, we had a play group in Tom’s room. Tom and I both play at a proficient and knowledgeable level, having both read articles and been familiar with some of the theory of the game. One of the silly ideas we threw around was teaching a class on the game. By that summer, we got the idea that we could teach a student-initiated course here at Stanford on it. We threw together an early syllabus and applied the fall of our sophomore year. Although we brought in a lot of interesting topics, the class still felt like something cobbled together to justify playing Magic. As such, we were rejected by the committee.

But we weren’t going to be blown off so easily. This spring, 2 quarters later, we re-applied with a new syllabus. This time, we changed out a lot of the Magic readings in favor of academic readings and re-designed the class so that the topics formed a more cohesive set. We moved from a course about Magic to a course that used Magic as a teaching tool for a lot of interesting topics. We worked to make the syllabus much more rigorous and were rewarded with apparently enthusiastic response from the faculty committee and approval to teach the class this fall.

So the purpose of this class is what I mentioned about: to find an interesting way to talk about what we consider interesting concepts using Magic instead of the stock examples. It’s actually amazing how closely the concepts of Magic are tied to real things. As such, the class is going to be meant for new or casual Magic players looking for something fun to do while getting a survey of a couple topics. These include:

Statistic & Probability – these are better known as the “mana curve” and “deck thinning” in Magic. Magic is a game where two players draw cards out of their deck. Trying to figure out when a card is going to be drawn and with what chance is absolutely stats.

Game Design – this one should be pretty obvious. Magic is a game. People design it. Thus, game design. Fortunately, Wizards of the Coast has had 2 excellent weekly columns on it: research & development in “Latest Developments” and design in “Making Magic.”

Game Theory – another one that is basically built into the name. Game Theory is about making decisions based on the decisions of others. That’s pretty critical in Magic because you’re constantly making choices based on what your opponent is doing.

Epistemic Logic – this is what you’re trying to do when you read your opponent or signaling in drafting. It’s the logic of knowledge. This has a lot of parts, but the part that I have exposure to deals with what agents know, what they know about what others know, etc. There’s some really interesting work formalizing this that we can apply to Magic

Graph Theory – this is the idea of a deck having good synergy. I personally am not doing the work for this, but the idea is that we can attempt to use graphs to represent decks and determine how effective it is based on what sort of topological surfaces the graph can be mapped onto.

Artificial Intelligence – honestly, this is just my chance to show off some of what I know about game AI. It’s reasonable to think that if a computer can play chess, it can play magic.

Of course, all this is gone into much more depth in the syllabus. I’m actually hoping that a lot of people will take a look at that and comment on it. The disclaimer is that I’m not an expert on any of this stuff. Far from. Instead, most of the academic stuff is going to be at a college 101 level. Thus, I’m likely misinterpreting/making mistakes on much of it.

So we’re going to meta out a level right now. This blog is about this class. What you’re likely to see on this page is just our research and progress in the class. That might include

  • decklists of beginner decks that we’re building
  • interesting articles we find around the internet
  • slides from presentations we’re putting together

Hopefully, Tom will be posting stuff as well, but he’s probably not as blog-crazy as I am. Which is a good thing, in some ways.

Since we’re just starting now (Tom just got back into the country), it’ll probably be slow in the near future. In the meantime, I posted some links on the right of some of the sources we’re using.

Posted in Logistics | 2 Comments »