That's right, we're going to discuss the intersection of two sets: Mathematics and Incredibly Nerdy Card Games. Dominion is a "deck-building" game that's all about making the best use of the (normally) very small amount of information you have. Unlike a lot of common card games, each player has his own deck of cards for which he is (almost) completely in control of the cards going into his deck throughout the game. The trick is to composing your deck such that your chances of drawing useful hands frequently are high. As I soon discovered after starting to determine what some of these probabilities come out to be, they get difficult to calculate. Very quickly. In fact, a large chunk of the research I've read on the topic (yes, I'm not the only dork interested in this topic. See?) has been based on not calculating the exact probabilities, but approximating it using a couple thousand trials in a simulator (Geronimoo's and Dominate seem to be the most popular). While there is certainly a use for it, anyone who knows me will tell you that I'm something of a perfectionist, so approximations will not due, when an exact answer can be found!! None-the-less, it's a huge topic, so this will be the first of likely many posts about this topic.
In a brief introduction to the rules relevant for this post: you begin your turn by drawing 5 cards off the top of your "draw pile" (ie- your shuffled deck of cards you haven't used yet). [As a quick disclaimer so I don't piss off the experienced Dominion players: there's some nuances here. For instance, technically, your hand is drawn at the end of the previous turn, and there are circumstances in which you may have more or fewer than 5 cards, among others. However, for the purposes of our discussion, this generalized rule will do for now, as I'm only interested in discussing basic, initial hand probabilities at first.] Technicalities aside, you start your turn with the ability to use a single action (that is, play a card that says "Action" on it...), perform it's text, and make a single card purchase using $'s gained through action uses and the remaining "Treasure" (money) cards in your hand. Generally, the "good" cards are more expensive, but it really depends on the "Kingdom" (the set of 10 differently-named cards available for purchase. This is usually chosen at random when setting up the game). Finally, whenever you can't draw a new card when you're supposed to, shuffle your discard pile and it becomes your new draw pile. So, it's very useful to know information such as "What is the probability that I draw enough money to purchase some card I'm interested in?"
Luckily, there has been plenty of research in probabilities throughout the centuries, in particular, solutions to the famous Urn Problem. From this, Dominion probabilities can be modeled using a Hypergeometric Distribution, that is, any probabilistic distribution (ie- you drawing a hand of 5 Dominion cards) that has the following probability mass function (ie- the likelihood of you drawing exactly k cards of a particular desired type):
So, let's jump right in and put some numbers to it: let's consider the probability of drawing all 5 Coppers (Treasure cards you use as money, $1 each) on your first turn of the game! By the official rules, you start the game with 7 Coppers and 3 Estates (Victory point cards that don't do anything until the end of the game, at which point you use them to win), so K=7, k=5, N=10, and n=5. Because these calculations can be somewhat tedious when performing many times (and because I'm lazy), have some code:
(FYI- I used a more computationally efficient algorithm for the binomial coefficient, so don't freak out when you review the below code and realize it's not exactly what's defined above. It's pretty basic combinatoric algebra, so I leave it as an exercise to the reader... I've always wanted to say that... though, you'll probably just look it up on Wikipedia, especially since I supplied the link above... *disapproving glare* ):
/// <summary>
/// Calculates the Binomial Coeffiencient, given two integers.
/// </summary>
/// <param name="n" >The count of the total drawing pool</param>
/// <param name="k" >The count of the subset you are selecting</param>
public static double CalculateBinomialCoefficient(int n, int k)
{
double result = 1;
for (int i = 1; i <= k; i++)
{
result *= (double)(n - k + i) / i; // must cast numerator as double to avoid integer division error
}
return result;
}
/// <summary>
/// Calculates the value of a probability mass function for a hypergeometirc distribution for a particular number of outcomes k
/// </summary>
/// <param name="N" >The count of the total population pool</param>
/// <param name="K" >The count of success states in the total population pool</param>
/// <param name="n" >The number of draws</param>
/// <param name="k" >The desired number of successes</param>
public static double CalculatePMF_HypergeometicricDistribution(int N, int K, int n, int k)
{
return (CalculateBinomialCoefficient(K, k) * CalculateBinomialCoefficient(N - K, n - k)) / CalculateBinomialCoefficient(N, n);
}
Crank'n this out reveals the probability of drawing the awesome starting hand of 5 Coppers is 8.333 %.
Fun Fact: notice that the probability of drawing exactly 2 Coppers is exactly the same, just as drawing 3 or 4 Coppers on your first turn is 41.667 % in either case. Between your first and second turns, you use each of your 10 starting cards exactly once- there is zero randomness to your second hand. Since your first and second turns are played without any possible interaction between players (other than plotting and psychological triggering based on what other players bought...), the first and second hands, can be thought of interchangeably. In some regards, it might be better to know that your probability of getting the 2/5 Copper split between your first and second hands is 8.333 + 8.333 = 16.667%, while getting the 3/4 split is 83.33%.
Knowing the probability of drawing EXACTLY a specific number of the desired card is useful, but you might also want the probability of drawing AT LEAST a specific number of the desired card. Suppose you're set on buying a particular $3 card with your starting hand; what's the probability you can do it on the first turn? We'd need to find the probability of drawing exactly 3, 4, or 5 Coppers. So add 'em up! (again, I'm lazy, so have some code):
private const int HAND_SIZE = 5;
/// <summary>
/// Returns the probability of drawing AT LEAST the MinimumCount copies of the desired card
/// </summary>
/// <param name="CardType" >Name of the card to calculate the probability for</param>
/// <param name="MinimumCount" >Minimum number of cards of the given type desired</param>
/// <param name="Deck" >The current deck of cards</param>
public static double CalculateProbOfDrawingAtLeastXCards(string CardType, int MinimumCount, DominionDeck Deck)
{
double probabilitySum = 0;
for (int k = MinimumCount; k <= HAND_SIZE; k++)
{
probabilitySum += CalculatePMF_HypergeometicricDistribution(Deck.DeckSize, Deck.CardCount[CardType], HAND_SIZE, k);
}
return probabilitySum;
}
As you can see, I've added a DominionDeck class to the project, defined below... (perhaps I'll get it up to BitBucket or make a mobile version so you can run your statistics in the middle of your next game...)
public class DominionDeck
{
public Dictionary<string int> CardCount { get; set; }
public int DeckSize
{
get
{
int total = 0;
foreach (string entry in CardCount.Keys)
total += CardCount[entry];
return total;
}
}
public DominionDeck()
{
CardCount = new Dictionary<string int>();
}
public void Initialize()
{
CardCount.Add("Copper", 7);
CardCount.Add("Estate", 3);
}
public void AddCard(string CardName)
{
if (CardCount.ContainsKey(CardName))
CardCount[CardName]++;
else
CardCount.Add(CardName, 1);
}
}
Crunching these numbers gives you a 91.667 % probability of drawing AT LEAST 3 Coppers in your first hand.
Of course you aren't restricted to using these probability calculations on only the draw hand... you can run the same equations to figure out later in the game what your probability of drawing a hand full of Victory cards and Curses? (Curses are like Victory cards, only they are worth -1 point at the end), in other words, a useless hand. Well, if your first 2 purchases of the game were both Estates, you have a slim 0.126 % chance of drawing a useless hand on your third turn (but you can reconcile yourself knowing all that's left in your deck is Coppers, leaving you with a 100 % probability of drawing 5 Coppers your next turn). Though, what's more likely to happen than drawing all Estates is drawing a hand with at least one Estate (AKA: a hand with at least one useless card, reducing your buying power to a maximum of $4); it's 97.348 % certain to happen on your third turn...
...Which brings me to the next topic I was going to mention: Deck Density. Buying up Victory cards is how you ultimately win the game, but they are (generally speaking) useless during the game, and act to fill up your hand with useless cards. As you saw with the last example, buying up victory cards early will very easily reduce the availability of useful cards like Actions and Treasures. Suppose: instead of purchasing Estates with your first two hands, you purchase Silvers (you'll need the 3/4 Copper split discussed earlier to accomplish this, as Silver costs $3 to buy, but don't worry, you're 83.33% certain this will happen; Doctors perform procedures on worse chances than that! Statistics really puts things in perspective, doesn't it? I really hope you're still able to place your hopes and dreams on numbers after reading my blog... anyway, I'm getting off topic...). You now have a deck with 9 Treasures and 3 Estates in it. Hey, that's a 15.909 % chance of drawing a hand full of Treasure cards- almost double the chances of opening with 5 Coppers! Also, that's just your probability of drawing 5 Treasure cards; Silvers are worth more than Coppers when buying stuff! In case you're curious, this scenario is the beginnings of what's referred to as a pure "Big Money" strategy. Honestly, there is enough number crunching in analyzing just your chances of drawing a certain amount of "purchasing power" (monies) to warrant it's own post (the likely focus of the future Part 2), so I'll hold off this discussion till another time, See the bullet points below for a preview.
So that's the basics (or at least what I'm comfortable publishing tonight). If you want to think about the same things I am currently thinking about (probably a scary prospect, in general), consider:
- There are cards such as Silver and Gold which are cards just like Copper, only worth $2 and $3, respectively. What's the probability of drawing at least $X? we'll need to consider all the probabilities of drawing Treasure cards totaling (at least) X.
- There are Action cards that can be played which cause you to immediately draw more cards. What's the probability that you get such an action card and draw more of your desired card, up to your desired count, during these subsequent draws?
- There are Action cards that can be played which cause you to be able to play more action cards. What's the probability that chaining the previous bullet point causes you to draw up to your desired count of desired cards?
- There are Action cards that give you money to spend in addition to some action text like the previous two bullet points.
- Whenever you can't draw anymore, you shuffle your discard pile, and draw from that newly created draw pile. How does that change the probability, if you have to shuffle during any of the previous bullet points?
Just some tasty math noms for thought...
