Tuesday, December 21, 2010

Visualizing hypergeometric distribution

What are the chances to draw exactly one card of four in a sixty card deck? This is exactly the question the hypergeometric distribution answers. Here are two graphs showing this distribution. First, the height of the bars shows the percentage of hands that have exactly the specified number of cards. The red bars show chances for drawing exactly one card of four. As you can see the maximum value is about 44% when 15 cards are drawn. This also happens to be when the average or mean value is exactly one.


Here is the same data with the bars stacked to show that the percentages always add to 100. This view clearly shows that your chance to draw at least one of the four cards after drawing fifteen is about 69%.

Saturday, December 11, 2010

How to calculate whether you have enough mana, continued

What are the chances that you will have one land to play for each of the first four turns? Using Deck-u-lator to answer that question was the topic of an earlier article.  Here is a graph showing the chance of having one land on turn one, two land on turn two, and so on for different 60 card decks.

With 20 land, there is a 54% chance to have 4 land on turn 4
With 24 land, there is a 57% chance to have 5 land on turn 5
With 28 land, there is a 51% chance to have 7 land on turn 7

Wednesday, December 8, 2010

Deck-u-lator JSON API

If you are interested in using Deck-u-lator from other applications, there is a simple interface. You can call the calculator directly from a URL.

http://deckulator.appspot.com/rpc
action=Calculate
arg0 is a JSON expression describing the problem to be calculated. The entire problem is a comma delimited list surrounded by square brackets. Each card type is represented by a two-element list. The first element is the number of cards in your deck. The second element is the number of cards in your combination.
arg1 is the number of cards you draw

The following example requests calculation of drawing 8 cards from a 12 card deck. The deck has three card types. The combination includes one card from the second and third types. The result is returned.

http://deckulator.appspot.com/rpc?action=Calculate&arg0=[[4,0],[4,1],[4,1]]&arg1=8

Sunday, December 5, 2010

Visualizing probabilities

I have been experimenting with Google Charts for displaying Deck-u-lator results. Here are the chances for drawing combinations with two, three, and four cards. These assume you have four of each card in your deck and are playing with a 60 card deck.
You can see similar charts when you calculate results from any of the example problems posted here.

Saturday, December 4, 2010

How does it work?

Deck-u-lator computes the ratio between the number of different hands that include specific cards and the number of possible hands that can be drawn from the deck you describe. If half these possible hands have the card combination you want, there should be a 50% or 0.5 chance of drawing your combination.

Calculating this chance uses a branch of mathematics called combinatorics. The number of different ways to choose \(H\) elements from a set of \(D\) elements is called the binomial coefficient is calculated using factorials (!).

$$ \binom{D}{H} = \frac{D!}{H!\,(D-H)!} $$

The number of different hands of size \(H\) drawn from a deck of \(D\) cards is \(\binom{D}{H}\). A similar formula is used to calculate the number of ways to satisfy each part of your combination. If your deck has \(D_X\) cards of type \(X\) and you need \(H_X\) for your combination, then there are \(\binom{D_X}{H_X}\)  different ways to choose the type \(X\) cards you need. The number of hands with the cards you need is the product of all the different ways to choose each card. This is called a multivariate hypergeometric distribution (without replacement).

The Mathematics of Magic The Gathering: Probability, Statistics, Game Theory, and Strategy by Jon Prywes has an excellent discussion of mathematics for games if you are looking for even more information.


Why are some calculations slow?

Deck-u-lator calculates card combo probabilities using multivariate hypergeometric distribution.  This calculation is relatively fast if the number of cards you draw is the same as the size of your combo.  However, things slow down when you try calculating results for big combinations when you draw about half your deck.  Why is that?

The problem is what to do with the extra cards.  If you want to know the chances of drawing a four card combo in the first twenty cards, there are sixteen extra cards.  Deck-u-lator tries all the different ways to choose those extra cards.  For each way to choose those extra cards from your deck, add them to your combination and then calculate the multivariate hypergeometric distribution.

How many different ways are there to choose those extra cards?  Our Black Lotus Mana Vault combination uses a deck with five types of cards.  The combination has five cards from four of those types.  If we want to calculate results for drawing thirty cards, we have twenty-five extra cards to work with.  How many ways are there to choose twenty-five cards from five different types?  In mathematical terms these twenty-five cards are a multiset and an upper bound on the number of different ways to choose them can be calculated as the number of combinations with repetition.  For this example there are 23,751 different multisets of twenty-five cards from five types.
$$ \binom{25+5-1}{25} = \binom{29}{25} = 23,751 $$
Deck-u-lator is fast enough that generating these multisets and then calculating the hypergeometric distributions only takes about half a second.  But if we try something similar with fifteen different types of cards, the number of multisets is much larger.  At the same speed this will take about four hours.
$$ \binom{15+15-1}{15} = \binom{29}{15} = 77,558,760 $$
Decks with eight types of cards are about the limit.  Calculations for drawing thirty cards from a deck like this will require 1,560,780 multisets and can be done in under ten minutes
$$ \binom{22+8-1}{22} = \binom{29}{22} = 1,560,780 $$

Monday, November 22, 2010

Building a Sligh Deck

Building a Sligh deck

SuperDad suggests another problem for the Deck-u-lator. What is the best distribution for cards in a Sligh deck? These decks are mono-color and have lots of small creatures that come out quickly and build to successively larger creatures as the game progresses.
Let's start with a simpler question. What are the chances of being able to get and cast a spell with a casting cost of 1 on your first turn. With 23 mountains 60 cards total, what we are varying is the number of casting cost 1 spells (called 1-drops here). The settings below will calculate the chance for being able to open with a 1-drop with 10 in your deck.


First turn Creature combination
have need card
Mountain
Creature
other



Adding more creatures to the mix

It would be fun to make similar graphs for 1-drops and 2-drops (bears). Similarly, for 1, 2, and 3-drops combined. The settings below can be used for your own experiments.
Remember to read about how to use Deck-u-lator to calculate chances when either one of two combinations will work. The basic idea is to calculate each combination on its own, add those chances, and then subtract the chance of getting a hand that has both combos.

Sligh, the original fast burn deck, was designed by Dave Price and was based upon the concept of being able to use all your mana every turn. It was built upon the following mana curve.

CostQuantity
1-drop9-13
2-drop6-8
3-drop3-5
4-drop1-3
X-spell2-3


Sligh deck combination
haveneedcard
Mountain
1-drop Creature
2-drop Creature
3-drop Creature
4-drop Creature
X Sorcery
other



How to calculate whether you have enough mana

These examples come from SuperDad for calculating the probability of drawing enough mana.


Example 1: Probability of lands in first four turns


If you want to know how what the probability of playing lands in each of your first 4 turns (you don't go first, 4+7=11 cards drawn), in a deck of 60 cards where 20 are land. Try it! If you want better than about a 50/50 chance of playing lands on each of your first 4 turns (to get that Juggernaut out), you need to add more land, elves, dark rituals, or something similar.

Black Lotus combination
have need card
Land
other








Example 2: Probability of drawing killer card within five turns


You have 4 I-win-you-lose-super cards in your deck. What is the probability that you'll draw one of your super cards in the first 5 turns? (5+7=12 cards drawn. As before, other player draws first so you get to draw on turn 1, 60 card deck). Try it! You can improve your odds by adding impulse, intuition, or something similar.


Mana Vault combination
have need card
I-win-you-lose
other







Example 3: Probability to draw and play a WW Creature


You are playing a 60-card white and red deck with 13 plains and 9 mountains. Your deck is loaded with WW creatures. What is the probability that you will be able to bring out one of these creatures on the second turn? Not good enough for a fast deck, you'd better put in more plains!! With Deck-u-lator we can also factor in the probability of drawing a WW creature to go with those 2 plains by adding a third card type.

Black Lotus and Mana Vault combination
have need card
Plains
WW Creature
other




Friday, November 19, 2010

Combinations with types

A natural way to specify card combinations refers to both specific cards and generic card types. For example, to power 1BB you need to draw two swamps and one other land. The killer combination from Reign of Vampirism requires a Captivating Vampire and four other Vampires. Deck-u-lator was designed to automatically try all the different ways of drawing extra cards. For these two cases above, we need to restrict how cards are drawn.

Here is one way to approach this problem. Since there is only one Captivating Vampire in the deck, the other four Vampires must be different cards. We can pretend there is a card called Vampire from which we need to choose four. The same trick does not work for land. Two lands need to be Swamps. The third could be either a Forest or a Swamp. We can use our usual technique for calculating or combinations here. Calculate once with three Swamps (18%), once with two Swamps and a Forest (19%), add the results, and subtract a hand with three Swamps and a Forest so we do not double count (18%), for a total result of 19%

All this would be easier if Deck-u-lator could recognize card types and use them automatically in calculations.


Using a Captivating Vampire

have need card
other
Captivating Vampire
Vampire
Swamp
Forest








Wednesday, November 10, 2010

How to calculate exact combinations

If the number of cards you draw exactly matches the number of cards you have specified, Deck-u-lator will calculate how likely it is to draw exactly that hand. When you draw more cards than you specify, Deck-u-lator tries all the different possibilities for assigning the remaining cards.
You can make use of the default card type, other, to round out your deck description. Here is an example of how to use other to calculate both exact and "at-least" combinations.
How likely is it that you will have at least a Mountain and a Lightning Bolt in your first eight cards? Design your deck then assign the numbers you have and need. The card type other is used here to make sure that calculations reflect drawing from a 60 card deck; the number of cards you have adds up to 60. Since the number of cards you need (2) is less than you draw (8), Deck-u-lator will include hands that have more than one Mountain and more than one Lightning Bolt as also satisfying your combination.

At least combination
have need card
other
Lightning Bolt
Mountain




Instead, if you want to know how likely it is to draw exactly one Mountain and one Lightning bolt, then you can require that the remaining six cards be drawn from the other type.

Exact combination
have need card
other
Lightning Bolt
Mountain




Monday, November 8, 2010

How to calculate the probability when either one of two different cards will do

Question:

I wrote a program for calculating probabilities myself, but I am not sure how to develop unions. How big is P if I have

1 Lotus

4 Mana Vaults

4 Goblin Mutants


in a 60 cards deck and want to bring out the Goblin Mutant on 2nd turn. Of course I could turn the Lotus into a 5th Vault, but that is not very proper. I think.

Answer:

Let me see if I understand what you are asking. You want to know how likely it is to bring out a Goblin Mutant on turn two. Ordinarily, the only available mana sources at that time would be two lands (mountains), so you will need extra mana. You include both a Black Lotus and four Mana Vaults for this purpose. You are not asking for the likelihood of a single combination, but for the combined likelihood of two different combinations. One combination has the Goblin Mutant, land, and the Lotus. The other combination has the Goblin Mutant, land and a Mana Vault.

Assuming you have 20 mountains in your deck, there is a 7% chance that you will get the Goblin Mutant out with the Lotus and a mountain in nine cards. There is an 18% chance that you get the Goblin Mutant out with a Mana Vault and two mountains in nine cards (plus one point of mana burn). There is a 3% chance that you get both a Lotus and a Mana Vault in the first nine cards (along with the Goblin Mutant and two mountains). Therefore, there should be a 23% chance to get your Goblin Mutant out by the second turn. This number is obtained by adding the likelihoods of the alternatives taken separately, and then subtracting the likelihood that they happen together.

It makes sense to subtract the combined likelihood so that you do not double count those hands. The likelihood is derived from counting the number of hands that have the combination and dividing that count by the number of possible hands of a given size. Of the 960 million hands that have the Lotus combination, 400 million also have the Mana Vault combination. Similarly, of the 2.7 billion hands that have the Mana Vault combination, 400 million have the Lotus combination. So the number of hands that can cast the Goblin Mutant on turn two is 3.3 billion. (2.7 billion + 960 million - 400 million)

As you suspect, this is very close to what you would get if you just counted the Black Lotus as another Mana Vault. There are 3.1 billion hands that have the Mana Vault combination if you permit five of them in the deck. That does not take into account the fact that you need one less mountain when using the Black Lotus.

Using Deck-u-lator

For the Black Lotus combination, zero out the Mana Vault. Then get the likelihood for the first nine cards.


Black Lotus combination
have need card
other
Black Lotus
Goblin Mutant
Mana Vault
Mountain





For the Mana Vault combination, zero out the Black Lotus and add another Mountain.


Mana Vault combination
have need card
other
Black Lotus
Goblin Mutant
Mana Vault
Mountain





Add those first two likelihoods together and subtract the likelihood of the hand that has everything. You can get the likelihood for a hand with everything by setting the Black Lotus and the Mana Vault both to 1. (Make sure you include both Mountains.)

Black Lotus and Mana Vault combination
have need card
other
Black Lotus
Goblin Mutant
Mana Vault
Mountain





Long live Deck-u-lator

Deck-u-lator has moved to the Google App Engine.  There are several improvements in this this new version.

  • It is more accurate.  I have replaced the Stirling approximations of the factorial function with exact factorial calculations.
  • It is faster.  Several coding changes were made as I re-wrote this from Perl in Python.  Calculations for factorial and binomial coeffecients are cached.
  • It is more reliable.  Google's App Engine has better uptime performance than the Imp Lair servers.
  • It is easier to use.  Calculations have gone from three steps down to two.

Give it a try!  http://deckulator.appspot.com/