Archive for December, 2009

Week 10 Podcast Up

Friday, December 11th, 2009

Our last podcast went up on mtgcast. It’s got the usual recap and thanks in there, so give it a listen if you want to hear the closest Tom and I are going to get to being mushy about Magic.

It looks like we already have 1 final paper posted here to the blog. We’ll be reading them and maybe posting the ones that seem like they’d be interesting to the broader public.

I think this blog may go silent, though let us know if there’s anything you want us to write about. The only thing off the top of my head is a U/W standard control deck I’m working on that’s doing half-decent. Since I’m on break now, I might just get the motivation to post that and talk about it some.

Keep us in mind, though, as we may return next summer. We talked to our faculty sponsor, and he said that the dept would be fine having the class taught again next year. If so, we might try to vamp up the material some, including potentially more, deeper content. We want to keep it fresh for us, too.

Until then, thanks for reading! It’s been a great quarter.

Magic AI by Gabriel Kho

Thursday, December 10th, 2009

My first experience with Magic: The Gathering was when I walked into my local comic shop one day at the tender age of 11. My only previous experience with card games was with the Pokemon: TCG. Then before my eyes I saw Magic: The Gathering Starter Set for some block I forgot about. Unfortunately, I found the card game’s instructions too complicated to follow so I abandoned it, though I must confess card games interested me, not because of the underlying strategy, but because I was interested in the art and the collecting aspect of TCG’s. Eventually, I saw the beauty in the strategy and metagme.

Flash-forward to freshman year of Stanford (2009), my RCC e-mails my freshman dorm about this Magic: The Gathering course. The fact that it was categorized under Symbolic Systems caught my attention because I was thinking about majoring in it. Also, I saw a video about a Starcraft class being taught in UC Berkley. I thought it might be a cool idea seeing how Magic: The Gathering implements game theory, game design, statistics and a breadth of other fields.

One of the areas of interest that I found fascinating was the AI. Unfortunately, I was absent for that lecture because I was busy taking a midterm. I am also not an expert in the field, the most advanced course I’ve taken to CS is the intro course. I heard Kevin made an AI that would run Magic: The Gathering. I am far from being even competently versed in this field, but I think it would be cool if someone could make an AI that could make strategies, or recognize combos when they exist. Maybe one day, there could be a Magic: The Gathering World Championship for AI. It would even cooler if it was a Draft or Limited format.

The different fields that contribute to your decision-making within the card game also fascinate me. Example, epistemal logic, knowing what your opponent knows helps determine your decision like if a player should play a creature or not. In that scenario, statistics helps a player understand the possibilities. Applying game theory to analyze what the best options are is something I never thought about. I think that all these fields coming together to produce an AI is an exciting concept.  I researched this and saw Wizards implemented it for Duels of the Planeswalkers. The article I read talked decisions tree. They talked about thinking about possible responses to each action. The main problem with the implementation was that they had to know how to use processors smartly. The solution was that they ruled out decisions that led to mostly bad scenarios for the AI or ones that made no sense like playing Giant Growth on an opponent’s creature. However, the developers did note that sometimes, those actions could have beneficial outcomes. The actions were self-segregated. However, the developers admitted that that there was no creativity or uniqueness to the AI. The AI couldn’t handle or create combos. I don’t know why that is so if they just have to check the decision tree for the most optimal result by scoring decisions and picking the one with the highest score. The AI can only think 3-6 levels deep.

Another blog (http://mtgrares.blogspot.com/2008/12/ai-overview.html) I read talked about how an AI the creator of the blog developed had code imbedded in the cards that would give guidelines to the AI on how to play the card. Example, Wrath of God is only played if there is a creature in play. Giant Growth is used on an attacking creature. However, the problem is that the selection of the cards is random. That means it isn’t the most efficient piece of code so it isn’t one that can beat humans. This is line with the Wikipedia article on the Xbox Live Magic video game, Apparently, since any card can override the game’s core rules, they had to program for special scenarios.

The blog (http://mtgrares.blogspot.com/2008/12/wizards-is-trying-to-kill-me.html) talked about how it troublesome to deal with new sets because they use weird mechanics. I can imagine landfall effect would cause problems for updating current AI. I imagine it would take incredible foresight to predict effects like cascading, landfall and quests. Implementing an AI that could handle these things without any modification before these concepts were introduced is something that is beyond the scope of the current AI.

I discovered certain things about my decision making and strategizing while playing Magic: The Gathering games and deck building. I didn’t just want cards that were effective. I wanted cards that had synergy in both effects and art. I wanted a deck with a very clear theme like birds or goblins, even if the theme didn’t create special effects like allies did. The cards I liked for their abilities were often the more useless ones that you couldn’t depend on like Hedron Crab, which has a random card effect that could be useful or useless depending on your luck. I wanted to win, but I wanted to win a fun way. I did not want a cold calculating sheer force way to victory (no offense to those who prefer this), I wanted to a strategy that would work 2/3 times or 3/5 times. I wanted a unique strategy that no one else uses or sees coming. I guess in the description of players I would be a Timmy, partly because I’m not good enough to be a Spike or Johnny. I would want to be a Johnny-Spike hybrid but I would need to increase my level of playing.

In fact, my favorite deck is one that isn’t my most effective, but rather one that follows a theme, Landfall. Ideally, when a land falls, multiple effects should occur. This was a deck I made during the booster draft of Zendikar, so it was obvious that I had a lot of Zendikar cards in supply within the draft. The Hedron Crab helped mess-up the tempo of my opponents when their bombs would just go to the graveyard. The deck depended on luck and would always have different results every time, as opposed to my deck that I used for the tournament which used a lot of creature removals from different blocks: Alara, Zendikar, and Magic X.

In comparison, people were better than me at deck building. The reasoning is that people used smarter methods. Example: Kotaro used permutation in order to design his five-color deck. People actually knew how to weigh the differences between cards, i.e. they knew which ones were better based on variables like mana cost, attack, toughness and mana abilities. I didn’t know much about possible alternatives. Once I found a card that did what I wanted, I stopped searching for cards to take its place. Needless to say, it was hard to part with my initial deck of birds, because I didn’t want to part with the theme.  However, sometimes you just have to throw it all away.

The meta-game affects how the deck was designed. I didn’t want to be green or black because everyone was black or green. I wanted originality so I decided to go either blue or multi-colored. However, I compromised and realized the power of the black cards in the pool. However, if I could have wanted to, I would have picked the color least represented in the tournament. The advantage of picking an unrepresented color is that no one would be prepared for it, and even if they sideboard for it, it’s a couple of cards.

Programming an AI that plays a flawed game like me solely because of personality would be very interesting. Instead of an AI that plays the game coldly and efficiently, it would very interesting because it’s an AI that has a personality. Like Wizards talked about, there’s Spike’s, Timmy’s and Johnny’s. Programming an AI to be a Spike would be boring, and it would be interesting if they were designed to be Timmy’s and Johnny’s. I remember Edgar talked in his presentation that he plays to annoy people instead of to win. Match-ups against AI like that would give more flavour to fighting against AI’s.

Week 9 podcast up

Thursday, December 3rd, 2009

Our last class session with final presentations was recorded and is available as a podcast.

I’ll withhold comment on anything until our final podcast to be recorded this weekend.