Math of Magic

Because math isn't always boring

Randomness, Part 2

Hello again

Before I begin, let me clarify something from last week, regarding how you multiply two permutations.

A permutation like (14235) means that 1 gets mapped to 4, 4 gets mapped to  2, etc. If you perform the same permutation twice, then in the first step 1 will get mapped to 4, and 4 will get mapped to 2, so the resulting permutation will map 1 to 2, so we start by writing “(12”. Next, we’ll see w hat  2 gets mapped to. 2 in the first permutation gets mapped to 3, and 3 gets mapped to 5, so we continue the permutation “(125”. Then we see what 5 gets mapped to, etc. I hope that makes things a bit more clear. If ever a number gets “left out”, we start another set of parentheses for that number and see what it gets mapped to. If it gets mapped to itself, we just leave it out.

Now, on to more randomness. Last time I said that the chances of drawing a card in your opening hand that you are playing four of is 4/60+4/60+..+4/60 = 7/15. But that’s not entirely true, because we’re assuming that each of the card draws has the same probability of drawing that card. But what happens if your first four draws are that card? Then suddenly the probability that the fifth card is that card drops to zero, so clearly something can’t be quite right.

The reason for this is that the probabilities for drawing a given card in each of the first seven draws are not independent, so we need to think about how we can come up with the actual number. There is a tool that we use quite often in probability theory, namely the fact that sometimes it’s easier to look at the probability that something doesn’t happen than it is too look at how likely something  is to happen.

Let’s look at how likely it is that, given seven card draws, how likely is it that we will  not draw at least one of the card we are looking for. The first card we draw has a 56/60 chance of not being that card. Now, if we draw one of the cards with the first draw, we already know that the “event” we are looking at doesn’t match the criteria, so we can assume the first card draw is not the card we want. Which means that there are 59 cards left, 55 of which are not the card. So we now multiply the probability that the first card we draw isn’t the card with the probability that the second card isn’t it, so we have

P’=56/60*55/59*…

We go on like this for the first seven cards, ending up with

P’=56/60*55/59*54/58*53/57*52/56*51/55*50/54 ≈ 0.6 =60%

To come up with the probability we do draw it, we subtract from one (or 100%) the probability that we won’t draw it, so

P=1-P’ ≈ 0.4 = 40%

So, in your first hand you have about a 40%, or two in five, chance of drawing any given one of your four-ofs.

Looking at the complementary event can come in very handy when dealing with a complex situation. If we wanted to look at the probability of drawing at least one copy, we’d have to add the probability of drawing one copy, plus the probability of drawing two copies, and so on.

 

That will do it for today. I forgot to add exercises last week, so I’ll make sure to add some this time.

Next week we will talk some more about shuffling. Noticing a pattern yet?

Exercises:

1. What is the probability of drawing all four copies of a card in your first hand?

2How does the probability change if you are on the draw.

3Some card games have a minimum deck size of forty, but only allow three copies of a card. Are you more or less likely to draw a three-of in your opening hand if you follow those construction rules?

Shuffling, Part 2

Hello, hope you all had a good fourth!

Today we’re going to talk a bit more about shuffling, including bringing up the dreaded A-word: Algebra!

But don’t worry, we won’t be solving for x here, this is a more general use of the term, but I’ll get to that in a bit.

Okay, so we’ve determined that pile shuffling isn’t  really shuffling but just a clever way to waste time, now lets look at what exactly is going on.

One thing we mathematicians like to do is provide notation that can be universally used. For instance, if we look at shuffling we’ll want to give a good way of describing what changes between the original state of the cards and the state after shuffling. I’ll illustrate this based on the example of pile shuffling.

Say you have a deck of sixteen cards arranged in such a way that you have one card of each converted mana cost from one to sixteen. You arrange them neatly in order with the Llanowar Elves on the top (or Ancestral Recall or what have you) and perform an 8-pile pile shuffle.  Your deck starts out like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

And ends like this:

9 1 10 2 11 3 12 4 13 5 14 6 15 7 16 8

What happens if we repeat this shuffle? The result is

13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4

The interesting thing is, if you look very carefully, you’ll see an interesting pattern emerge. Let’s follow a certain card, say the card with the CMC of 5. in the first shuffle, the card with the 5 will get rearranged to be in the position 11, or

5->11

In the next shuffle, the card in position 11, which used to hold your Darksteel Colossus (or what have you) and got mapped to position 14, follows the same path your Tattered Drake does in the second shuffle, so in other words

11->14

So we have, over the course of two shuffles

5->11->14

If we imagine both these actions as one shuffle action, a combined pile shuffle so to speak, we can cut out the middle step, and write it as

5->14

If we write down these maps for all the cards, we will end up with the exact order we wrote above, which we will write as

1 2 3 4   5   6 7  8   9 10 11 12 13 14 15 16
13 9 5 1 14 10 6 2 15 11   7   3 16 12    8   4

We call this a permutation. A permutation is any function, or map, that changes the order of a set but not its contents. We will usually write permutations in the manner I did above, in two rows, with the number being mapped from above, and the number being mapped to below. But there is another, simpler way.

Let’s start with one pile shuffle. As a reminder, the map looks like this:

1 2   3 4   5  6  7  8   9 10 11 12 13 14 15 16
9 1 10 2 11 3 12 4 13    5 14   6 15   7 16   8

Take the card in the position 1. it gets mapped to the slot 9:

1->9

What now happens to the card in slot 9? It gets mapped to the position 13

9->13

And in 13? It gets mapped to slot 15.

13->15

If we continue this, we get a sort of chain that looks like this:

1->9->13->15->16->8->4->2->1

and we eventually get back to where we started. We will go ahead and wrap these in parentheses, like so:

(1 9 13 15 16 8 4 2)

Disregarding the double 1. Now, if we want to know what happens to any of these cards, we just go on to the next one down the line and we have our answer. But this doesn’t account for all the cards, so we go through the rest of them until we have accounted for all our cards. We’ll go ahead and just write them one after the other:

(1 9 13 15 16 8 4 2) (3 10 5 11 14 7 12 6)

Those two sets of numbers are called cycles, because if you keep doing the shuffle often enough you cycle back to where you were. And no, you don’t get to draw a card if you discard it. As we have seen before, if you shuffle your deck 8 times using the pile shuffle, you will get back exactly to where you started from. Which is why it’s not actually shuffling.

Now, for the two pile shuffles. We can easily do the same procedure as before, following each card through, but there is an easier way. What we’re going to do is multiply the two permutation or, rather, the permutation with itself. The way this works is we sort of follow what happens to our numbers as they pass through the permutations. So, 1->9->13, so we start with (1 13 … then we follow what happens to 13->15->16, so we write (1 13 16… and so on, until we end up with:

(1 9 13 15 16 8 4 2) (3 10 5 11 14 7 12 6) * (1 9 13 15 16 8 4 2) (3 10 5 11 14 7 12 6)
=(1 13 16 4) (2 9 15 8) (3 5 14 12) (6 10 11 7)

Note that we tend to sort these so that the lowest number is the first in a cycle, and then sort those in order. This permutation has four cycles of length 4, which means that after 4 of these shuffles (or eight single pile shuffles), we end up with the first order.

These permutations form a very interesting structure in mathematics called a group, which we will explore in a further article. Group theory is an interesting subset of Algebra, which is where that particular sticky subject was lurking in this article the whole time.

Next week, we’ll get random again.

Update

Due to the holiday, today’s post will go up late, possibly tomorrow but no later than that.

Have a happy fourth of July, whether you celebrate it or not!

 

Tosus

Randomness, part 1

So, today I’m going to talk about randomness, as promised. But, keeping true to the spirit of randomness, first I’m going to talk about Duels of the Planeswalkers on iPad.

First off, I’m so glad it finally made the leap to the platform. I have my iPad with me pretty much everywhere I go, and I love the ability to pull it out wherever and play a quick game of Magic or three. I do however have a few quibbles with it, hopefully thing they can change for DotP 2014.

First off, I think Stainless would do well to consider the differences in portable and console gaming. Portable gaming tends to be something one does on the side, so if I were them, for the portable version, I would get rid of the notion of time limits for responding to abilities. I realize that those are mostly to facilitate multiplayer, but given the asynchronous nature of gaming on the iPad, I don’t think it would hurt too much there either. Really, they should look at what PlayDek have done with Ascension and try to emulate that as much as possible. Granted, Ascension is a much simpler game, but they brought it to the iPad very well, and one of the great parts of it is being able to launch into a game in seconds, whereas the load time for DotP – at least on my old iPad 1 – closes in on a minute, with all the animations and menus and so on.
But other than that, I’m very happy it exists, and I have been having a lot of fun unlocking cards and dueling opponents.

Now, after that bit of randomness, randomness!

What do we mean when we say a deck is random? Well, the simplest answer is, all the cards in the deck are in a random order, which sounds reductive, but it really is important to define these things.

If all the cards in the deck are in a random order, then for any given card, which we’ll number after its position from the top of the deck, the probability that that card will be any given card in the deck is the same. Or, in symbols,

P_n(X)=1/N

Where n is the position in the deck, X is the individual card (we’re not counting multiple copies of a card just yet… we’ll get to that a bit later. Assume for now you have a singleton deck), and N is the total number of cards in the deck.

We call this the universal distribution, and it’s very important for probability theory. I’m going to skip the part where I explain how probabilities work, I assume my readers already know the basics.

It’s interesting to note that we can sum up either by n while leaving X constant, and we get:

Σ_n P_n(X) = 1

Or in other words, the probability that a given card X is actually in the deck is one. Also, we can sum over X:

Σ_X P_n(X) = 1

and get the same thing, since the probability that the card in position n is one of the cards in the deck is also one. This works since there are a total of N of both n and X.

If there are multiple copies of a given card in the deck, this formula changes somewhat. We’re going to change up our set that X is a part of a bit. We’re going to name the set of all the  individual cards in a deck, in other words including multiple copies, A, and the set of all the card names, of which some cards might be multiples, M. For any given m out of M, we’ll define c(m) to be the number of copies of that card. Since the probability that any given card will be one of those copies is, fairly obviously, equal to the probability that it is one individual card times the number of copies of that card, we have

P_n (m) = c(m)/N.

Before we close for today, I want to look at a practical example of how this can be useful. Let’s talk about opening hands. Say you have four copies of a card in your sixty card deck. What is the probability that you will draw it in your opening hand?

For starters, we’ll sum up the probability that the card will be in your first seven cards, in other words

Σ_(n=1…7) P_n(m) = c(m)/60 + c(m)/60 + … + c(m)/60 = 7 * 4/60 = 7/15

Or about half. This makes sense intuitively, but is it the whole story? Not exactly. That formula tells us what the probability is that each of the first seven cards is the card you want, but it doesn’t factor in that you might get multiple copies. But that will have to wait for another post.

Next week we’ll mix things up some more.

Exercises:

1. What happens if you sum up over the elements in M?

2. Calculate Σ_n P_n(m) = 1 for a given m in M. What is the result? How can you interpret this?

3. Is pile shuffling random? Explain why or why not.

Shuffling, part 1

So, for our first foray, we’re going to look at shuffling. We all do it, usually several times a day, but how does it work, exactly? What methods work the best for shuffling, and which don’t work at all?

That last question is interesting: Which methods of “shuffling” get used on a regular basis that don’t actually shuffle your deck. Perhaps you already know the answer, it’s the bane of judges everywhere, the so called “Pile Shuffle”.

Pile shuffling (though, as we will see, it isn’t really shuffling at all), is when a player deals cards from the top of their deck into piles in front of him or her, then picks up those piles one after another. It certainly seems random, but it is in actual fact anything but. I’ll try to illustrate this for you, starting with a simpler example.

Take a deck of 12 cards that we deal into six piles. Say also that the cards are either lands (L) or spells (S), and at the beginning the player sorted them so that they alternate land-spell-land. This is allowed, as long as the deck gets shuffled thoroughly since the order they started in will be unrelated to the order they end up in.

So, to start, our deck looks like this: L S L S L S L S L S L S (counting from the top to the bottom. If you flip them around to look at the card faces, this order will be reversed, but you usually shuffle face down)

Let us pile shuffle this deck now. The first pile will get the first land card, the second will get the first spell, the third will get the second land, and so on, till we end up with this:

L  S  L  S  L  S
L  S  L  S  L  S
1  2  3  4  5  6

When we stack these we have a deck that looks like this:

L L S S L L S S L L S S

You may already see a problem here. While this order isn’t exactly the same as the first one, it still has a very regular pattern about it, and is very predictable. This should already raise red flags, but let’s continue.

The second pile shuffle will look like this:

S  S  L  L  S  S
L  L  S  S  L  L
1  2   3  4 5  6

Remember, the first card we lay down will be at the bottom of the pile, once we lay down the first six piles the next card will be on top of the first. Piling these together gives us:

S L S L L S L S S L S L

Pretty close to our original. Already after two pile shuffles we have a big problem, but what happens after the third?

L  S  S  L  S  L
S  L  S  L  L  S
1  2  3  4  5  6

Which leads to

L S S L S S L L S L L S

Now, you might be thinking, this looks pretty random. Sure, some lands and spells are clumped together, but if you got handed a deck that looks like this, you’d assume that the player had actually shuffled it, right? Well, let’s go on to some more pile shuffles and see if this stays true.

L  L  S  L  L  S
L  S  S  L  S  S
1  2  3  4  5  6

L L L S S S L L L S S S

And one more:

L  L  L  S  S  S
L  L  L  S  S  S
1  2  3  4  5  6

L L L L L L S S S S S S

So, now we’ve gone through five pile shuffle, and we’ve nicely put all our lands on top, and all our spells on bottom. Not a very good order, strategically, but that’s not important. What is important is that we know exactly what the order is and, what’s worse, all we have to do is pile shuffle one more time

S  S  S  S  S  S
L  L  L  L  L  L
1  2  3  4  5  6

S L S L S L S L S L S L

And we have this. In other words, the exact same order that we started with, except with lands and spells reversed. In fact, do another six pile shuffles – and I’ve seen players easily do that many before starting a game – and you’ll have the same order as in the beginning. Don’t believe me? Try it yourself!

This is why pile shuffling isn’t considered randomization. After each shuffle you know exactly where the cards are going to be. Even if you pick up the piles in a random order, you still have the same relative positions of cards in the piles, which can still lead to a very non-random outcome, especially if all you care about is two qualities, such as land or non-land.

That’s it for now. When I continue this topic I’m going to break out the algebra, but next week I’m going to talk a little more about what “random” means.

Exercises:
(It’s a math blog, of course there are exercises!)

  1. What happens when you pick up the piles randomly? What can you say about the order of cards after a given number of pile shuffles?
  2. Try out the pile shuffle with a full deck of thirty lands and thirty non-land spells. How many pile shuffles do you need to get back to a pattern of land-spell-land?
  3. What about if you pile shuffle a deck while tracking three qualities: land, creature, non-creature spell. Assume equal quantities of each.

Introductions Are in Order


Welcome to my new blog, the Math of Magic.

Still here? That word “math” didn’t scare you away? Wow… well, congratulations, and thank you. I promise it won’t all be math in this blog. Well, mostly math, but it will be fun, just wait!

Well, fun for us math geeks, anyway. But want to know a secret? Come a little closer, let me whisper it to you.

If you play Magic: the Gathering, you’re a math geek.

There, I’ve said it. Don’t believe me? What if I told you a game of Magic was just one huge mathematical operation. Even the entire game of Magic, with all its tens of thousands of cards and trillions of potential interactions, can still be summed up in something as simple as a vector space. A very large vector space, granted, but not infinite.

Sorry to say, but every game of Magic you’ve ever played has just been locating, step by step, your place in this giant vector space. The names of the cards don’t matter, the flavor, the colors, all bow down to the might of math.

I sense I may be losing you, come back! It’s not all bad. The fact Magic is based on math isn’t entirely a bad thing. It’s what allows judges to make unambiguous rulings at tournaments, what allows Duels of the Planeswalkers to beat you every once in a while. And, most importantly, it lets R&D make new cards – usually by taking a look at the underlying equations and saying “okay, how can we break these?”.

If you want to play Magic without math you can, however it would become very… strange very fast. You and your opponent would have to debate what a Stronghold Overseer actually oversees, and whether Calling the Wild summons wolves to do your bidding, or just lets your Evolving Wild, well, evolve. In short, it would be a game without rules, just with storytelling. That game exists too, and it’s called “Dungeons and Dragons” (which technically has rules, but also has a player that can override any of those rules at a whim). Many people do enjoy that game, and many of them also enjoy Magic, but I feel quite confident that those few that actually play Magic solely for the flavor will be quickly disappointed when you equip your Sword of Feast and Famine to a Wall of Omens, and struggle to figure out how any of that makes any kind of flavor sense.

Yes, Magic is based on rules, and rules are based on math. I am firmly of the opinion that understanding math is key to becoming a better Magic player. With that in mind, I intend to dive in to the swirling morass of algebra, probability theory, game theory, and perhaps even a bit of calculus (though probably not a lot) that goes into each and every game of magic you’ll play.

For a flavor of what I intend to look out, check out the article I wrote for Cardshark.com (if you just read that in Chewies voice, then send me an email!) at http://www.cardshark.com/Articles/Magic-the-Gathering/Thomas-Edgar/Math-Magic/View-Article/4270. And if you don’t believe me that math can be fun, check out Vi Hart’s YouTube channel at http://www.youtube.com/user/Vihart.

Stay tuned for my first article on the Math of Magic, where we will look at something that happens in every single game of Magic, oftentimes before it even begins: shuffling.

If you want to get in touch with me, you can email me at dergeek@gmail.com, follow my Twitter feed at twitter.com/Tosus, call my voicemail line at 425-200-4335, or subscribe to me on Facebook under https://www.facebook.com/Tosusiam.

Thank you for reading, and stay mathy!