October 17th, 2009

I realize I haven’t posted in a couple weeks, though I’ll call the podcast as a cover. The lack of anything notable, though, is a good sign that things are going swimmingly, though.

The Zendikar draft last week went well, thanks to intervention from a student who happened to have packs when ours didn’t ship in time. About half of the people there were pretty experienced players, and a couple had even taken a look at Zendikar limited. The winning deck ended up being a B/R aggro deck topped out with a Sorin Markov. I think everyone put together reasonably good decks. The only surprising move in the draft was that fetchlands were going 6th-7th pick. Apparently no one told them that they were worth more than they paid to get into the draft. Whoops.

In-class constructed is going well as well. The decks have definitely gotten a lot better. Green is pretty popular for the beatdown, and there are a few white weenie decks. I’ve seen a couple U skies decks being played, with just enough counters to go around, and a lot of mid-range fliers for beats. Red is surprisingly unpopular; I think I saw 1 red deck and 1 G/R deck, neither of which were doing too well. The lack of good burn is a problem, though I slapped together a RDW that used seismic strike for some good work (drooling ogre is great out of block, by the way). One of the most surprising developments is people playing MBC. I’ve seen at least 3, and they’re good. Looming Shade has been a big winner, and Festering Wound has been annoying, but the real winner has been Nightshade Seer. That definitely went under our radar, and its reusable, high effectiveness removal can completely destroy decks.

On the personal front, we did end up getting our booster case. 2 boxes go to the class, 2 for Tom, 1 for me, and 1 for our group of friends. It feels like a waste, but we ended up just cracking them instead of drafting. Although we spend just as much time playing super smash bros, it was hard to justify sitting everyone down for a couple hours to do that, and we wanted to get them open to be able to cash in on money cards early. No priceless treasures, though we got a bunch of fetchlands to sell. Tom got a foil Ob Nixilis, and I got a foil misty rainforest, so not all was lost. I think the set is good, though maybe a little overhyped. The good cards are certainly good, though. Already, we’ve got a bunch of new decks built out of it, including an allies deck, a landfall deck, a vampire deck, and more that I can’t think of. Of course, most of it ended up being split among other decks since we’re primarily casual, but they’re fun additions. I myself took the vampire aggro deck and put together a blood tribute/sanguine bond combo deck that’s a ton more fun to play.

There might be more to speak of in the very near future. We just got a pretty big influx of cards that’ll be explained shortly (probably next podcast), and there’s another draft tomorrow, so news is forthcoming.

Week 2 in review

September 30th, 2009

We had our 2nd class last night, and it went pretty well. You can find our practice recording here, and slides here.

We made some changes from our podcast to the actual class, primarily being that we cut out a lot of the chit-chat and got straight to the content. As such, we managed to shave off a good half-hour so we only took about an hour to talk through. It mostly went well, though I was a little unhappy with the presentation of some of the cards and decks. I mentioned that we were going to immediately jump into Magic and really assume that they know the popular decks and the cards. It’s actually kind of ridiculous, now that I think about it, that it’s abundantly clear to me what a blightning beatdown deck looks like, and exactly why a certain card is so good. Those are a lot more difficult to explain when your audience doesn’t necessarily know what cryptic command does.

I was pretty happy with our explanation of tempo and card advantage, though. In my opinion, those pretty much represent the highest level of common Magic theory around. They’re the buzzwords, like AJAX for web dev or bipartisan for politics, that pretty much anyone familiar with the field is going to hear a lot, but really requires a little thought to understand what it means. For me, it was a great reminder about the tradeoff between tempo and card advantage, so that good all around.

After we were done with that, we let everyone get into the card pool to build, and everyone got really into it. Everyone had stacks of cards sitting around them, trying to figure out either how they were going to tweak the deck they were given, or build a new one. I was surprised by how many people were interested in building a new deck. Not surprisingly, green was a very popular color since our card pool is creature-heavy with little control. We actually ended up with a shortage of forests, but since most people were building mono-color decks, we just had them sub in other basic lands.

About 10 people or so ended up staying a full hour past the end of class, when we wrapped things up since we had to get out of there. So getting to play Magic was definitely a factor for a lot of them. Some of the decks looked pretty good from a pretty poor card pool, so I think we should have a pretty interesting metagame emerge.

Zendikar Prerelease

September 26th, 2009

Good news: I was actually winning in a tournament, last done at least 3 years ago. Oh, and Zendikar is a lot of fun.

I went down to the big shop in the area this morning with 2 friends for a prerelease. I’m glad I pre-registered because the line to sign up was out the door, and I’m pretty sure they had to cap. In addition to events just getting bigger and bigger, I think Zendikar was sufficiently hyped, including priceless treasures. The crowd caused the event to fall behind about an hour, but it was well-worth it.

The format was 6 packs of sealed, and I opened pretty good packs. My rares were a Malakir Bloodwitch, Bloodchief Ascension, Valakut, the Molten Pinnacle, Archive Trap, Gigantiform, and a Verdant Catacombs. 2 hyped, limited-unplayable cards, 1 money card, 2 bombs, and 1 decent card. I got a tip that I shouldn’t play white when I opened one pack and didn’t get a single white card. My white had no removal and a smattering of not-so-good allies and kor. And my blue had several playables, but nothing too good to make it worth it, leaving me with black, red, and green. The creature curve for all 3 looked pretty similar, though the quality of those creatures varied widely. The 2 bomb black rares and 4 removal spells made me think black as my central color first, but I saw that my creatures were pretty weak (confirmed when I saw some good black card pools from others). It was painful, but I ended up cutting black. The bloodchief ascension was just too good, though, to not play, so I ended up playing 2 uncommon duals, the b/g fetch, and 1 swamp to make it playable. Ironically, it didn’t matter in a single game I played. I’m thinking that in limited, it might be a “win-more” card, but maybe I just wasn’t properly poised to use it.

My initial build was a r/g aggro deck playing several borderline creatures just because they were cheap, and that was a huge mistake. I quickly learned in a practice game that you can run out of steam very quickly. Instead, it was my 3 and 4 cost creatures that were doing the heavy lifting. Also, there was a lot of talk about playing 19-20 lands in limited decks to help out with landfall abilities, and it definitely didn’t seem worth it to me. I think I had maybe 3 landfall abilities in my deck, and only the Zektar Shrine Expedition was any good. Even so, I had no problem activating it with 17 lands. Perhaps it’s just because I was playing an aggro deck, but you definitely don’t need to scale up. So here’s a round by round


Game 1: He was also playing a r/g aggro deck, and his was better. To my 1 scythe tiger, he had 2. Him playing first meant that I was always a step behind, which mattered with the amount of removal he had. Bad news, and although the life totals weren’t ridiculous at the end of the game, I never felt like I was even with him in the game.

Game 2: 5 land hand with no creatures, mull to 6. I think it was a 2-lander and vaguely playable. He got out a first turn goblin guide, which is nuts. What was worse was that even with that help, I still couldn’t find any land, not helped by the need to play a scythe tiger to get something on the table. He did at least 10 damage, probably more, with the goblin guide alone, and I think I got 2 lands out of it. It was just scary. Granted, I didn’t have a lot of lands near the top, but even so, I don’t think the lands would’ve been able to get around it. Goblin guide should be very good in constructed.



Game 1: He was playing a B/W deck with a bunch of vampires, and he came out screaming. A first turn vampire lacerator into a turn 2 blood seeker with a disfigure and hideous end for removal was bad. Oddly enough, a little bit of life gain and the lacerator damage meant we both got to 15 life around the same time, but it quickly went downhill from there. WHen I dropped below 10, things got ugly with a guul draz specter and a cliff threader meant I was never in the game. After this, I remarked that I was shocked he lost the first round, because his deck looked nuts. I sided in a seismic shudder to deal with things, and I never sided it out. There are a surprising number of good 1-toughness creatures out there, and other than a regenerating river boa, I didn’t have any, so this was amazing for me.

Game 2 and 3: I don’t remember these too well, but I somehow stabilized in both of these after some mean removal. Both of his starts were ever so slightly slower (maybe drops on 2 and 3 or something like that), and I think that made all the difference for me. The expedition’s 7/1 hasty trample was great, and gigtantiform won me games. That card was surprisingly good. I wrote earlier about how firebreathing can make a sparkmage apprentice into a relevant creature, and gigantiform did the same thing for nissa’s chosen and torch slinger. Sure, you might get 2 for 1-ed, but a late 2/2 is pretty much a dead card on the board anyways, and against this guy, at least, he used up his removal early trying to “get there” before I stabilized. I just barely got out of both of these.



Game 1 and 2: He was playing a R/G/B deck, but it really didn’t matter. First turn scythe tiger is nuts. With punishing fire to follow up against the river boa, and it’s a blowout. I really felt bad for him, because it happened twice, and he was having significant color problems, but the games were over far too fast. I think scythe tiger-like power is the only reason why straight-up aggro might be really good in zendikar. In limited, though, I think people are going to find that, plated geopede, and similar cards too sexy to pass, so it might be hard to play that.



Game 1: He was also playing R/G, but it didn’t matter since we already decided to split packs. We played anyways, though, and a first turn scythe tiger got in for I think 6 damage before he stabilized. Unfortunately, that was more than enough. He had some great stuff once he stabilized, but the Hellfire Mongrel was a blow-out. I played it when he had 1 card in hand, and his only chance at that point was to keep playing cards to race. Fortunately, I had a bunch of chumpers and a slaughter cry to fend off the 7/1 from the zektar expedition, and the mongrel got him for about 10 damage. That game was absolutely insane.


Out of it, I got another 3 packs, and my first successful tournament in awhile. I don’t have too many other insights, though perhaps to say that “land matters” is slightly overstated. To be honest, I didn’t see a lot of interaction with lands in my deck. Good to get into your deck, not necessary to have the gas to win.

Report from our first class

September 23rd, 2009

So things might have gotten a little quieter leading up to the first class, but we’ve definitely been ramping up. SInce Tom and I are roommates, our dorm room is very much dominated by our magic cards. We have about 10,000 cards (mostly common, mostly crappy) for the class, and we initially built 30 decks for the 30 students taking the class. In addition, we also managed to convince the guys over at mtgcast to put our practice recording on the network as a podcast, which you can find here.

So there were some pretty significant changes to our presentation after we rehearsed on the podcast. These include

  • there was a lot of general cleanup. We realized we forgot a lot of things, and we could condense here and there
  • we put in one really slick slide with animations to show the stack
  • we moved a lot of the rules stuff from the first segment to the second segment. We wanted to get students playing as quickly as possible, and since the decks we built were very basic, we figured we didn’t have to talk about things like planeswalker or artifacts immediately
  • very significantly, I lost my voice. On the podcast, I mention that I”m under the weather, and I was actually losing my voice then. It might not sound that bad, but my voice is a lot deeper on the podcast than usual. Good thing we did it when we did, as well, because 3 hours later, gone. I’m still resting now, so Tom did the entire lecture in class, but he did a great job, so no worries

We kept iterating on the slides up until about an hour before the class, which I would post, but there’s some vaguely personal information and specific information that we would prefer not to have widely available. The slides that we used for the podcast, though, are available here

On that day, as well, I also mentioned to Tom that we might build a few extra decks in case we have some extra people show up, which was an excellent choice. We arrived to a full room and ended up passing out all 35 decks, with even a couple people in the room without. The demographics of the room wasn’t quite what we were thinking it would be, but were certainly not disappointed to see people. We were hoping to get mostly new players, underclassmen so we actually have something to teach them. On a class poll, most had played before, and more than a couple had experience with the topics we’d be teaching. And amazingly, not everyone in the room was male. I’m glad to see we’re getting better balance than most local tournaments.

So the lecture part went well. We got additional help from George, a level 3 DCI judge who’s also a student here at Stanford. Fortunately, we didn’t embarrass ourselves by explaining anything wrong, only asking for confirmation on a couple things we talked about related to planeswalker. Through the lecture, we got some good questions about rules, and it definitely seemed like people were interested.

All in all, I was pretty pleased by how it went. Attendance was good, and people seemed engaged and having fun, but we’ll see if we have a good return crowd for next week. As far as content here goes, I think we might be a little silent on the blog. We’ll be working a lot more, but things go hush-hush as we’re on good footing with what we want to present, and really want to give the first look to students now. I’ll probably continue to do weekly reports here, and now we’re on MTGCast as well (thanks Tom!), so every Wednesday, our practice should go up.

So yeah, Tom and I are pretty pumped up about this. Things look good, we have 24/7 office hours, and we’re prepping for the rest of it.

Plain text flier

September 16th, 2009

Here’s the email I spammed the lists with. We’re gearing up to start this next Tuesday, so things might go a little quiet here, but maybe I’ll come up with some interesting content as the class goes on.


Ever been daydreaming in class about what would happen if a dinosaur were hit by lightning?

Boom! Pet dead.

Well, there’s a course where you’ll actually be on topic!

I know a lot of you are just trying to figure out classes and gearing up to do as much as you can, but for a change of pace, you might take

SYMSYS 15SI The Theory and Design of Magic: The Gathering

Maybe you have fond memories of junior high either playing or harassing the nerds who played at lunch, but whoever you are, this class is going to be a ton of fun. Perks include:

– getting to learn how to play Magic. Who knew you could get college credit to play a card game? If you’re not familiar with it, Magic is a card game where you use mana to make faeries and mutant bunnies attack and blow up the world. Think Pokemon, but way more legit (though maybe not quite as cute). We’re going to start from the basics and rules of the game, so everyone is welcome!

– ever wonder how combinatorics or nash equilibrium might matter other than at 3:00 AM on a scribbled mess of a pset? We’ll have interesting examples of how you can apply classroom material to something real (sort of)

– exposure to a lot of the Symbolic Systems major. We’ll be talking about Game Theory, Statistics, Epistemic Logic, AI, and more, so you’ll get a great look at the rest of your major if you’re considering symsys

– already an experienced Magic player? Great! Although the class is targeted towards new players, we’ll be covering new and exciting material so you can learn something, too

We’ll be meeting on Tuesday nights, 7-9 in 200-217, and you can sign up in Axess for the class. Even if the class is full, show up on the first day in case of drops.

See you there!

Kevin and Tom

The Icarus Cognitive Architecture

September 3rd, 2009

In my last post, I talked mostly about Knowledge Representation (KR), an area of AI where the intelligence is logical inference on statements. In an example there, I showed how First-Order Logic provided the symbols to have a computer infer that a creature was tapped. KR is very good at making inferences about and understanding its environment, but perception is half the battle for intelligence. You also need to act, and that’s where cognitive architectures come in.

Cognitive architectures attempt to provide an integrated system for all sorts of intelligent behavior. How this happens is fairly broad, but generally, you need some components for recognition and some for action. Some of the better known ones include ACT-R, Soar, and Prodigy. The one that I know about is Icarus. I’ll give you a quick run-down about how it works, and then show it in action. You can read the manual if you want a more complete picture (it’s fairly well written and not too technical), but I’ll try to pick out the important parts.

Icarus is a goal-driven architecture. When it starts, you give an agent a certain goal, and it attempts to use various skills to work towards that goal until it recognizes that it has been completed. An agent will work at this goal for a given number of cycles (or ticks). On each one of these cycles, it first looks to see which percepts are satisfied. For example, you might have a percept that recognizes a creature that either has haste or been under your control since the beginning of your upkeep. On top of these percepts, Icarus can make inferences to come to beliefs about the world. We say that the agent has “concepts” of what potential “beliefs” there are. An example of this might be (blocker ?creature) which specifies that a creature should be used as a blocker because it satisfies readiness, your opponent has a creature, and has a much higher toughness than power. As it is, (blocker ?creature) doesn’t mean a lot, but it might be leveraged later to determine an action.

So percepts and beliefs are our grounding in KR. We also have a goal, which is a belief so that we can recognize that our goal has been completed. The last part here is the set of skills that our agent has. These skills have start conditions and functions that are invoked to make things happen. These functions are the actions; they can actually change the environment (usually by manipulating the variables representing the environment). If an agent sees that its goal has not been satisfied because the goal is not in the set of percepts or beliefs for this cycle, it will invoke the skill that should cause this goal to be reached. This becomes even more powerful because Icarus has hierarchical skills as well. This means that skills can have subgoals which invoke other skills that must be satisfied first. For example, the (cast ?spell) skill might have subgoals of (mana ?cost) and (target ?creature).

So that’s a lot of junk. I have no idea if that makes any sense (actually, tell me if it doesn’t, because it means I need to refine this for the class), but I do have some examples of this at work. The code I’ve linked to is Icarus code. It’s definitely not like C because it’s all written in Lisp, a very popular language among AI researchers. I’d like to hope it makes sense on its own, but I might have lived in code for long enough that code looks like plain English to me (that’s a tragic thought). An important thing to note in all of the code is that in Icarus, anything that has a question mark in front of it, like ?creature, is a variable, and most other stuff is a constant. And anything with a semicolon in front of it is a comment, absolutely in plain English so I can try to explain what’s going on. So you can take a look at my very simple Icarus agent that determines whether a creature should attack, and how much it needs to pump before it’ll attack with it.

Magic Icarus Agent Code

So we can see the output for the running of this agent here. You can see its goals, percepts, beliefs, and what skills it’s trying to execute on each cycle. In this case, on cycle 1, it sees its goal is attack-set. It gets the skill for that. On cycle 2, it sees that it needs to satisfy one of its subgoals, so it executes attack. Note that it already knows that craw wurm is the strongest, so it can skip that subgoal. On cycle 3, it sees that it satisfied all of the subgoals of attack-set, and on cycle 4, it declares attack-set completed. Fun.

But maybe that’s not really that impressive, so I ran it again. In this run, you can see that the first thing I do is add a new creature to the enemy side; a Kalonian Behemoth. The big difference here is that it first sees that our creature isn’t the strongest. To make this belief true, it has to use both of its subgoals. Maybe it doesn’t sound so impressive, but I think it’s neat that we have a single agent that behaves differently based on its environment.

So hopefully that gives you a sense about how cognitive architectures work. Of course, I realize that my agent isn’t nearly powerful enough to actually play magic. I do think, though, that something very impressive could be built out of it. Compared to our minimax AI, I think it’s very clear that this “understands” Magic far better. It recognizes parts of the environment and has a relatively clear line of deliberate actions and skills to help it reach the goal of winning.

But your likely skepticism is warranted. There are a few major drawbacks here. One, there’s a lot of code to do this. As I mentioned last time, it might take hundreds or thousands of predicates (or percepts or concepts) to encompass Magic, and although it might be more true to life, that’s a lot of code that has to be hand-written. And that’s one of the real problems for researchers interested in cognitive architectures: a lot of the knowledge has to be done by hand. And if it’s done by hand, you’re hard-pressed to argue that your agent is intelligent. Instead, the intelligence happens to all be that of the person who programmed the agent. Thus, a big part of research in this area is to provide generalizable knowledge that extends past domains. For example, an agent that could play Magic would be good, but if that agent could play Yu-Gi-Oh based entirely on its own reasoning without additional code, that would be tremendous.

Another drawback is that these agents are bad with numbers. It’s hard to imagine computers being bad with numbers, but you can kind of see that with this agent. For example, let’s say you wanted to figure out how much you want to pay for your firebreathing. You might test it with 3, then 4, then 5. That’s hard for an agent to do because it doesn’t support numbers as variables as part of the state. Or maybe you wanted your goal to be to minimize the damage you take this turn. It doesn’t deal with that too well, either. These, however, would be easy for a statistical algorithm. It would just run a for-loop over those values for firebreathing and see which had the highest resulting evaluation.

So that’s a look at using a cognitive architecture to play Magic. Likely more difficult to do than just programming it straight up, but for cognitive architectures, Magic is just one of many domains it might try to tackle. Large, statistical algorithms are definitely more popular now, but maybe we just need a good presentation of an generally intelligent agent to prove that symbolic AI has some promise.

And by the way, big Zendikar spoilers coming out as I write:

Symbolic AI and Knowledge Representation

August 31st, 2009

I have no excuse for why I haven’t written. Know that it isn’t because we aren’t working on the class, though, because that has been progressing nicely.

I mentioned in a previous post that I’ve spent some time working with a cognitive architecture, and it seemed like a good place to test out some Magic logic. Specifically, I was working with the Icarus cognitive architecture, designed by Pat Langley and maintained by his lab. Cognitive architectures aim to model the logic and behavior of a thinking system as a path towards AI. Notably, it tries to give a symbolic, big picture approach to AI. Although Google’s search algorithm and alpha-beta pruning are both products of AI, neither really matches how people think. We don’t know to go to for baseball news because a million people linked to it; we know because we understand what mlb represents and the connection to other ideas.

And that’s one of the major “religious” goals here: learn a lot by a single example. Data mining requires condensed information thousands of examples. Cognitive architectures require detailed information from a single example. One isn’t necessarily better than another, but are instead different approaches t learning. As an analogy, data mining is like heavy playtesting for tweaking. When you know how to play your deck, you might look to play many, many matches to know whether you need 3 or 4 lightning bolts in your hand. And you can learn a lot about your deck that you couldn’t from playing one match. But you’re learning so much in just even that first game. For example, I was watching a Standard B/G Elf deck play against a Jund Aggro deck a couple weeks ago. I understood that Chameleon Colossus was good, but only when watching the Jund player squirm did I realize how well it works, with lightning bolt, terminate, and maelstrom pulse all being useless. I didn’t need to watch 1000 games to know that the Elf deck will do better with more Colossuses in; I saw and understood that in one go. How? There wasn’t nearly enough statistical data to do that sort of analysis. For cognitive architecture people, maybe it’s logic.

If you’re not familiar with First-Order Logic (FOL), it’s not really that important. Just know that we have a very good way of formalizing to say a variety of things. It takes a bunch of statements, evaluated to be either true or false, and tries to chain those together into a much larger and more powerful language. Logic is definitely philosophy stuff, but in AI, we have Knowledge Representation, or KR. KR attempts to encode our knowledge into logical statements and make inferences based on that data.

For example, here’s an example involving what happens when creatures attack. First, we need to define several predicates. Predicates are similar to functions but only return true or false depending on the values passed to it. Let

attack(x, t) be a predicate that means that creature x attacked on turn t, so attack(“GrizzlyBears”,3) means that you attacked with a Grizzly Bears on turn 3

tapped(x, t, p) be a predicate that means that creature x is tapped during turn t in phase p, so tapped(“ElvishArchdruid”, 4, “1stmain”) means that the Elvish Archdruid was tapped during the main phase of your 4 turn

after(x,y) be a predicate that means that phase x is after phase y, so after(“combat”, “upkeep”) means that combat comes after upkeep.

As a matter of convention, all of the single letters are variables, and the constants are put in quotes. This scheme isn’t really standard but will work well enough for our purposes.

So, we, of course, known that when you attack with a creature, you have to tap it. We could encode this in First-Order Logic as follows:

∀c∀t∀p ((attack(c,t) ∧ after(p, “combat”)) → tapped(c,t,p))

That looks a little weird (and might be wrong, so someone double-check me on that), but let’s break it down:

  • ∀c∀t∀p means “For all c, t, and p”. c,t, and p are all variables (just like in algebra and programming), so this says that the following statement will apply for all values of c, t, and p.
  • (attack(c,t) ∧ after(p, “combat”)) means that it is true both that creature c attacked on turn t and phase p comes after combat. The ∧ means “and”, which is why both the first part AND the second part must be true
  • → means that something implies something else. In this case, it means that the bit we just looked at implies the rest. We can say that something implies something else if either the implied part is true, or the implying part is false. It can also be read as “If A, then B”. Maybe this will make more sense when we put it together
  • tapped(c,t,p) means that creature c is tapped on turn t during phase p

So when we takes that all together, the sentence says:

For all c, t, and p, if creature c attacked during turn t, and p is after combat, then c is tapped during phase p.

This should make sense and is generally true. We could probably consider this one of our known truths (axioms) in Magic. Of course, things like vigilance, dying, untap abilities, and more don’t necessarily fit this, but we could extend our set of predicates and axioms to include those. And it’s somewhat vague, as there might be multiple combat phases and such, but this is just a model.

So why does this matter? Because this sort of sentence allows us to make inferences about a situation. For example, let’s say we know that


is true, so a Raging Goblin attacked during turn 1. If we assert that

∀c∀t∀p ((attack(c,t) ∧ after(p, “combat”)) → tapped(c,t,p))

and we know


is true, then we can infer that

tapped(“RagingGoblin”, “1”, “end”)

So we know that the Raging Goblin is tapped at the end of turn 1. You were waiting for something more insightful, eh?

So this might seem pretty simple, but you can imagine that if you add enough predicates, it can do more and more complex inference. We might be talking hundreds or maybe even thousands of predicates and axioms (without even trying to encode individual cards), each with tens of arguments, but when you think about, this is all stuff that you know as a player. When you learn Magic, someone has to tell you that there’s a main phase before and after combat, and all creatures untap at the beginning of your turn, and creatures can’t attack or use tap abilities unless you controlled them since the beginning of your upkeep.

I’ll get around to talking about the advantages and disadvantages more fully about this approach later, but it might help to put things in perspective if we take a moment to compare it to Alpha-Beta Pruning and Minimax (I’ll use ABP to represent this class of algorithms, though that’s probably misleading and wrong), a statistical approach to AI. Read that if you haven’t, but quickly, we can represent Magic as a set of positions connected by actions, and we’re trying to search over that tree of positions to find the path that gets us the biggest reward (likely where you win). It’s a little tricky, since the tree has to have different levels and links for your actions and your opponent’s actions, and there are a lot of positions in Magic, but alpha-beta pruning can speed that up.

Anyways, note that in KR, the computer actually “understands” what’s happening. Using →, it has axioms that see the consequences of tapping a land or drawing a card. For ABP, it can see how the game changes, but even that doesn’t matter that much to it as it just collapses all of that with the evaluation function. While the resulting behavior can certainly be the same, KR seems much more similar to how we as humans think, and intentionally so. If you were to see a printout of ABP evaluation, you’d probably get a bunch of indexes and see it total various positions. If you were to see a printout of KR evaluation, you’d see various values being plugged into logical sentences, trying to reason out what else is true.

Hopefully by now, I’ve proven to you that KR can do a lot in understanding a game and determining what’s true and false. Understanding the rules of the game and what is true is much different from knowing how to play the game, though. Although knowing that your Raging Goblin will be tapped after attacking is a necessary pre-requisite to playing well, the game is about determining whether it should be attacking and how you’re going to reach the goal of winning the game. That’s where Icarus comes in; it’s a goal-driven cognitive architecture with beliefs and skills and actions and goals to take KR and turn it into a decider.

If you’re still skeptical that KR will give us a complete basis for Magic playing, though, I promise you, you’re absolutely right. There are some pretty gaping holes that, even if not impossible to fix, are amazingly confusing and overly complex to work around. I’ll probably address that at the end of this series, but definitely comment on the limitations of KR. It would be really helpful to me to know how much about the idea of KR I’ve conveyed in this, and a good exercise to think about what is possible. I’ll probably try to address them next time as well when I talk about Icarus.

Some thoughts back and forth

August 18th, 2009

One of the things I’ve been trying to do is to get some opinions from some more prolific people in the Magic community. It seems like a pretty natural instinct to appeal to the most knowledgeable, and fortunately, I got a hold of Frank Karsten, recent Magic Hall of Fame inductee and Magic writer, including several pieces on Magic. This is going to be a somewhat long post, but here’s what our email exchange looks like. Feel free to add in on any of the points in either:

Frank to Tom and me

Course Syllabus

A Class? On That Silly Card Game?

Game Design:

  • “…by understanding the intent of design, one can become a significantly better player.”; you may (instead) argue that learning something about game design may also be useful for computer science students when making computer games or something like that.

Game Theory:

  • “The history of game theory comes more from political situations and the arms race”; I think historically, it actually originates from an analysis of parlor games and of economic situations of coalition formation (Von Neumann and Morgenstern’s 1944 Theory of Games and Economic Behavior).
  • “where the choices one must make choices”; the second ‘choices’ is superflous
  • “whether to bluff, call, or fold”; so in poker bluffing is equal to raising? J

Week 1 – Overview of topics and the rules of Magic

Week 2 – Deckbuilding Basics and “Card Advantage”

Week 3 – Game Theory in Multiplayer games

  • I never play any multiplayer, so I may be biased here … but I would move multiplayer (if you want to cover it at all) to the end of the class, or at least after probability and deckbuilding. I would rather first teach everything about the game itself and then afterwards move on to extensions such as multi-player Magic. Putting it in week 3 seems too early, especially when not everyone is a solid Magic duel player yet.
  • Note that game theory is not only applicable to multiplayer games but also to two-player games. I regularly roll dice on the Pro Tour to decide whether to block or not (since a mixed play leaves no strategic holes that can be taken advantage of by a good bluffer, as partially explained here, for example. A game-theoretical analysis of bluffing is also applicable to games such as poker.

Week 5 – Statistics and Simulation in Deckbuilding

  • Wait, what are those articles on e.g. tempo doing there? I don’t see what that has to do with statistics.
  • However, statistics can be a very useful tool in building decks and playtesting. In addition to the relevant and valid topics you want to tackle in this class, I can add some statistical questions that I had to answer in my preparation for Pro Tour Honolulu (these are real examples of how probability theory can be applied to relevant questions and are straightforward exercises on conditional probability):
    • With X lands and Y creatures in your Z-card deck, what is the probability that a Gift of the Gargantuan will yield either one or both?
    • When deck X has an A% chance of winning before sideboarding against deck Y and a B% chance of winning after sideboarding against deck Y, what is the probability of deck X winning a match against deck Y?
  • You could also discuss mulligan decisions here and use probability to show that keeping one-land opening hands is almost always a bad move. For example, take a one-land opening hand and calculate the probability of finding at least one land in the top 2 cards of your deck. From that extrapolate to the odds of winning the game if you keep the 7-carder and compare that to an (estimated) odds of winning the game if you go down to 6 cards. If the latter is higher (it almost certainly is), then you should mulligan.

Week 6 – Epistemic Logic and Limited

Week 7 – Metagame and Applications of Graph Theory

Week 9 – Presentations

  • You may want to plan this part out a bit further. Build a deck for what format? Do you assume that everyone has all the needed cards at his/her disposal?

General Resources

  • “the makes of Magic” -> “the makers of Magic”
  • You can also add
  • And my less formatted response:

    Week 1

    Our class is intended to be just as appropriate for beginners as it is for experienced players, so no assumptions about what the students know. Our first class is an intro to the rules, and we’ll get them into games shortly after that. We’re going to recommend that they heavily visit our 24/7 “office hours” to get experience playing over that first week so that we could begin talking about more real things starting week 2. Since Magic is more the context than the point of the class, we don’t want to waste any time on that.

    The motivation for the articles that we picked is that it would be more helpful for them to have references instead of explanations of the rules (especially since readings for the first week will be done after, not before that class). Of the 3 or 4 friends to whom Tom and I taught the game in our dorm room, they all picked up the game really quickly and, as soon as they were told, understood why you play instants during your opponent’s end of turn phase and what to look for in using counters. I’m trusting that students are pretty smart and see the biggest obstacle just being how much they know about existing magic cards and popular decks. It’s usually pretty easy to see how a deck works and why it might be good. It’s a lot more difficult to try to understand why that deck might be good in a given format, especially if you don’t know what cards are there.

    Do you think those are fair assumptions about how to put this together, based on your experience with new players? This is actually a fairly big concern that we have, because if we don’t get the class off on the right foot or have the proper basis for the situations to come, we’re hosed.

    Week 3

    I’m thinking the multiplayer is a dorm room bias because I actually got a lot of feedback telling us, like you mentioned, to move multiplayer to the end of the course. As I mentioned, Tom and I are mostly casual players, and when we play, it’s pretty much just whoever happens to be sitting in the room. Given that, I still usually prefer playing 1 on 1 games, but I think the move to multiplayer early gives us a wider space to discuss game theory without introducing additional rules complexity. Since a lot of games are cooperative (you get a lot more games when not everything is 0 sum), I think that makes more sense when you have potential allies and not just one guy across the table trying to beat your face. The goal of the class is to demonstrate interesting ideas with the side effect of developing better play skills instead of trying to develop a rock-solid basis for future pro magic players (though I’d be proud if that happened), so I figured I would bend things a bit to make way for what I think is interesting. Game theory, I think, just makes a lot more sense and is more approachable earlier in the class instead of hitting with graph theory. Given all that justification, though, I’d be happy to listen to alternative schemes and reasoning for structuring that.

    Week 5

    Yeah, I think mulligan does make a lot of sense with statistics. Combinatorics is obviously huge when determining the composition of an opening hand, and it just keeps on going from then on. That sounds like a great application; thanks.

    And if you happen to have real examples of some analysis that you’ve done, I’d be very interested to see it. Certainly don’t go through the effort to write it up if it’s not in an available format, but I think it’d be great to work in analysis from “real REAL” magic so that there’s something to present to the hardcore magic community and not just toy examples to satisfy the class.

    Week 9

    Pretty much our idea for how presentations and cards would go is that Tom and I have a decent supply of extra cards, mostly bulk commons (whoever needed 50+ copies of CoP:Red?), and we would build some initial decks for them and let the rest of those cards be their entire card pool. Though it might be an interesting experiment in game theory, we’re going to bar outside cards from getting into the class environment. That way, we don’t have to worry about the class becoming unbalanced or unfun just because someone was willing to invest more into the class. The only trickiness there is that some cards will be scarce; I’m sure the 1 or 2 sudden deaths we have will be greatly desired, but we’re not too worried about that. The card pool isn’t going to be super-cohesive or uniform, but when our budget is 0 and we’re running the class out of our pockets, that’s about what we’re willing to offer.

    And Frank’s response:
    Week 1 => My experience with newer players is very limited. The last time I taught a new player was during last century. Furthermore, a completely new player would benefit more from being taught by someone who learned Magic a couple months ago than by someone who plays on a much higher level. That makes it much easier for the teacher to relate to the new player. That’s something to keep in mind.

    Week 3 => I understand where you are coming from. If you keep it in week 3, I would personally name the class ‘game theory in single- and multiplayer games’ (rather than just multiplayer games) and focus on applications of game theoretical concepts to both types of games. That is, I would spend an entire class on multiplayer games that early.

    Week 5 => Can’t think of any relevant analysis I’ve done in the past from the top of my head, but I’ll take a look at archives sometime soon. I’ll let you know if I find anything.

    Week 9 => If three players all want the same Sudden Death, this may get annoying. Another idea is to split the class in 5 groups after a few weeks and let every group build a mono-color deck. Then unfortunately not everyone has their own deck, but there will be no unfair allocations of cards and the deck building process becomes a cooperative group process rather than something everyone does individually. Don’t know if this is more desirable, but I’m just tossing out ideas.

    More ideas then … as for week 8, you may also consider doing something with search algorithms in deck building. An AI that builds decks has to take into account that adding e.g. just 4 Channel or just 4 Fireball to a given deck won’t improve it, but adding 4 Channel and 4 Fireball to a deck makes it better (use any 2-card combo for this example). Theory on search algorithms that use this logic may be interesting, perhaps?

    Definitely some much better ideas in there than what we’ve come up with. Let me know if anything in there stands out to you as important.

    Who Says Red’s No Good in M10?

    August 15th, 2009

    (This post has very little to do with the class. Just my observation from a night at FNM)

    For about the first time since Kamigawa, I’ve been paying attention to drafting, mostly because I’m actually going to FNM, and, for the first time, I actually stand to benefit from knowing. One of the most commonly discussed topics is what colors are the best. Here’s what I heard:

    • White: It’s solid, and probably square in the middle. The opinion about white has been pretty stable. Obviously, both Serra Angel and Baneslayer Angel are amazing, and Safe Passage has been a good surprise. Minor soldier themes work out pretty well, and having both cheap creatures and big fliers mean that it can be flexibly played both as an aggro and control color.
    • Blue: Initially, everyone thought it sucked. Its removal looked weak (I lost an Ice Cage to a Jump, once), and its creatures are a little wimpy. Then everyone found out that blue is awesome. Its fliers are pretty solid, Sleep wins games, and card advantage has turned out to matter a lot. I think the biggest discovery with blue is that M10 is actually a fairly luck-dependent format. As such, you pretty much win if you get good bombs. And the only way to beat bombs is to have good counters. Right now, I would say that blue is considered the open secret in M10 limited.
    • Black: Black has been good, and continues to be good. About the only complaint is that the good black cards are very color hungry, so it has to be a main color. Mono-black is a great deck to have: it has removal, creatures, and card advantage. Probably is (and people know that it is) the strongest color.
    • Red: Red looked really sexy when it first came out. With Wizards moving towards creature-heavy games, they brought back Lightning Bolt and Ball Lightning. There are the bombs, and there’s repeated removal. What people noticed really quickly, though, is that beyond that, red is very shallow. Quickly, you’re looking at 4/1 hasties and 2/1 for 2 as the new hotness. Not so much. Thus, it has been relegated to splash status at best; like black, its color requirements are heavy, and people are going to draft the good cards to splash, so it really can’t be a maindeck color. This is well known.
    • Green: Green started out looking really good, and it is. It has fantastic creatures (I’ve only found 2 ways to kill cudgel troll in M10: polymorph and planar cleansing anyone know any others?), acceleration, a little removal (did you know that Deadly Recluse is just as good as a Serra Angel?), and the bombs to make the world go round. Howl of the Night Pack + Overrun is just disgusting. Actually, just Overrun is disgusting. Even so, I think the open secret right now is that it’s overrated. There are a lot of creatures with more toughness than power, and a lot of games end up in the mid-game stalemate with 5-6 creatures on both sides. At that point, green doesn’t have the evasion to win. Its best chance is overrun, and when people see it coming, they can deal with it. I would say the other open secret is that green isn’t that amazing. It’s good, but it’s not the automatic win.

    So what does that mean the best color to play is? Well, 2 weeks ago, I would’ve said blue. LSV has been touting U/W skies as a legit deck, and it works. Blue isn’t the strongest color, but would seem to be the best metagame choice for balancing power level and popularity. Now? I think mono-red is worth a shot.

    Note that above, I said that red isn’t great as a maindeck color. Which might be true. Go mono though, and it might go great. As far as popularity, yes, you’re not going to get passed a fireball or earthquake. That’s life. You’re not going to get passed bombs. That’s also to be expected. These aren’t game breakers. People might still pass you some very good color intensive creatures and removal. So availability of quality cards is high.

    Card quality is also a lot better than you might think. 2 cards that I think have been great surprises are Viashino Spearhunter and Kindled Fury. First strike is huge. The creatures may not look beefy, but they’ll stand up in combat, and will do just fine. I think the important choice here, though, is that it works only really well in mono red. Firebreathing is absolutely insane in mono-red. You might think that it’s a 2-for-1, but if you play it on a sparkmage apprentice, you hopefully found one of the many good targets for the 1 damage, and you made a 1/1 something to pay attention to. They actually might need to expend removal on it. At worst, the block it, and you use your 8 mountains to kill a Kalonian Behemoth.

    So a lot of that sounds speculative, and it is. Here’s what I managed to draft at FNM, though, with my deck being all the red stuff + the howling mines:

    17 Mountains
    Creatures (14)
    1 Goblin Piker
    1 Sparkmage Apprentice
    2 Fiery Hellhound
    1 Goblin Chieftain
    2 Prodigal Pyromancer
    2 Viashino Spearhunter
    2 Canyon Minotaur
    1 Dragon Whelp
    1 Beserkers of Blood Ridge
    1 Shivan Dragon
    Other Spells (9)
    1 Act of Treason
    1 Kindled Fury
    3 Lightning Bolt
    2 Firebreathing
    2 Howling Mine

    1 Angel’s Mercy
    1 Glorious Charge
    1 Veteran Armorsmith
    1 Convincing Mirage
    1 Levitation
    1 Telepathy
    1 Mind Shatter
    1 Sanguine Bond
    1 Birds of Paradise (!)
    1 Borderland Ranger
    1 Bramble Creeper
    1 Centaur Courser
    1 Emerald Oryx
    1 Fog
    1 Lurking Predators
    1 Mist Leopard
    1 Oakenform
    1 Rampant Growth
    1 Regenerate

    Maybe not too exceptional until I point out that I was actually rare-drafting here. Since I have to take the train home after FNM, I can never stay for the 3rd round, so the best I can ever do is to go 2-0 and get 1 pack for it. Instead, I find that it’s usually worth it rare-draft instead and take the money while I can. Here’s more context

    • My opening pack had a foil howling mine and an guardian seraph. I went with the money and took the howling mine, so I knew I wasn’t going to go white, and that the guy on my left probably would. I think I also shipped some good blue cards, so that was out as well
    • My 2nd pick had not a lot notable in it. All I know is that I rare drafted a Lurking Predators.
    • Going through the rest of my first pack, it looked like I would be going red/green. I took some fogs and mid-rangy green creatures. The quality of the cards wasn’t great, but such is life. I’m pretty confident that the reason why is because the guy on my right was also drafting red/green, and because I was rare-drafting, I had missed the signals. Oops. Apparently, he got quite a few lightning bolts.
    • My 2nd pack had a Birds of Paradise and a Fireball. As I said, I was money drafting. Had I known that I was going mono-red, I would’ve looked at the fireball for 1 more second, then taken the birds.
    • I think in picks 3-6 in the 2nd pack, I got 3 Lightning Bolts and had to pass in Goblin Artillery in one of those. This was a huge clue that red wasn’t being played around most of the table
    • My 3rd pack opened with a Shivan Dragon, I think. Or maybe it was the other howling mine. I can’t remember
    • So in theory, I was getting cut off from red again this round, yet I still ended up with some good stuff
    • By the time I was done drafting, I still didn’t know I was playing mono-red, so I had passed both Seismic Strikes and a Pyroclasm out of ignorance and greed

    When I put my deck together, it was red/green. I was actually going to get lands when I counted my cards and realized I only had 6-7 green cards, and they actually weren’t amazing. At that point, I counted and saw I could make mono-red if I put the howling mines in. Gross. Even so, I had heard good things about playing mono colors. Fewer mana issues justify the slight loss in power, so I did it.

    And it really worked. Round 1 was basically the story of me not having drafted Seismic Strike. I can’t deal with Serra Angel, and that was bad news. Even so, I got an amazing win in the 2nd game doing 5, then 7 damage with a Dragon Whelp. Lost that one 1-2. In the 2nd round, I lost the first game to a Baneslayer Angel. Game 2, the Dragon Whelp came again, and in game 3, double lightning bolt took out a Baneslayer Angel, and a Shivan Dragon for 9ish + another lightning bolt.

    So 6 firebreathing cards was great. Having 17 lands causes a minor flood every game (since I really don’t need the high land count to fix colors, but having exactly 23 playable cards meant that I literally could not replace a mountain with another card), but that’s not bad news when you can firebreathe up to 10 damage. I mean, when you’re 1-2 lands from overcoming a righteousness, I think that’s good. Actually, 6 firebreathing cards is disgusting.

    Granted, while I’m moaning about how my deck would’ve been better had I taken the fireball, pyroclasm, goblin artillery, lightning elemental, seismic strike, and other good creatures, my deck was still pretty good. 3 lightning bolts + shivan dragon and more is nothing to scoff.

    Which is exactly my point! I was on the left of someone drafting my exact colors, and I wasn’t intending to build this deck, but simply picking half-decent cards netted me a good red deck. I think it’s an archetype that’s worth a shot if you notice you’ve picked up a couple good red cards.Of course, this is all based on a single draft, so I might be horribly wrong, but it’s worth considering. And remember: firebreathing is amazing, and love the fact that you can get it 13-14th pick.

    Standard Metagame and Iterative Deletion

    August 8th, 2009

    I guess we just had nationals a couple weeks ago, and the results were very interesting. Of course, all the big name decks made appearances, and since I don’t play professionally, I’m actually very much out of the loop on what’s going on there. What I thought was interesting, though, was the metagame shift from one week to the next. While we saw a bunch of fae and elf combo decks doing well in the first round of nationals, we see that fae got severely hated out of the US nats finals (32 copies of great stable stag, 31 copies of volcanic fallout), while decks like jund seem to do a little better. Great to know, but perhaps not so helpful right now.

    I think this is actually my first shot to see whether some of what I know will be useful. In the game theory class from Yale that I’ve been following, we’ve talked a lot about iterative deletion. The idea basically goes that we have some game. There are a set of strategies that are dominated by another. Therefore, we might assume that no one will play those strategies. With that new game, though, there are more strategies that no one will play, so we can eliminate those. Those ones are only strictly dominated if we assume that everyone else is rational. From those, we can eliminate even more, and maybe see it converge to something. This is very well seen in the “guess 2/3 of the average” game.

    I skate over the subject because 1) I’ll cover it more rigorously if I think this can go somewhere 2) I’m feeling lazy right now and 3) because a very excellent article has already been written on a similar subject. John Beety wrote a great piece on how information about how other agents acts will affect your own decision. So if you know that most of the field will play deck X, you should play deck Y because it has a good matchup against that. A bunch of people might know that, though, so you’ll see the popularity of deck X be followed by a surge in deck Y. That’s the metagame shift.

    That’s kind of where we are right now. I mentioned we had a shift just recently, and I was thinking that I might be able to actually apply it to the current metagame. If someone’s done this rigorously already, please let me know so I can save myself the effort. If not, though, I’d be willing to give it a shot. There are a lot of numbers to crunch, but I think that’s where my programming background will pay off.

    This is where I very much need your help. As I mentioned, while I know what the decks do, I actually know very little about matchups. To be honest, I’ve never actually seen most of these decks played (so on a side note, if anyone knows anywhere where I can watch magic games, either videos or spectating online matches or something, please let me know. Right now, I just have a couple youtube subscriptions for that), so I really don’t know what deck beats what with what regularity. So that you can help me, I created a google spreadsheet that is openly editable that can just does matchups. The first page is the observed probability that the deck on the left column will beat the deck in the first row, given the numbers from this article. Let me know if these numbers are somehow skewed by low frequencies or if more data is out there. The second sheet is completely empty, where it would be really helpful if you could just write a sentence or two about what the perception (qualitatively) is about which deck should beat which, and why. I think I have the knowledge to do the analysis of the metagame; I just don’t have the data.

    Hopefully, assuming it gets filled in well, I’ll be able to come back in the next couple days to a week about my findings. There’s a good chance that the analysis will just reinforce what everyone knows, but maybe there’s a surprise out there.