On the Application of Bayesian Analysis to Magic by Chris D

December 13th, 2009

(Here’s one of the more technical papers I got. Very, very interesting analysis of Magic AI. Of course, the people out there who actually do Magic AI have a better idea how true these things are, but I think there a bunch of good observations. -Kevin)

Recently, deterministic computer systems have been shown to be highly effective in the solution of various games of strategy previously thought exclusive to the provenance of human thought.  Chess, and other chess-like games, are a primary example of this.  The ability of computer systems to play strategy games such as chess has presently surpassed all human players.  Indeed, for some simpler games, such as checkers, computer programs have successfully “solved” the game – creating an algorithm that, along with a corresponding database of predetermined calculations, can provably determine the best move in any position in a relatively short amount of time.  On the other hand, many other strategy games have not been successfully played by computers.  This lack of success can be attributed to a variety of vicissitudes, depending on the characteristics of the game being attempted.

Chess is a particularly auspicious candidate for computerized solutions, being that it is: (1) open in the information domain, that is, all aspects of the game state are known to all players at all times; (2) highly tactical, that is, many if not most variations involve lines of play in which each player is forced to play from among a very small number of good-looking moves, and where all other moves can be clearly shown to lose, which decreases the branch factor of the game tree; (3) simple to define, that is, each piece moves according to basic geometric factors and legal moves tend to remain legal over long periods of time; (4) drawish, that is, games tend to produce draws and wins always involve capitalizing on the opponent’s errors.  These factors combined make chess a good candidate for computer play.

Magic the Gathering, on the other hand, is, for many reasons, poorly suited to be played by an artificial intelligence.  These include the facts that it is: (1) closed in the information domain, that is, portions of the game state, such as the content of the players’ hands, is known by only one player, and, additionally, the order of cards within the players’ decks, which, overall, represents most of the information content of the game state, is hidden from both players.  This will present problems to any computer trying to play a good game of Magic, although it can be mitigated somewhat by considering the fact that the impact of the information of card order within the deck on the outcome of the game is much lower than that of the information that is available to the players.  Additionally, Magic the Gathering is: (2) highly strategic, that is, players are seldom forced to do anything, and there are many points of time within each “turn” where players may act or react (but usually choose not to), further increasing the time complexity of the game tree; (3) difficult to define, that is, as there are thousands of Magic cards in print, many of which have eccentric and difficult to implement rules that alter or create new aspects to the game state, it is difficult to represent and effectively analyze the game state; (4) random in outcome, that is, games tend to be won or lost often based upon random chance, and in many cases strategy is less important than drawing the correct card.

Many of the ways in which Magic is difficult to implement on a computer can be resolved, if only partially, through an aggressive use of Bayesian analysis.  In particular, Bayesian analysis allows the program to make decisions based only on a partial knowledge of the game state, and to update its decision algorithms depending on new information that becomes available.  However, since the expected behavior of the Magic the Gathering, when considered as a system, is highly dependent on the behavior of the opponent, it is difficult to use Bayesian analysis to determine the correct play in a given situation.

A computer should be able to manage Magic data from multiple perspectives.  In general, we can consider the effects of a play as an Aggro, Combo, or Control action.  Also, we can attempt to quantify the loss/benefits of an action in terms of variables such as (1) life lost/gained, (2) damage dealt, (3) field advantage, (4) card advantage, (5) mana acceleration, (6) information gained/lost.  An example of a card which would give card advantage is Divination, which draws two cards at the cost of one.  An example of a card which causes information loss is Time Spiral, since it causes cards from the hand/graveyard to be shuffled back into the library.

When designing a deck, it is important to keep a balance between many different factors.  For example, in decks which include mana acceleration, it is critical to have exactly the right number and kinds of cards which provide mana acceleration.  Even in decks which do not focus on card advantage, it is often beneficial to include it.  For example, I included two Sign in Blood cards in my class tournament deck, in order to provide card advantage at critical times.  I also included two Gravediggers, which are also intended to provide card advantage.  In general, I found the addition of the additional element of card advantage to be invaluable in defeating certain kinds of Aggro decks within the environment, specifically those which would go full Aggro for the first few turns of the game and then run out of cards to play.  Against these sorts of decks, I can trade my creatures one for one (or in many cases one for two) and, by gaining card advantage from such cards, still have one or two extra cards later on to play when my opponent has run out of cards.  Similarly, any computer program that attempts to play magic must be aware of elements such as card advantage, field advantage, and mana acceleration, which, although possibly orthogonal to their main strategy, will provide the additional push needed to dominate a similarly situated opponent.

One major barrier to the performance of the Magic the Gathering engine is the lack of professional Magic games recorded in a computer-readable format.  In comparison, chess has hundreds of years of history over which the rules of the game have remained basically the same, and millions of recorded games played throughout that history.  The nature of chess also lends itself to being recorded and analyzed by computer programs.  On the other hand, Magic the Gathering has rules that change every few months, and its games have no real ability to be recorded, partially due to the limited information available to players.

Several elements of strategy which I found useful during the tournament could, under the right conditions, be adapted to play using a computer algorithm.  I found that it was generally best to get out a creature on turn one, and to use the most powerful creature available when one does so.  So, for example, I started off many games with my tournament deck by playing a Swamp and then casting a Vampire Lacerator, which is a 2/2 with a negative ability of life loss for its controller.  If I am going second, this is especially useful because it discourages attacks from 1/1 creatures my opponent may have played on his or her first turn.  If I am going first, then I can usually attack on turn 2 for 2 damage, and then play an appropriate 2-drop creature, such as a Rathi Trapper 1/2 or a Putrid Leech 2/2, both of which can block enemy one-drop attackers.  A computer would also need to know when to trade its creatures for its opponent’s creatures; for example, if I played a Vampire Lacerator on turn 1, and my opponent played a Goblin Guide 2/2 and swung with it, I would probably block and trade my Lacerator for his Goblin; on the other hand, if instead I was playing green and had out a Llanowar Elves 1/1, and my opponent played a Raging Goblin 1/1 Haste and swung, I would probably not block and the computer ought not to block either.  On the other hand, there may be special conditions during which these actions would not be correct.  For example, if I controlled a Lacerator and my opponent swung with a Goblin Guide, and I noticed that I have a Child of Night and two Feast of Bloods in my hand, then I might not block in order that I can play my Child of Night on turn two, and then control two vampires in order to satisfy the cast condition for Feast of Blood.  So this situation is really more complicated than simple rules can determine.  This is why Magic is such a complicated game and is hard for computers to play well.

Excerpt from Ben’s Final Paper

December 12th, 2009

I’m not exactly sure how I’m going to deal with these papers, but maybe some will be posted in full, some may just be parts, and some may get comments as well.

In any case, here’s an excerpt from a paper by Ben G., who wrote about his madness deck and the idea of information in Magic:

While studying epistemic logic, I found that the idea of controlling information was really interesting to me; what value do we place on information, and how do we control it with our actions? The general impression I got from the class is that information is valued relatively poorly, but is still valued. That is to say, the aspect of information shouldn’t change whether a player should perform an action, but it should change when or how an action is performed. If a player can play a creature, they should wait until after the combat phase so that they limit the information available to the opponent. Unless, of course, playing the creature earlier gives any advantage, in which case that value overrides that of the information revealed.

I think this is a really interesting point to make, about the when and how, not the whether. The way I see it, you use information primarily to let your opponent make mistakes. A classic example is “drawing the counter” when you slow-roll your hand or play cards in an atypical order to make your opponent waste counterspells on non-essential things.

Information is a favorite topic for Magic writers. I actually just saw one from Ben Stark on channelfireball about it that I actually haven’t read it. It’s a hard topic to address because I think the scope of Magic is too large to explain how information should affect your play-by-play. Instead, I think the general guidelines that writers give you are the best part because they make you think about playing Magic differently.

Week 10 Podcast Up

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

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

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.

Tournament Follow-up

November 18th, 2009

We ran the tournament last night that pretty much caps off the class. It was 4 rounds of swiss to form a top 8 that will play in about 2 weeks. All in all, it went pretty well.

Having never run a tournament before, I was somewhat worried that things would go to crap. Problems I foresaw included:

  • downtime between rounds. No one likes to stand around waiting for their next match
  • issues with time. Since I wanted to get 4 rounds roughly in the 2 hour timeslot for the class, I told them that there would be 30 minute rounds. I’m sure that it rushed some of the students, but whatever. I foolishly got lenient to get some games to end, but it was pointed out to me that that’s not exactly fair
  • bad pairings. I was doing it mostly manually with a spreadsheet and a program to shuffle the order of names, so I had to group people by points by hand and hope that there weren’t any repeat matchups. It only happened once in the last round, and a single switcheroo (not sure if that was fair) fixed it

Overall, I think it went smoothly. 4 rounds in about 2 hours 45 minutes, so no major hiccups. Tom and I were playing a lot of Magic during rounds (for perspective, we, knowing our decks, got in 5 games in about 20 minutes, which was how long it took some people to play 1 game), and we only got maybe 5 judge calls the entire tournament.

As far as the winners go, we had 1 person go 4-0, 3 go 3-1, 2 go 2-0-2, and 4 go 2-1-1. On tiebreakers, we got that sorted out for the top 8, with decklists posted here. A majority of the rest of the rest of the decklists are here. Some observations about how decks did:

  • Mono-black decks were strong. We had 3 in the top 8, and 3 just outside, either at 2-1-1 or 2-2. I believe Reuben actually got into the top 8 over a mono-black control deck using aladdin’s ring when his opponent brought in cop:black and plains as his anti-black hate
  • Mono-blue decks did not do well. Generally, decks running blue didn’t do well, which we could’ve expected given the lack of good strong control pieces. At the beginning of the quarter, the U fliers deck looked pretty good, but once the power level and aggro went up with Zendikar, horned turtle wasn’t able to hold back the tide so well
  • Red was not popular and therefore wasn’t well-represented. Leland has R as part of Boros Bushwhacker, but across the board, the only red I really saw was splashed for some burn in green decks.
  • Soldiers went down in popularity, but the two decks that were doing pure soldiers both ended up in the top 8. There are a lot of common elements (full armor/swordsmiths, vanguards, brave the elements), but the differences are more interesting. Yi has an equipment sub-theme going on in there, but Steve has slighly more staying power with the serra angel and team pump
  • Kotaro was the one who went 4-0 with his domain deck. Suprisingly consistent for 5 colors and not the best fixing around. It isn’t a “all the best stuff in the format” as much as it’s just playing off of domain. But who’s to complain for a 3/3 for 3 that can become a 5/5 in 2 turns?

I won’t go as far as to predict who’s going to win at this point to avoid biasing what happens here or showing favoritism, but I know that these are going to be good matchups. They have to keep the exact same decklists, sideboard and all, going into the top 8, so at this point, it’ll mostly be playtesting. Tom and I agreed that we would make similar decks to all of these so that people can practice. We are going into Thanksgiving break and then exams, so hopefully people don’t have TOO much time to be playtesting, but it would be good.

Week 8 podcast up

November 11th, 2009

Our lecture on Epistemic Logic got posted earlier today, and you can find it here, and slides here.

And with that, we’re pretty much done. That’s the last prepared lecture that we have. Next week is our tournament, the week after is Thanksgiving break, and the week after is the final week of classes with presentations.

It’s pretty amazing how quickly the quarter has gone. Well, some classes have gone by really slowly, but it seems like just yesterday that people were figuring out how to play the game, and I was anxious to start talking about something real. Of course, we’re not done yet, so we’re not into reflection on the class yet.

Tom and I are up in the air on whether we’ll be doing a podcast for this coming week. We really don’t have anything to talk about, but if you know of something you want us to talk about, we’re open to suggestions.

Student Decklists posted

November 9th, 2009

As a preview to some content on the next podcast, I posted decklists that have been submitted to us from students here. Feel free to take a look, and if you have any feedback, I’m sure the students will be very appreciative. Either leave a comment or email Tom or me and we’ll pass it along.

If you’re thinking of other cards that they should be playing with, generally, we’re pretty full on Lorwyn forward thanks to Dave’s donation. That is, there are really no rares, and uncommons (especially good ones) are very sparse, but commons should be generally available, and other things might be gained with trades.

Week 7 Podcast up

November 4th, 2009

I guess I’ll link.

And show notes

Sorry, the gain at the very beginning is way too high, but I correct it a couple seconds in.

Syllabus Description: This week, George Michelogiannakis, a level 3 DCI judge, will talk about professional Magic. So far, we’ve focused primarily on casual Magic, but there are many tiers of tournaments organized by the DCI and staffed by judges. George will give you a glimpse of this part of Magic culture.

Because it’s a guest lecture, this is actually recorded in class, so there’s a lot more noise and people on this podcast.

Slides are at: http://magic.kevinleung.com/slides/DCI.ppt

What I’m Playing With

November 3rd, 2009

Updates here have been slow, sorry. Of course, there’s always the podcast that I guess I could be putting links up for each week. We actually don’t have a fresh one this week because we have a guest lecturer coming in.

In the meantime, I thought I’d showcase the deck that I’m playing with. We’re limited to whatever is in the card pool, and although this is technically a constructed format, I find that the shortage of good, valuable cards means that matches play more like limited games. I’ve been watching LSV’s videos of his drafts and taking that as inspiration for decks. At the beginning of the quarter,  I was playing an all M10 blue skies deck that was half-decent. Recently, with Zendikar coming in, I put together a new deck looking like this:

Lands (24)
14 Plains
10 Island

Creatures (24)
4 Kor Skyfisher
2 Welkin Tern

4 Ondu Cleric
4 Makindi Shieldmate
4 Stonework Puma
4 Umara Raptor

2 Kor Sanctifiers

Other Spells (12)
4 Journey to Nowhere
2 Narrow Escape
4 Into the Roil
2 Adventuring Gear

It’s not bad. It’s not great, but on the plus side, it’s all Zendikar commons, so if you’re playing block pauper?…

If you’re familiar with Zendikar, there are no surprises. There’s a allies thing going on to 1) stall the game and 2) pump up umara raptor. The raptor is pretty much the only win condition that the deck has. The welkin tern and kor skyfisher can do it as well, but most people don’t really feel the pressure from that. The shieldmate and cleric are great stall. A 3/6 is hard to swing through, and you can get a good 15 life off of a single cleric. Life gain isn’t insane, but it’s pretty good when you’re trying to race a deck with fatter ground beats and you only have a 2/3 flier to beat down.

I just read an article about how allies is a pretty linear mechanic, and that’s true. The thing that I like about this deck is that even though the theme would seem to be simple in just playing out lots of allies, the bounce actually provides some really interesting options, mainly being bouncing allies in a crunch and replaying them for the bonus. There are 10 bounce spells in the deck, and they even have cool interaction with journey to nowhere (bouncing it while the enters play ability is on the stack to permanently remove something from the game).

I considered trying to make it better by throwing in some cheap-ish changeling creatures like avian changeling or mothdust changeling. The former is pretty much better than the stonework puma, and the latter has built in reinforce for my raptors and shieldmates. I think there’s something charming about zendikar block pauper, though, so I’ll probably stay with this build.