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

(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¹⁸ board positions; chess has 10⁴³ positions; go has a whopping 10¹⁹⁰ 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₁ = L₂ = 20 BLOCKING_COEFF = 0.5

H₁ = 7 E[HL₁] = 7 * 24 / 60 E[HC₁] = 7 * 20 / 60 E[HS₁] = 7 * 16 / 60

H₂ = 7 E[HL₂] = 7 * 24 / 60 E[HC₂] = 7 * 20 / 60 E[HS₂] = 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³⁵ different possibilities of play. However, this does not include the 60! possible permutations of cards drawn for each deck. So each game has 10³⁵ * (60!)² ~ 10²⁰⁰ possible outcomes. Then considering all possible pairs of 60-card decks, I derive the following for the number of possible Magic game states: 10²⁰⁰ * ((17118!) / (60! * 17058!))² ~ 10⁵⁵⁰ .

This number is unfathomably large, much larger than the 10¹⁹⁰ board positions of go. Even though the estimate of 10⁵⁵⁰ 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.

This entry was posted on Tuesday, December 15th, 2009 at 6:36 pm and is filed under Final Papers, Statistics. 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.