Archive for the ‘Statistics’ Category

Estimating the Number of Magic Game States by Frank L.

Tuesday, December 15th, 2009

(I think I might be posting mainly very technical ones, unless there’s interest in seeing the other ones. I don’t intend to post all of them, but I figure I should at least present the ones with the most innovative ideas. In this one, Frank does what he says in the title: estimates the number of Magic game states. I talked about the position space of Magic and how big it is, but Frank actually goes about quantifying it. Anyone want to check his math?)

Like many other games, Magic has a finite game state. That is, there are a finite number of combinations of cards in play, cards exiled, cards in the graveyard, cards in the library, cards in the hand, cards tapped, counters, life totals, etc., at least in normal gameplay. This fact arises from the finite set of cards in existence, and, as far as I know, no card exists that can lead to a repeated game state. This leads to a natural question: how complex is Magic?

I assume that the number of possible game states is a measure of the complexity of the game. Checkers, which has already been solved, has around 1018 board positions; chess has 1043 positions; go has a whopping 10190 board positions. The rules of Magic are significantly more complex than the straightforward rules and limited pieces of checkers, chess, and go, which makes it necessary to make a few simplifying assumptions.

First, I establish the definition of a board position in Magic. I simplify the set of all cards into three categories: lands, creatures, and other spells. With this trichotomy in mind, I consider life totals, number of cards in the library, number of cards in hand, creatures in play, land in play, creatures tapped, lands tapped, and number of cards in graveyard, but I do not consider counters, planeswalkers, cards exiled, cards morphed, etc. My game states are evaluated at the beginning of each turn, where each player takes a different turn. Because of the wide and ever-expanding rules of Magic cards, there are too many contingencies, too many twisted subtleties in the rules for me to include other parameters in this estimate.

Second, I consider only the case of a two-player game, with life totals starting at 20, each with 60 unique and distinguishable cards. I use averages of the top 11 decks listed on the Magic the Gathering site to establish 24 lands, 20 creatures, and 16 other spells in this deck. I assume a mana curve of 3. The assumption that the deck has 60 distinguishable cards may seem unfounded, especially considering that most decks will have 3 or 4 of the same crucial card. In some ways, this assumption serves to counterbalance the lack of treatment of other board situations that can arise in normal gameplay.

Third, I make the assumption that decks are randomly shuffled, that each player draws exactly one card each turn, that only damage is dealt by creatures, that creatures are X/X (where X is their converted mana cost), that all spells are colorless (and hence do not run into the issue of mana color), and that all non-creature spells are instants and deal X/2 damage, where X is their converted mana cost. The maximum hand size of 7 is not enforced. No spell-countering, life-gain, discards, mulligans, or other aberrations occur.

Fourth, I violate all rules of statistics and make the simplifying assumption that E[AB] = E[A] * E[B] for all A and B. That is, any two variables of interest are independent. This affords a convenient way of calculating the number of Magic game states. I calculate by simulation the number of possible board positions per game. The total number of Magic positions is this number, multiplied by all valid pairs of 60-card decks formed by permuting the 17,118 unique Magic cards in existence.

Let’s define a few terms and variables. A turn consists of a move by a single player, so player one will have odd turn numbers and player two will have even turn numbers. Let Ln be the life total on turn n. Then let Hn = HCn + HLn + HSn be the number of cards in hand at the end of turn n, where HC, HL, and HS are the number of creatures, lands, and other spells in the hand at the end of turn n. Let PCn and PLn be the number of creatures and lands in play at the end of turn n. Further subdivide these into TPCn and UPCn (tapped and untapped creatures) and TPLn and UPLn­ (tapped and untapped lands) at the end of turn n. Let Tn = 3 be the average power/toughness of the creatures in play by turn n, and Cn = 3 be the average converted mana cost of the creatures and other spells in the hand.

A conceptual argument for the calculations of these two numbers follows. E[Hn] is the number of cards in the hand after the draw step of turn n. So the update for the draw step is

Hn := Hn + 1 Card draw

HLn := HLn + 24 / 60

HCn := HCn + 20 / 60

HSn := HSn + 16 / 60

Each turn, a player can play a land if E[HLn] > 1, play spells with a combined mana cost less than or equal to E[UPLn], attack with any combination of E[UPCn], and be blocked against by any combination of E[UPCn-1]. Since game states are evaluated at the beginning of each turn, the order of playing lands, playing spells, and attacking does not matter. To account for summoning sickness, I will assume that all spells are played in main phase 2, after attacking.

Let’s address attacking first. Random attacking is a binomial distribution with N = E[UPCn] and p = 0.5. The number of attacking possibilities is 2 ^ E[UPCn­], since each creature can either attack or not, and the expected number of attackers per turn is E[UPCn]/2. Random blocking is a multinomial distribution with N = E[UPCn-1] and p = 1/(E[UPCn]/2 + 1). Then the number of blocking possibilities by the opponent is (E[UPCn]/2 + 1) ^ E[UPCn-1]; that is, each of the opponent’s creatures can block one of the attacking creatures or not at all, and the expected number of blockers per attacker is E[UPCn+1] / (E[UPCn]/2 + 1), multiplied by a BLOCKING_COEFF that specifies players’ tendencies to block. Assuming that the creatures have roughly the same power and toughness by symmetry, the number of attacking creatures killed KAn roughly equals the number of defending creatures killed KDn: E[KAn] = E[KDn] = E[UPCn] * E[UPCn+1] / ((E[UPCn]/2 + 1) * 2). Then the following updates occur after the attack:

Ln+1 := Ln+1 – (UPCn/2 – KAn) * Tn Life total of the opponent

UPCn+1 := UPCn-1 – KD­n Defenders killed

PCn+1 := PCn-1– KDn

TPCn := PCn – UPCn/2 – KAn Attackers killed and tapped

UPCn := UPCn/2 Non-attackers remain

PCn := UPCn + TPCn Update creature count

After the attack, a land is played if possible:

UPLn := PLn + (HLn >= 1 ? 1 : 0) Land played

PLn+2:= UPLn

Then creatures and spells are played. The total number of E[HCn] creatures and E[HSn] other spells played follows a uniform distribution from 0 to E[UPLn] / E[Cn] , for an average number of x = min(E[HCn] + E[HSn], E[UPLn] / (E[Cn] * 2). Then the number of creatures played is E E[HCn] / (E[HCn] + E[HSn] ) * x, and the number of spells played is E E[HSn] / (E[HCn] + E[HSn] ) * x. This introduces 2 ^ (E[UPLn] / E[Cn]) possibilities at this stage. So the updates after main phase 2 are

UPCn := UPCn + E[HCn] / (E[HCn] + E[HSn] ) * x

PCn := UPCn + TPCn

HCn := HC­n – E[HCn] / (E[HCn] + E[HSn] ) * x Creature played

HSn := HS­n – E[HSn] / (E[HCn] + E[HSn] ) * x

Ln+1 := Ln+1 – E[HSn] / (E[HCn] + E[HSn] ) * x / 2 Spell played

TPL­n := PLn / 2 Lands tapped

UPLn := PLn / 2 Lands untapped

Hn := Hn – E[UPLn] / (E[Cn] * 2) Hand count update

Finally, plugging in the initial values and simulating on a computer:

E[Cn] = 3 E[Tn] = 3

L1 = L2 = 20 BLOCKING_COEFF = 0.5

H1 = 7 E[HL1] = 7 * 24 / 60 E[HC1] = 7 * 20 / 60 E[HS1] = 7 * 16 / 60

H2 = 7 E[HL2] = 7 * 24 / 60 E[HC2] = 7 * 20 / 60 E[HS2] = 7 * 16 / 60

n

L

H

HL

HC

HS

PC

UPC

TPC

PL

UPL

TPL

#poss

1

20

5.83

1.8

2.24

1.79

0.09

0.09

0

1

0.5

0.5

1.26E+00

2

19.96

6.83

2.2

2.57

2.06

0.09

0.09

0

1

0.5

0.5

1.59E+00

3

19.96

5.5

1.2

2.39

1.91

0.28

0.23

0.04

2

1

1

2.70E+00

4

19.76

6.5

1.6

2.72

2.18

0.27

0.23

0.04

2

1

1

4.61E+00

5

19.77

5

0.6

2.44

1.96

0.53

0.41

0.12

3

1.5

1.5

1.14E+01

6

19.28

6

1

2.78

2.22

0.51

0.41

0.1

3

1.5

1.5

2.88E+01

7

19.34

4.33

0

2.41

1.93

0.84

0.63

0.21

4

2

2

1.13E+02

8

18.49

5.33

0.4

2.74

2.19

0.78

0.61

0.18

4

2

2

4.51E+02

9

18.67

4.67

0.4

2.37

1.9

1.07

0.76

0.31

4

2

2

2.38E+03

10

17.42

5.67

0.8

2.7

2.16

0.97

0.72

0.25

4

2

2

1.22E+04

11

17.77

5

0.8

2.33

1.87

1.22

0.85

0.37

4

2

2

7.99E+04

12

16.18

4.83

0.2

2.57

2.06

1.19

0.89

0.3

5

2.5

2.5

6.20E+05

13

16.69

4.17

0.2

2.2

1.76

1.4

1.01

0.39

5

2.5

2.5

6.18E+06

14

14.82

5

0.6

2.44

1.96

1.32

0.98

0.34

5

2.5

2.5

6.09E+07

15

15.48

4.33

0.6

2.07

1.66

1.51

1.08

0.43

5

2.5

2.5

7.24E+08

16

13.35

4

0

2.22

1.78

1.5

1.12

0.37

6

3

3

1.03E+10

17

14.14

3.33

0

1.85

1.48

1.64

1.21

0.43

6

3

3

1.80E+11

18

11.83

4

0.4

2

1.6

1.59

1.19

0.4

6

3

3

3.16E+12

19

12.71

3.33

0.4

1.63

1.3

1.72

1.26

0.46

6

3

3

6.34E+13

20

10.24

4

0.8

1.78

1.42

1.65

1.23

0.42

6

3

3

1.23E+15

21

11.23

3.33

0.8

1.41

1.13

1.76

1.29

0.47

6

3

3

2.67E+16

22

8.6

2.83

0.2

1.46

1.17

1.77

1.34

0.43

7

3.5

3.5

6.96E+17

23

9.68

2.17

0.2

1.09

0.87

1.86

1.4

0.46

7

3.5

3.5

2.09E+19

24

6.96

2.67

0.6

1.15

0.92

1.84

1.39

0.45

7

3.5

3.5

6.42E+20

25

8.08

2

0.6

0.78

0.62

1.9

1.43

0.47

7

3.5

3.5

2.13E+22

26

5.27

1.33

0

0.74

0.59

1.96

1.51

0.46

8

4

4

8.80E+23

27

6.42

0.67

0

0.37

0.3

2

1.54

0.46

8

4

4

4.07E+25

28

3.59

1

0.4

0.33

0.27

2.02

1.56

0.47

8

4

4

2.00E+27

29

4.71

0.4

0.4

0

0

2.01

1.53

0.48

8

4.2

3.8

1.02E+29

30

1.88

0.8

0.8

0

0

1.99

1.5

0.49

8

4.4

3.6

5.24E+30

31

2.98

0.8

0.8

0

0

1.65

1.16

0.49

8

6.2

1.8

2.60E+32

32

0.28

0.2

0.2

0

0

1.72

1.16

0.56

9

7.2

1.8

1.31E+34

33

1.16

0.2

0.2

0

0

1.48

1.03

0.46

9

7.2

1.8

5.06E+35

34

-1.22

0.6

0.6

0

0

1.6

1.08

0.52

9

7.2

1.8

2.00E+37

According to this calculation, the average length of a Magic game is a reasonable 33 turns, with around 1035 different possibilities of play. However, this does not include the 60! possible permutations of cards drawn for each deck. So each game has 1035 * (60!)2 ~ 10200 possible outcomes. Then considering all possible pairs of 60-card decks, I derive the following for the number of possible Magic game states: 10200 * ((17118!) / (60! * 17058!))2 ~ 10550 .

This number is unfathomably large, much larger than the 10190 board positions of go. Even though the estimate of 10550 game states is necessarily extremely rough and simplified, it provides a glimpse into the true nature of the game’s complexity. In the end, all this math has simply confirmed what we perhaps knew all along: Magic is complex.

Posted in Final Papers, Statistics | 2 Comments »

Swans at the Monte Carlo

Thursday, July 23rd, 2009

Looking around on the internet, I found a few interesting articles doing hard stats work on magic. Pretty consistently, though, instead of doing combinatorial (is that a word?) analysis, they just ran a monte carlo simulation to determine what happens. Having just taken a class on probability, I thought I would try to do some deck analysis the definite, combinatoric way. And then I realized it was hard, so I did a monte carlo simulation as well.

Monte Carlo simulations are named after the casino, though I’m not entirely sure why. The basic idea of it is that often, you have problems you want to solve that either don’t have closed forms or have very complex closed forms (closed forms are expressions that are finite and well-defined. Sorry that’s vague, but I’m not entirely sure what the official definition is either). In the case of Magic, I’m pretty sure closed forms exist to express what sequence of cards you draw and how winnable certain orderings are, but they’re hard. Instead, one can find an approximate solution by running a very large amount of simulations of the problem and determining the answer at the end by averaging over all of those answers.

One place where this can be applied in Magic is to determine when a deck can win. One deck that’s come out of nowhere recently is cascade swans. The deck basically works by combining seismic assault with swans of bryn argoll and a lot of lands. Once you get both cards out, you start whacking your own swans to draw lots of cards, then pitch a bunch of lands to do damage to your opponent. Fun. It got cool when Alara Reborn was printed because cascade cards effectively increase the number of copies you have of each of those cards. So it’s a combo deck, and when the pieces are down, it goes.

There are a couple reasons why I decided to do an analysis of this deck. First, it’s simple. Barring lands (which I kind of ignore because they’re hard), there are only 5 different cards. Because it’s a combo deck, you know exactly when it wins. Two, it’s very non-interactive. Pre-sideboarding, it doesn’t really bother to do anything with or to your opponent other than spontaneously win. The simulation works really well as a goldfish to make it simpler. Three, I was curious to see how the deck works, because I’ve actually never played, played against, or even seen it played in a youtube video. It seems like an easy deck to play, too, unlike, say, sunny-side up, so that would make it easy to program.

To make this work, I threw together a python script that plays a swans deck. It has some pretty simple logic on making choices, and actually punts on most of Magic. But I figured that’s okay. So here’s a look at a couple sample runs.

I ended up programming it in steps to make sure it worked all the way along, and that actually gives us some interesting analysis. Over 100,000 runs, I compiled how many times the deck won on that turn in 4 cases. 1) Assuming Ad Nauseam and Cascade are dead cards and do nothing 2) Cascade works, but Ad Nauseam doesn’t 3) Both work, and Bloodbraid Elf is preferred to be played before Bituminous Blast and 4) Both work, and Blast before Elf. Here are 2 graphs on it. The first is how often it was won on that turn, and the second is cumulative (meaning how often it won by that turn)

Swans data

>>> swans.playGame()
DECK
Land Land Land Land Land Land Land Land Land Land Land Land Land SwansofBrynArgoll SeismicAssault Land Land BituminousBlast Land Land BituminousBlast Land BituminousBlast BloodbraidElf Land Land Land Land SeismicAssault AdNauseam SeismicAssault SwansofBrynArgoll Land BloodbraidElf SwansofBrynArgoll Land Land Land Land Land BloodbraidElf Land SeismicAssault Land Land Land Land BloodbraidElf Land Land Land Land Land
HAND
Land Land Land Land SwansofBrynArgoll BituminousBlast AdNauseam
Turn 1
Turn 2
You drew a Land
Turn 3
You drew a Land
Turn 4
You drew a Land
You play SwansofBrynArgoll
Turn 5
You drew a Land
You play AdNauseam
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a Land
Off of Ad Nauseam, you drew a SwansofBrynArgoll
Off of Ad Nauseam, you drew a SeismicAssault
Your life is now 13 because of Ad Nauseam
Turn 6
You drew a Land
You play SeismicAssault
You won on turn 6!

swans-cumulative

(there’s some graph-making noobness. sorry)

So some interesting stuff out of that. There’s a 24%ish chance of winning on turn 3 just by playing seismic assault turn 3 and swans turn 4. Just about 53% chance of winning by turn 5 when cascade is turned on, 66% by turn 6, and 86% by turn 10. That’s pretty impressive. There were two things I thought were impressive. One, cascade is obviously huge. Ad Nauseam helps, but it’s really the cascade that makes turn 5 and 6 shine in consistency. Two, there isn’t a significant difference between playing elf or blast first when you don’t have either assault or swans on the table. I guess I could do analysis to figure out whether it should, but the lines are right on top of each other, so it doesn’t seem to matter.

There are obviously some huge issues with the analysis as is, which I know. This includes:

  • No opponent. Of course goldfishing isn’t entirely meaningful
  • I assume that when assault and swans hit the table, you win. This isn’t necessarily true, but I haven’t heard otherwise. If it happens, though, please tell me, and I can stop being lazy and add that to the model
  • It never mulligans, so it’ll keep 7 land hands.
  • Ad Nauseam doesn’t really look for specific cards. It just chugs until it loses about 10 life.
  • And most importantly, I DIDNT ACCOUNT FOR COLORS

There are at least 3 colors in this deck, and more in some other builds. Trip red on assault makes it hard to get other stuff out, so this isn’t entirely fair. Admittedly, I think this sort of analysis is most valuable when figuring out if you’re getting the right colors, but that takes a lot more work that I wasn’t willing to do, since I figured this would be a quick and dirty script.

If you have any programming knowledge, please take a look at the script. I likely made some mistake, and I would definitely be willing to fix that. Even if you don’t program, it’s python; it’s supposed to read pretty much like english anyways, so take a look. And if you have any ideas about how I can make the script more powerful/inclusive or any other analysis that you think might be useful, feel free to leave a comment.

(edit: I guess I should throw out the caveat that this is very much a work in progress. I plan on iterating this a lot before presenting it, so please, any criticism will be good. Particularly, if you’ve actually played swans before, it would be helpful to just get some idea how it’s played. For example, I assumed that swans players prefer to play, not draw, first, and that there’s generally an order to which cards are played. Let me know if there are any more nuances to playing that I could potentially include)

Posted in Statistics | No Comments »