"The Theory and Design of Magic: The Gathering" Class Page

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.

This entry was posted on Monday, August 31st, 2009 at 6:43 pm and is filed under AI. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.