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 $$