*(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 10^{18} board positions; chess has 10^{43} positions; go has a whopping 10^{190} 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 L_{n} be the life total on turn n. Then let H_{n} = HC_{n} + HL_{n} + HS_{n} 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 PC_{n }and PL_{n} be the number of creatures and lands in play at the end of turn n. Further subdivide these into TPC_{n} and UPC_{n} (tapped and untapped creatures) and TPL_{n} and UPL_{n} (tapped and untapped lands) at the end of turn n. Let T_{n} = 3 be the average power/toughness of the creatures in play by turn n, and C_{n} = 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[H_{n}] is the number of cards in the hand after the draw step of turn n. So the update for the draw step is

H_{n} := H_{n }+ 1 Card draw

HL_{n} := HL_{n} + 24 / 60

HCn := HC_{n} + 20 / 60

HS_{n} := HS_{n} + 16 / 60

Each turn, a player can play a land if E[HL_{n}] > 1, play spells with a combined mana cost less than or equal to E[UPL_{n}], attack with any combination of E[UPC_{n}], and be blocked against by any combination of E[UPC_{n-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[UPC_{n}] and p = 0.5. The number of attacking possibilities is 2 ^ E[UPC_{n}], since each creature can either attack or not, and the expected number of attackers per turn is E[UPC_{n}]/2. Random blocking is a multinomial distribution with N = E[UPC_{n-1}] and p = 1/(E[UPC_{n}]/2 + 1). Then the number of blocking possibilities by the opponent is (E[UPC_{n}]/2 + 1) ^ E[UPC_{n-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[UPC_{n+1}] / (E[UPC_{n}]/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 KA_{n} roughly equals the number of defending creatures killed KD_{n}: E[KA_{n}] = E[KD_{n}] = E[UPC_{n}] * E[UPC_{n+1}] / ((E[UPC_{n}]/2 + 1) * 2). Then the following updates occur after the attack:

L_{n+1} := L_{n+1} – (UPC_{n}/2 – KA_{n}) * T_{n} Life total of the opponent

UPC_{n+1} := UPC_{n-1} – KD_{n }Defenders killed

PC_{n+1} := PC_{n-1}– KD_{n}

TPC_{n} := PC_{n} – UPC_{n}/2 – KA_{n }Attackers killed and tapped

UPC_{n} := UPC_{n}/2_{ }Non-attackers remain

PC_{n} := UPC_{n} + TPC_{n} Update creature count

After the attack, a land is played if possible:

UPL_{n} := PL_{n} + (HL_{n} >= 1 ? 1 : 0) Land played

PL_{n+2}:= UPL_{n}

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

UPC_{n} := UPC_{n} + E[HC_{n}] / (E[HC_{n}] + E[HS_{n}] ) * x

PC_{n} := UPC_{n} + TPC_{n}

HC_{n} := HC_{n} – E[HC_{n}] / (E[HC_{n}] + E[HS_{n}] ) * x Creature played

HS_{n} := HS_{n} – E[HS_{n}] / (E[HC_{n}] + E[HS_{n}] ) * x

L_{n+1} := L_{n+1} – E[HS_{n}] / (E[HC_{n}] + E[HS_{n}] ) * x / 2 Spell played

TPL_{n} := PL_{n} / 2 Lands tapped

UPL_{n} := PL_{n} / 2 Lands untapped

H_{n} := H_{n} – E[UPL_{n}] / (E[C_{n}] * 2) Hand count update

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

E[C_{n}] = 3 E[T_{n}] = 3

L_{1} = L_{2} = 20 BLOCKING_COEFF = 0.5

H_{1} = 7 E[HL_{1}] = 7 * 24 / 60 E[HC_{1}] = 7 * 20 / 60 E[HS_{1}] = 7 * 16 / 60

H_{2} = 7 E[HL_{2}] = 7 * 24 / 60 E[HC_{2}] = 7 * 20 / 60 E[HS_{2}] = 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 10^{35} different possibilities of play. However, this does not include the 60! possible permutations of cards drawn for each deck. So each game has 10^{35} * (60!)^{2} ~ 10^{200} possible outcomes. Then considering all possible pairs of 60-card decks, I derive the following for the number of possible Magic game states: 10^{200} * ((17118!) / (60! * 17058!))^{2} ~ 10^{550} .

This number is unfathomably large, much larger than the 10^{190} board positions of go. Even though the estimate of 10^{550} 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.

If different life totals are considered different states then there are infinite states as there are numerous infinite combos, life-gain or otherwise.

Yes, though one of the mentioned assumptions to make the approximation work was that there were a finite number of life totals. Although it’s true that infinite combos allow for an infinite number of life totals, adding this constraint makes this analysis tractable.

Another fact that may make this approximation more justified is that many of those life totals are indistinguishable. For most game states, there’s no difference between a player being at 1 million life and 1 billion life. The fact that there exists a deck that can distinguish these makes this a cheap point, but the general indistinguishability of them is a good footnote.