Archive for September, 2009

Week 2 in review

Wednesday, 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

Saturday, 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

ROUND 1

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.

0-1

ROUND 2

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.

1-1

ROUND 3

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.

2-1

ROUND 4

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.

2-1-1

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

Wednesday, 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

Wednesday, 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.

****PLEASE FORWARD WIDELY****

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

Thursday, 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:

http://mtgcast.com/?p=2365