Archive for August, 2009

Symbolic AI and Knowledge Representation

Monday, 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 mlb.com 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

attack(“RagingGoblin”,”1″)

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

after(“end”,”combat”)

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.

Posted in AI | 1 Comment »

Some thoughts back and forth

Tuesday, 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 http://www.wizards.com/Magic/Magazine/Article.aspx?x=mtgcom/daily/fk41), 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 www.channelfireball.com
    • 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.

    Posted in Random | No Comments »

    Who Says Red’s No Good in M10?

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

    Posted in Random | No Comments »

    Standard Metagame and Iterative Deletion

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

    Posted in Game Theory, Metagame | No Comments »

    What’s a Good Metric for Magic?

    Tuesday, August 4th, 2009

    This has come up a couple times now, and I think it deserves its own post: what’s a good one-shot metric for Magic? As in, what’s the best way to boil down a situation into a single number?

    The motivation for this is that pretty much all Game Theory problems depend on comparing the payoffs for you and other agents. You want to maximize this payoff in these games, so a question about “What should I do?” can simply be comparing a single payoff for that set of strategies.

    What’s tricky is how to get Magic to fit into this scheme. First, Magic is a long series of choices, not just a single situation. Thus, when you transition from one turn to the next, it’s not like there’s some result and clear answer about whether you’re better or worse off. The game keeps going.

    Typically, these situations are usually dealt with in Magic puzzles by making the challenge to win the game by the net turn. For example I’ve seen quite a few of those puzzles where they set up the cards and say, “How can you win next turn?” (with the implication that you’re a failure if you can’t win). The unfortunate part about this is that this only gives us a binary payoff of either win lose. And a lot of situations depend on more nuanced comparisons between the values.

    So some of the metrics I’ve considered or had mentioned to me include:

    • life totals. This is what I used in the first You Make the Play. The problem with this in my mind, is that it doesn’t come close to representing anything about the game. I’m comfortable being at 10 life when I just played a Wrath. Not so much when my opponent just sneak attacked a Progenitus. More generally, I’m really wary about using any in-game metric, whether that’s life totals, total mana, total permanents, accumulated beats/card advantage. They’re all meaningful, but none of them can entirely capture a situation
    • turns to live. Also an interesting one. I think this one is better in that you assumingly abstract away most of the game to come up with this number. The problem I see with it, though, is that one must immediately ask, “Well, what does that mean to this deck or that deck?” Again, 4 turns to live means a lot more to a heartbeat deck than a turbo-fog deck. Granted, most of these situations are within a single deck, but it doesn’t give consistency between you and your opponent
    • an evaluation function. This is what I talked about in minimax. I thinkt his is fair because people can agree that it could somehow exist, and it abstracts away the game. It does better than turns to live because we can also assume that it is normalized for all decks so that a 5 means that a player playing heartbeat would be just about as confident as another player playing zoo who also got a 5. This, however, is obviously very difficult, and I have no idea what such an evaluation function would look like. Heck, if you could figure it out, you could probably “solve” Magic. That, however, is not how things are, though we can imagine that we would come up with something else
    • percentage to win. I feel like this is actually very similar to the evaluation function, except that 66% chance of winning means a lot more than 24. Both abstract the game away entirely and turn it into a number that somehow translates into your ability to win. This seems to be what I’ve drifted to, but Reyemile brings up the very valid point that it might not be fair to abstract away the game like this. From a theoretical perspective, this is vastly easier to work with, but given that the purpose of the course is to reevaluate these theoretical games into the much more concrete situation of Magic, I don’t think it’s fair for me to call it a day with this one.

    Opinions? Any other methods you feel like would work, or pros/cons of what I’ve mentioned above that I didn’t put down?

    Posted in Logistics | No Comments »

    You Make the Play: bolt edition take 2

    Sunday, August 2nd, 2009

    Hopefully everyone’s gotten a chance to look at the setup for the problem here. I got 2 great comments, so it looks like I have something to talk from.

    So there are a couple different options here. Being Magic, there are a lot more option here than what I’m presenting, but we’ll narrow the focus down to what actually seems to matter. Your main choices are:

    1. Swing with Knight of Meadowgrain, leave mana open for harm’s way
    2. Play Honor of the Pure, swing with Knight of Meadowgrain
    3. Don’t swing, maybe do something post-combat

    There are a few more combinations throwing in the Figure of Destiny somewhere (I should probably switch out the figure for a 2 mana creature so that + harm’s way isn’t an option, but no worries), but as far as the outcomes I listed, that really shouldn’t affect it.

    On this turn, only 1 red mana open and an unknown card means your opponent is representing Lightning Bolt. We can throw this together into a table to see what we get (too lazy to do the HTML on it, sorry)

    Bolt payoffs

    The numbers inside are our payoffs, normalized so I don’t have to use decimals. See the original post for how those numbers correspond to the payoffs, and see Salivanth’s comment for more explanation on all of those (the only one I disagree with is the swing, no bolt situation. He might play maelstrom pulse, not Jund Charm, so you that’d be a 50%er as well)

    What do we have here? Well, we learned about dominant strategies in the last “You Make the Play“, so we can try to apply that first. Remember, a strategies dominates another if it results in a better outcome regardless of what your opponent does (here’s a little more: a strictly dominant strategy always does better; a weakly dominant strategy does at least as well in all situations). Looking at the chart, we can see that not swinging is a dominated strategy. Swinging only results in payoffs of 3 regardless of bolt, and doing nothing has 2s regardless of bolt, so you’re always better off swinging. If you want to take a look at Salivanth’s comment again, he shows that HotP is strictly dominated by no HotP, which I agree with up to the point about what happens in scenario 2.

    Now if we only had dominant strategies, this would be where the story ends. If your opponent does have a bolt, we shouldn’t play HotP, but if they don’t, we should play HotP. In the end, this should be pretty obvious, but is a lead-in into how we determine what we do.

    Reyemile made the excellent point that whatever we do is “pure guesswork” for the reasons listed. Simply, I haven’t told you anything else about how the game has been going so far. How many bolts has your opponent played? How many cards left in the library? Were there any other times where they clearly should’ve played it if they had it? The most important point here is that the best action is determined by what you think your opponent has in your hand.

    Again, not surprising, but remember what happened in the Prisoner’s Dilemma. Sure, it matters what your opponent does in figuring out your payoffs, but it doesn’t affect what you should do; you should accuse the other person (or in our Magic case, sit). Here, what you’re trying to do is figure out what your best response (that’s official terminology) is to your opponent’s action.

    And this should be intuitive as well. Depending on how confident you are about what your opponent is going to do. Basically, we can multiple the probability that your opponent has a bolt by the payoffs for each action you choose. Thus, we get equations about the expected payoffs for various actions at various confidences. Here’s a graph about what that looks like. The x axis is your judged probability that they have a bolt. y axis is payoff. Blue line is swinging only, orange line is HotP, and teal line is doing nothing.

    Graph of Best Response

    (Major props to Apple, by the way, for having the Grapher application. That was really easy)

    So what you see there isn’t surprising. Doing nothing never yields the best reward, and HotP is only better when they don’t have a bolt. In more Game Theory terms, nothing is strictly dominated by swinging and weakly dominated by HotP. Swinging only is better when you think there’s a greater than 50% chance that your opponent has a bolt. This, of course, is on the graph because you can look for the intersection between the two curves and determine the ranges in which one is greater than the other. The result is a little trivial in this case because it happens at 50%, but when I get this into a real slide, I’ll pick more creative payoffs so that the intersection is at 57% or something.

    So that’s about it with best response. As foreshadowing, best response is the basis for one of the more famous results in Game Theory named after a dude with a movie now, so maybe we’ll hit that if I can come up with a half decent example. And I’ll put responses to the comments from last time more fully in another comment there. Of course, feel free to comment again on this one. I feel like I’m almost hitting the point of BSing here to try to work this in, so if you’re disgusted by this, please don’t just run away. Let me know; criticism is great feedback.

    Tags:
    Posted in Game Theory | No Comments »

    You Make the Play: bolt edition

    Saturday, August 1st, 2009

    Alright, I’m going to try to set up another situation for you to judge and lead into another topic. Being a work in progress, let me know if the problem is poorly presented or doesn’t really apply because I’m going to need to use these eventually.

    You’re playing something like Florian Michelac’s build of white weenies, and your opponent is playing something like Pierre Simoni’s Jund Cascade deck (both can be found here). Scenario:

    Your opponent: 2 cards in hand (1 is definitely Jund Charm, unsure of the other), 1 red mana open (and all colors available to play jund charm next turn), no creatures in play

    You: Knight of Meadowgrain in play, 2 white mana open, and Honor of the Pure, Harm’s Way, and Figure of Destiny in hand. Here’s what you know:

    • If you swing with Knight of Meadowgrain alone and it gets through, you have a 1/2 chance of winning
    • If you swing with Knight pumped by Honor of the Pure and it gets through, you have a 2/3 chance of winning
    • If you can’t hit your opponent this turn, you have a 1/3 chance of winning

    It’s your precombat main phase. What do you do, and more importantly, why?

    Posted in Game Theory | 5 Comments »

    We’re official!

    Saturday, August 1st, 2009

    They just posted courses for enrolling this fall, and we’ve got our official listing. Whoop whoop! (real post hopefully coming later this weekend)

    Course Listing

    Course Description

    I’m sad that neither my nor Tom’s name appears anywhere on it, but I’m happy to concede that point to get the class done.

    Posted in Random | No Comments »