Probability for Slay the Spire fanatics

I’m a huge fan of Slay the Spire and I wanted to share a small probability trick I’ve learned that has helped me improve my game by calculating the odds of “greedy” plays succeeding. This trick will likely also benefit other games based on cards or probability, too, but the examples from this post will be specific to Slay the Spire.

The general problem I was trying to solve is:

I have a deck containing N desirable cards out of D total cards. If I draw H cards from that deck, what is the chance that I draw (exactly / at least / at most) M desirable cards?

This sort of question comes up often in card games, including complex ones (like Slay the Spire) or simpler ones (like poker). Here are some concrete examples of how this relates to Slay the Spire:

• “Next turn I draw 5 cards. What is the likelihood that I draw at least 3 Strikes if there are 7 cards left in the deck, 4 of which are Strikes”.

  (Answer: 5 / 7 ≈ 71% chance)

• “One Neow bonus lets me lose 7 max HP to select from 1 of 3 random rare cards. Right now I’m only interested in 6 of the 17 possible rare cards, so what is the chance that I random at least 1 of those 6?”

  (Answer: 103 / 136 ≈ 76% chance)

The nice thing about Slay the Spire is that it’s a turn-based single-player game, so (unlike poker) you can take all the time you want when deciding your turn and nobody will rush you to hurry up. This means that I can safely geek out on these sorts of probability calculations to increase my likelihood of winning.

In this post I’ll first present the solution to the above probability question (both as a mathematical formula and as code) and then explain why the formula works.

The formula

Before presenting the solution to the above problem, I’d first like to reframe the problem using more precise set notation to avoid ambiguity:

Define U to be the universal set of all cards in the deck and then define two (potentially overlapping) subsets of those cards:

• A: The set of cards that are drawn
• B: The set of cards that are desirable

Let’s also define ¬ to mean set complement, such that:

• ¬A means the set of cards that are not drawn
• ¬B means the set of cards that are undesirable

Finally, we’ll use ∩ to denote set intersection, which we will use to define four non-overlapping (i.e. disjoint) sets:

           ¬B │       B
    ┌─────────┼─────────┐
 ¬A │ ¬A ∩ ¬B │ ¬A ∩  B │
────┼─────────┼─────────┤
  A │  A ∩ ¬B │  A ∩ ¬B │
    └─────────┴─────────┘

… where:

• A ∩ B means the set of cards that are drawn and desirable
• A ∩ ¬B means the set of cards that are drawn, but undesirable
• ¬A ∩ B means the set of cards that are desirable, but not drawn
• ¬A ∩ ¬B means the set of cards that are neither desirable nor drawn

Then the problem becomes:

If the size of the sets A and B are fixed, what is the probability that their overlap (i.e. the set A ∩ B) has a given size?

I use this presentation to highlight that:

• The problem isn’t really specific to cards. It will work for arbitrary sets
• The problem isn’t specific to drawing cards or desirable cards. It works for any two subsets of cards
• The problem is symmetric with respect to A and B. If we swap the size of the two subsets of cards we expect to get the same answer

Using |S| to denote the size (i.e. cardinality) of a set S and using ! to denote factorial, then the probability of two subsets of fixed sizes overlapping by a given size is:

                |A|! × |¬A|! × |B|! × |¬B|!
p = ────────────────────────────────────────────────────
    |A ∩ B|! × |A ∩ ¬B|! × |¬A ∩ B|! × |¬A ∩ ¬B|! × |U|!

With this solution in hand, we can solve our original problem by just renaming the variables:

I have a deck containing |B| desirable cards out of |U| total cards. If I draw |A| cards from that deck, what is the chance that I draw (exactly / at least / at most) |A ∩ B| desirable cards?

We already have the solution for the case where we draw exactly |A ∩ B| desirable cards. From that we can compute the solutions for drawing at most or at least |A ∩ B| desirable cards.

The code

If you still don’t follow along, I translate the above solution into Haskell code in this section.

Note that even though the previous formula depends on the sizes of nine sets:

• |U|
• |A|
• |¬A|
• |B|
• |¬B|
• |A ∩ B|
• |A ∩ ¬B|
• |¬A ∩ B|
• |¬A ∩ ¬B|

… there are really only four degrees of freedom, because the size of the following four disjoint sets:

• |A ∩ B|
• |A ∩ ¬B|
• |¬A ∩ B|
• |¬A ∩ ¬B|

… uniquely determine the sizes of the other sets, because:

| A| = | A ∩  B| + | A ∩ ¬B|
|¬A| = |¬A ∩  B| + |¬A ∩ ¬B|
| B| = | A ∩  B| + |¬A ∩  B|
|¬B| = | A ∩ ¬B| + |¬A ∩ ¬B|
| U| = | A ∩  B| + | A ∩ ¬B| + |¬A ∩  B| + |¬A ∩ ¬B|

… so each function in our API will only take four function arguments, corresponding to the size of those four disjoint sets. There are other ways we could define the API that use a different four degrees of freedom, but I find this interface to be the simplest and most symmetric.

module Probability where

import Numeric.Natural (Natural)

-- Use exact Rational arithmetic by default instead of floating point arithmetic
default (Natural, Rational)

-- Obligatory: http://www.willamette.edu/~fruehr/haskell/evolution.html?
factorial :: (Enum n, Num n) => n -> n
factorial n = product [1..n]

{-| The probability that two sets of sizes @|A|@ and @|B|@ overlap by a set of
    exactly size @|A ∩ B|@

    prop> exactly 1 0 0 a === 1 % (a + 1)
    prop> exactly a b 0 0 === 1
    prop> exactly a 0 b 0 === 1
    prop> exactly a b c d === exactly a c b d
-}
exactly
    :: (Enum n, Fractional n)
    => Natural
    -- ^ The size of @|A ∩ B|@
    -> Natural
    -- ^ The size of @|A ∩ ¬B|@
    -> Natural
    -- ^ The size of @|¬A ∩ B|@
    -> Natural
    -- ^ The size of @|¬A ∩ ¬B|@
    -> n
exactly _AB _AnotB _BnotA notAB =
    fromIntegral numerator / fromIntegral denominator
  where
    _A = _AB + _AnotB
    _B = _AB + _BnotA

    notB = _AnotB + notAB
    notA = _BnotA + notAB

    _U = _AB + _AnotB + _BnotA + notAB

    numerator = product (map factorial [ _A, notA, _B, notB ])

    denominator = product (map factorial [ _AB, _AnotB, _BnotA, notAB, _U ])

{-| The probability that two sets of sizes @|A|@ and @|B|@ overlap by a set of
    at least size @|A ∩ B|@

    prop> atLeast 0 a b c === 1
    prop> atLeast a b c d === atMost a c b d
-}
atLeast
    :: (Enum n, Fractional n)
    => Natural
    -- ^ The minimum size of @|A ∩ B|@
    -> Natural
    -- ^ The maximum size of @|A ∩ ¬B|@
    -> Natural
    -- ^ The maximum size of @|¬A ∩ B|@
    -> Natural
    -- ^ The minimum size of @|¬A ∩ ¬B|@
    -> n
atLeast _AB _AnotB _BnotA notAB = sum (map overshootBy [0..(min _AnotB _BnotA)])
  where
    overshootBy x = exactly (_AB + x) (_AnotB - x) (_BnotA - x) (notAB + x)

{-| The probability that two sets of sizes @|A|@ and @|B|@ overlap by a set of
    at most size @|A ∩ B|@

    prop> atMost 0 a b c === exactly 0 a b c
    prop> atMost a 0 b c === 1
    prop> atMost a b 0 c === 1
    prop> atMost a b c d === atMost a c b d
    prop> atMost a b c d + atLeast a b c d === 1 + exactly a b c d
-}
atMost
    :: (Enum n, Fractional n)
    => Natural
    -- ^ The maximum size of @|A ∩ B|@
    -> Natural
    -- ^ The minimum size of @|A ∩ ¬B|@
    -> Natural
    -- ^ The minimum size of @|¬A ∩ B|@
    -> Natural
    -- ^ The maximum size of @|¬A ∩ ¬B|@
    -> n
atMost _AB _AnotB _BnotA notAB = sum (map undershootBy [0..(min _AB notAB)])
  where
    undershootBy x = exactly (_AB - x) (_AnotB + x) (_BnotA + x) (notAB - x)

Exercise: If you don’t use Haskell, try to port the above functions to your favorite programming language.

Examples

Let’s test drive the above utilities on the example scenarios from Slay the Spire.

• “Next turn I draw 5 cards. What is the likelihood that I draw at least 3 Strikes if there are 7 cards left in the deck, 4 of which are Strikes”.

  Here, we will be using the atLeast function with the following input sizes for each disjoint set:

  • | A ∩ B| = 3 - We wish to draw at least 3 Strike cards
  • | A ∩ ¬B| = 2 - We wish to draw at most 2 non-Strike cards
  • |¬A ∩ B| = 1 - We wish to leave at most 1 Strike card in the deck
  • |¬A ∩ ¬B| = 1 - We wish to leave at least 1 non-Strike card in the deck

  … which gives us a 5 in 7 chance:

  >>> atLeast 3 2 1 1
  5 % 7

  Exercise: Use the atMost function to compute the chance of falling short by drawing at most 2 Strikes.

• “One Neow bonus lets me lose 7 max HP to select from 1 of 3 random rare cards. Right now I’m only interested in 6 of the 17 possible rare cards, so what is the chance that I random at least 1 of those 6?”

  This will also use the atLeast function with the following input sizes for each disjoint set:

  • | A ∩ B| = 1 - We wish to draw at least 1 desired rare card
  • | A ∩ ¬B| = 2 - We wish to draw at most 2 undesirable rare cards
  • |¬A ∩ B| = 5 - We wish to leave at most 5 desirable cards in the pool
  • |¬A ∩ ¬B| = 9 - We wish to leave at least 9 undesirable cards in the pool

  … which gives us a 103 in 136 chance:

  >>> atLeast 1 2 5 9
  103 % 136

  Exercise: Use the exactly function to compute the chance of randoming 0 desirable cards.

Explanation

This section provides a semi-rigorous explanation of why the formula works, although probably not rigorous enough to be called a proof.

The probability of drawing a correct hand is:

    {The number of correct hands}
p = ──────────────────────────────
    {The number of possible hands}

The number of possible hands is the number of ways that we can draw a hand of size |A| (without replacement) from a pool of |U| cards (our deck):

{The number of possible hands} = |U| choose |A|

Similarly, the number of correct hands is the product of:

• the number of ways to draw |A ∩ B| desirable cards from a pool of |B| desirable cards and
• the number of ways to draw |A ∩ ¬B| undesirable cards from a pool of |¬B| undesirable cards

{The number of correct hands} = (|B| choose |A ∩ B|) × (|¬B| choose |A ∩ ¬B|)

Putting that together gives:

    (|B| choose |A ∩ B|) × (|¬B| choose |A ∩ ¬B|)
p = ─────────────────────────────────────────────
                   |U| choose |A|

Then we can use the “n choose k” formula for computing the number of ways to select n cards from a pool of k cards without replacement, which gives us:

            |B|!                   |¬B|!
    ──────────────────── × ──────────────────────
    |A ∩ B|! × |¬A ∩ B|!   |A ∩ ¬B|! × |¬A ∩ ¬B|!
p = ─────────────────────────────────────────────
                        |U|!
                    ───────────
                    |A|! × |¬A|

… and then if we simplify that we get our original formula:

                |A|! × |¬A|! × |B|! × |¬B|!
p = ────────────────────────────────────────────────────
    |A ∩ B|! × |A ∩ ¬B|! × |¬A ∩ B|! × |¬A ∩ ¬B|! × |U|!

Conclusion

Unfortunately, this formula is quite difficult to do in one’s head so I usually load these utility functions into a Haskell REPL to do the math on tricky turns. I haven’t yet figured out an easy heuristic for getting a quick and approximate answer for this sort of probability calculation.

However, if you’re willing to take the time to compute the odds this sort of calculation can quickly add up to improving your odds of winning a Slay the Spire run. I often use this trick to compute the expectation value of greedy plays which can save quite a bit of health or potions over the course of a run.