Math of Magic

Because math isn't always boring

Month: August, 2012

Probability, part 3

So, now we’ve defined all these wonderfully confusing terms. How do they help?

Potentially quite a bit, but let’s start by getting some cold, hard numbers. We’ll start with our original 35/25 deck, and figure out a few expectancies. We’ll start with the expected turn by which we’ll have drawn 4 lands.

The probability that we’ll have drawn exactly four lands on turn one, i.e. after having drawn seven cards, is, as we saw last week,

L[4](1) = (C(m,k)*C(N-m,n-k))/C(N,n)=(C(25,4)*C(35,3)/C(60,7)≈0.214

So the first term of the sum is 1*0.214. For the second term, we draw one more card, and therefore one more spell, for a probability of

L[4](2) = (C(m,k)*C(N-m,n-k))/C(N,n)=(C(25,4)*C(35,4)/C(60,8)≈0.258

and a term of 2*0.258 = 0.516. Adding these two terms together gets us 0.214+0.516=0.730. We go on creating these terms, with the probabilities of

L[4](n) = (C(25,4)*C(35,n+2)/C(60,n+6)

Which we can multiply by n and then add all up together. We do this for all values of n… okay, no, not really. Once we’ve drawn our 39th card, even if we started out by drawing all 35 non-lands, the next four cards will have to be lands, so any further draws will put us over the exact number of lands we are looking for, namely four. That means we can stop adding up terms after n=33, which happens to coincide with the last number for which C(35,n+2) is defined. Using our handy-dandy calculator (WolframAlpha is your friend!), we arrive at an expectancy of

E(L[4]) = Σ n * (C(25,4)*C(35,n+2)/C(60,n+6) ≈ 10.647.

In other words, we expect to have drawn exactly 4 lands on average between turns 10 and 11. If that number seems high, well, it is, and there’s a few reasons for that, the biggest being that we only have used positive numbers for n. If we accept negative values of n (in other words, we take into account the cards drawn before the start of the game), we arrive at the value 3.894 – a much more reasonable (and realistic) value. So why use the first value at all?

Well, firstly it’s just a mathematical construct that will help us in making mulligan decisions, not an actual representation of  what turn we’ll draw four lands by, and secondly shut up! I goofed, all mathematicians are entitled to a false start or two!

Ahem, anyway, there actually is a good reason for using the first expectancy, and that is because the expectancy I calculated actually doesn’t assume we know anything about our opening hand. What we need to do is look at how the expectancy changes based on the contents of our opening hand. To do this, we have to use something called the conditional expectation.

Let’s say the opening hand has three lands in it already. So what is the probability then that we draw our fourth land in the second turn? Well, the library still contains 22 lands and 31 spells, so the probability is a straight 22/53 ≈ 0.423. The probability that we have four lands in the next turn is the probability that you draw first a land and then a spell plus the probability you draw a spell and then a land, or

22/53*31/52+31/53*22/52=2*(22*31)/(53*52) ≈ 0.495

And if this is starting to look familiar to you, then good, you might just be a mathematician after all. You see, once we take out the three lands and four spells out of the library, all we’re basically doing now is drawing balls out of an urn again, just this time it’s an urn that has 22 white and 31 black balls in it. Once again, we can calculate an expectancy of

E(L'[4])= Σ n * (C(22,1)*C(31,n-1)/C(53,n) ≈ 8.413.

Again, remember, this is just a mathematical construct, it doesn’t mean you have to wait 8 turns to draw another land. But what IS interesting is when you compare that to the expectancy if you start with 2 lands and 5 spells.

E(L''[4])= Σ n * (C(23,2)*C(30,n-1)/C(53,n) ≈ 84.15

Which is, in case you didn’t notice, a considerably larger number. In other words, if you have an opening hand with two lands in it, on average you’ll have to wait quite a bit longer to draw up to four lands than you will if you start with three lands.

Shocking, I know! But we’ll get into how this can actually be of decision-making help to us next week.

Exercises

  1. What is the expectancy, without looking at your opening hand, of drawing 3 lands? Of five?
  2. What are the expectancies of drawing four lands for the other numbers of lands in your opening hand?
Advertisements

Probability, part 2

Okay, so all this theory is fun, but how can it make you a better Magic player? Sure, the last post helps with deckbuilding – a little – but most of those numbers have been really well explored by now, and vary more based on other factors than math.

So let’s try and tackle something a little more concrete: The decision on when, and when not, to mulligan.

I suspect this topic might span more than one post, so bear with me.

Whenever you’re tackling a problem like this, it’s good to define your terms. We all know what a mulligan is, it’s discarding your starting hand based on the information you gain from looking at it in the hopes of a better one. What does “better than ” mean? Well, it can mean any number of things, depending on your deck. It could mean you’re likely to draw your combo pieces, or maybe you want to maximize copies of a certain card. But in general, I think that a successful opening hand means that, by the time the game gets underway, you’ll both draw enough lands to cast your spells, and enough actual spells to cast. Again, for each deck this is going to be different; fast decks are going to want more spells, more control-ish or combo decks might need more consistent land drops.

I’m going to introduce a bit of a new concept here, namely the random variable. Which doesn’t mean that you pick a letter at random instead of x, it’s actually a very specific kind of function that has to do with assigning a certain event to a number. For example, the number of lands in your opening hand is a random variable, call it X. You can represent the probability of certain numbers of lands in your opening hand by P(X=3), for example.

A good metric to measure the quality of an opening hand is how long it takes to be reasonably sure of drawing a certain number of lands, and the same for spells. For a baseline, let’s look at a deck with 35 spells and 25 lands. We’ll define our random variable L[n] as the number of turns it takes to draw n lands and, along the same lines, S[n] as the number of turns it takes to draw n non-land spells. Remember that random variables are a number that are associated with a certain probability, in the sense that we are interested in things like what P(L[5]=3)  is.

Actually, let’s go ahead and calculate that. Using our formula from last week, we have

P(5)=(C(m,k)*C(N-m,n-k))/C(N,n)=(C(25,5)*C(35,5)/C(60,10)≈0,229,

assuming we’re playing first which, for the sake of argument, I’ll be assuming here throughout this series of articles. As a reminder, C(a,b) is the binomial coefficient, sometimes also called “a choose b”.

What is interesting for us to help us decide when to mulligan is the average number of turns we’ll need to draw a given number of lands – we’ll say, for the sake of argument, 4, since most decks want to make their first four land drops pretty consistently. When talking about random variables, this “average” is called the expectancy.

When you calculate the average of a set of numbers, for example, you add up the numbers, and then divide by n, the number of numbers in the set. The expectancy is very similar, if you look at the numbers in the set earlier all to have the same probability of occurring, namely 1/n.

When we calculate the expectancy, we again add up all the numbers that can occur in the random variable, but we multiply each one first by the probability it has of occurring. So, in our example above, we take the number of turns “3”, and multiply it by the probability that by turn 3 we have drawn exactly 3 lands, which is 22,9% (-ish). we do this for all conceivable numbers, which would be infinitely many, but luckily we can pretty much stop counting after 60, since by that point you’d have drawn all of your deck anyway. The formula for this is written:

E(L[n]) = Σ (P(L[n]=X) * X)

and the result is simply a number, in our case one that lies somewhere between 0 and 60. As a reminder, Σ is used to denote a summation, in other words we add up all the terms that appear after it. I left off the range because it should be clear that we’re adding over all integers, although in our case we can stop after 53. Of course, actually calculating this can be a bit of a pain, but there are a few shortcuts.

I’ll delve into those, and how we can use the expectancy to help our Mulliganing decisions, next week.

Exercises:

  1. Given a deck with a 35/25 land ratio, what is the probability that, on turn four, you will have drawn exactly four lands? What about at least four lands?
  2. How are the random variables L[n] and S[m] connected? Can you make a formula to calculate one based on the other?
  3. What is the expetency for the random variable of “number of lands drawn in your opening hand” for a deck with a 35/25 land ratio?

Probability

Earlier, we talked about randomness. For the time being, we’re going to assume that the deck is going to be truly randomized and see how we can use probability theory to help us better our game. I touched on this earlier, but I intend to get a little bit more in depth here now, and talk about something concrete, namely mulliganning.

When should you mulligan? Well, obviously if you have no lands in your opening hand, you should probably mulligan. Likewise, if you have only spells, that is also not great. If you only have spells that are too expensive to play before your opponent runs you over, that would be bad too, but harder to quantify. For now, let’s just focus on the ratio of spells to lands, and worry about mana costs and colors later.
Optimally your first few turns you should make a land drop. For the sake of argument, we’ll say that your first three turns you absolutely want to make your land drop, so by turn three you want to make sure that the probability of drawing three lands is as high as possible. To do this, we build a deck of sixty lands – kidding! We want to have spells to cast as well. So, by turn three, if you’re on the play, you’ll have drawn (disregarding any shenanigans) nine cards.Of those nine cards, you’ll want at least three spells and three lands. The other three can be either spells or lands, both are about equally good at this point. So what is the probability of this happening?

Let’s say the deck consists of L lands and S non-land spells. L+S=60, because we’re not playing Commander (or with Battle of Wits). The chance that, out of 9 cards, you will draw 3 lands, is something that we call an Urn Problem, because it is analogous to drawing a certain number of colored balls out of an urn. In this particular case, we are drawing balls without replacing them, which gives us a distribution known as the hypergeometric distribution. The probability of drawing k(=3) lands out of n(=9) cards from a deck consisting of N(=60) cards, m(=L) lands, is equal to

P(L)=(C(m,k)*C(N-m,n-k))/C(N,n)
=(C(L,3)*C(60-L,9-3))/C(60,9)

where C(n,k) is the polynomial coefficient of n over k, also spoken as “n choose k”. The probability for drawing 3 spells in 9 cards is the same, but substituting S for L.
So, now we have to find out the probability that we draw 3 spells, right? Well yes… And no. You see, when we figure out how likely it is that we draw 3 lands out of 9 cards, we are simultaneously drawing 6 spells. What we actually have to do is figure out how likely it is to draw 6 lands and therefore three spells. And also 4 lands and 5 spells, and 5 lands and 4 spells. We already have the tools to do so, we just have to plug in the numbers and add them together.
What we are left with is…. A very long equation that we can solve for L (though it wouldn’t be easy), but we have e advantage of experience on our sides. Since the average Magic deck will have between 19 and 26 lands, we can just plug in the numbers and see which one gives us the highest probability… But I leave that as an exercise for the reader. 😉

Exercises:

1. Plug in the numbers and find out what the optimum number of lands is in this situation.
2. How does the situation change if you are on the daw? What is the optimal number of lands then?

Strictly Better (or not)

Often when comparing two cards people will use the term “strictly better,” as in, “Lightning Bolt is strictly better than Shock.” To understand what players mean by this, we need to make a brief excursion into the field of mathematics known as “Game theory”

Game theory is a field of mathematics that deals with strategic decision making, something that Magic players do all the time. In game theory, a lot of the discussion revolves around so-called “dominating strategies.” A strategy is said to “dominate” another strategy, if said strategy will always lead to a better outcome.

The concept of “strictly better” stems from this idea. A card is said to be “strictly better” than another card if in every possible circumstance having that card will lead to a better outcome than having the second card. In the example above, Lightning Bolt could be considered “strictly better” than Shock because they have the same mana cost and speed, but while Lightning Bolt deals 3 damage to a creature or player, Shock only deals 2.

In almost every situation, you will prefer to deal three damage, even if two would be enough to kill the creature in question, if you’re paying the exact same amount of mana either way.

But here is where Magic is tricky. With over 12,000 unique cards, and a near (but not actually) infinite variety of play situations, saying that having a given card will always be better than another is almost always doomed to failure.

Say, for example, you have a Chandra, the Firebrand with six loyalty counters on it, so that you can activate her ultimate ability to deal six damage to your opponent, and you know your opponent, who is at 8 life, has a Faith’s Shield in hand. If you have a Lightning Bolt in your hand, casting it will bring your opponent down to 5 life, which will then allow him to casts Faith’s Shield and use the Fateful Hour ability, preventing you from being able to kill him or her with Chandra this turn. If you have Shock instead, casting it will bring your opponent to six life, meaning you can activate Chandra’s ultimate to finish him or her off.

Or your opponent uses Mindslaver and casts it on yourself. Pretty much any card’s “strictly better”-ness can be disproved with Mindslaver, honestly. Which is why, in Magic, the term has grown to near-uselessness. Instead, a different definition has to be used, one that focuses on the attributes of the card itself, rather than the theoretical background of the phrase.

A card can instead be said to be “strictly better” than another, if each attribute of the card – speed, (mana) cost, power, toughness, abilities, etc. – is better than the other. 

A list of examples can be found here.

As I said, this isn’t strictly better in a mathematical sense, but it is in a way that is more useful for Magic players.

Exercises:

  1. Find more examples of cards that are “strictly better” in the Magic sense.
  2. Find situations where the examples you discovered, and the ones mentioned on the wiki, actually turn out to be worse than the alternative. For purposes of this exercise, ignore effects like Mindslaver and Sorin Markov’s ultimate ability.

Infinity

There is no such thing as infinity in Magic.

I know, this seems a bit unfair, since infinity is such a cool concept, but sadly the rules specifically state, anytime an infinite number of things happen, you just choose a number for how many times they happen, and then it ends. Unless you can’t, then you break the game as badly as if you had just divided by zero. This also is in the rules, and is usually referenced by the old resolving-a-O-ring-with-only-two-other-O-rings-on-the-board example.

What this means is, assuming you and your opponent both have a way of producing infinite mana, he or she will never be able to cast a Fireball big enough that you can’t save yourself with an Alabaster Potion.

But what if we got rid of the rules on infinities? What if you really could produce an infinite amount of mana, not merely an arbitrarily large amount?

Well, first of all we have to make sure we actually can make an infinite amount of mana. Most “infinite mana combos” involve taking a finite number of steps that end up where you started from but with some number of extra mana in your mana pool. If you wanted infinite mana, you’d have to perform these steps an infinite amount of times, which isn’t actually possible. Luckily, the magic rules state that if you can demonstrate a loop like this, it’s enough to point out the sequence and, assuming your opponent can’t or doesn’t want to do anything to interrupt it, name a number of times you want to perform it. So let’s make things easy on us and just say that we modify that rule to allow for that number to be “infinite”.

So, back to where we were. Say we have an infinite amount of mana, and our opponent casts an infinitely large Fireball. Can we save ourselves with an Alabaster Potion?

Well, this is where things get tricky. Infinity is strange in that regular math doesn’t actually work on it. You might think, sure, if you can prevent an infinite amount of damage, then you’re safe, but it doesn’t actually work like that.

Take the set of integers (0,1,2,…), for example. There are an infinite amount of numbers. Now subtract all the even numbers from that set, and you’re left with 1,3,5,…., which is still an infinite amount of numbers. Infinity minus infinity is not defined. So that’s our first problem, and it exemplifies one of the main reasons Magic doesn’t allow for infinities.

But let’s say that we redefine “infinity” in a way that we actually can resolve such a situation. Say that we state that, whenever we create an infinite amount of something, we have to define a set of infinite integers and use that to mark that particular infinity. so, in the example above, the Fireball player defines his or her infinity as the set of integers. Then all the Alabaster Potion player needs to do is define the same set for his or her infinity, and they’l live.

Let’s take another example. Say we still have infinite mana, and a way to recur Gelatinous Genesis. We cast it once for X=1, creating 1 1/1 Ooze. Then we cast it for 2, then for three, and so on, an infinite number of times (again, modifying the rules so that we can do this without actually taking an infinite amount of time). Your opponent has a Deepfire Elemental. Can your opponent kill all your oozes?

Well, the answer to this is… maybe. The problem is, for each value of X you have to choose between one of X creatures to target, which doesn’t sound that bad, until you realize that you, as a person, have to choose which one of those creatures to target. An infinite number of times. And there’s no way to shortcut that, at least not in the Magic rules. Luckily, math comes to the rescue here… sort of.

There is a principle called the Axiom of Choice, which basically says that if you have to make an infinite number of decisions for something, like choosing an ooze, you can. The funny thing is, math doesn’t need the Axiom of Choice. (Most) math works just fine without it, though some proofs get much trickier, which is why a lot of times in some fields of mathematics, you’ll see the phrase “Assuming AC,…” simply because without that phrase the proof just plain doesn’t work, though that doesn’t actually mean that the result isn’t any less true without the AC.

So, let’s add the Axiom of Choice to the comprehensive rules. Now you can kill all the oozes, but will that save you? Maybe, maybe not, because the Ooze player can just cast it again, and you can kill them, and they can cast them, and you can kill them, and so on, ad infinitum. There’s no easy way to resolve this situation, it doesn’t fit the unbreakable-loop rule, so the game goes on forever or until one player gets tired and falls asleep. Then the other player gets the last word in, and wins the little face-off. 

…and that’s why we don’t allow “infinities” in Magic.

I’ll have more to say on the subject for sure, but I hope you enjoyed this little excursion.

Exercises:

  1. Say instead of Deepfire Elemental above, you have a way to recur Pernicious Deed. Your opponent has cast his or her infinite number of Oozes and passed the turn to you. Can you kill them all? Do you need AC to do so?
  2. What other situations can you think of where infinity breaks the game?