How to conquer the galaxy (probably)

I’ve recently gotten very into Leder Games/Cole Wherle’s newest board game, Arcs. It’s a scrappy, clever game about power struggles within a failing interstellar empire, and it’s chock full of deliciously thorny mechanics that lead to interesting decisionmaking.

One of these mechanics is its system of building dice pools. Whenever you send your ships into combat in Arcs, you assemble a dice pool of one die per ship, and resolve the combat in a single roll. What makes this such an interesting bit of decisionmaking is the different types of dice you can pull from for your pool.

Each die has a different utility and risk profile: blue Skirmish dice are basically a coin flip for whether you’ll score hits against your enemy, and carry no risk of harming your own ships. The red Assault dice can do considerably more damage to the enemy, but with a higher chance of blowing up your fleet with self-hits and intercepts. And the orange Raid dice carry the most risk of self-hits, as well as chances of blowing up enemy buildings (which can be good or bad), but importantly are the only dice which let you roll keys, the game’s way of stealing goodies from your opponent.

Building your dice pool is an exercise in risk management: how many of your own ships can you afford to blow up to get what you want? With the exception of blue Skirmish dice, the symbols are unevenly allocated over the faces of each die, making for some dramatic dice rolls. For future reference, here’s the layout of each die from the game’s manual:

Now to be clear, I don’t think Cole Wherle intended players to perform exacting calculations of the odds for every dice pool. The gist of the mechanic is that one die is safe, one is risky, and one is real risky, so plan accordingly.

But as a fan of recreational math, I got to wondering: given any assortment of Skirmish, Assault, and Raid dice, what are the odds of rolling any given outcome? For example, suppose I roll 2 Skirmish dice and 2 Assault die, what are the odds of me rolling hits vs self-hits? And as it turns out, what I thought would be a fairly dreadful brute-force statistics problem actually led to some elegant math in unexpected places.

To whet your appetite, here’s a dice pool calculator I wrote using the approach we’re about to cover. Don’t worry if you don’t know Arcs or what a “generating function” is, hopefully that will all make sense by the end of this post.

Dice pool:

Skirmish SS

Assault AA

Raid

Generating function:

Symbols to compare:

Symbol 1 HitSelf HitBuilding HitInterceptKey

Symbol 2 HitSelf HitBuilding HitInterceptKey

A simpler case

To start with, let’s analyze the case of rolling a pool of $n$ standard six-sided dice and adding up the values. We can consider each die to be a discrete random variable, which means something whose value is randomly determined from a discrete set of values. In this case, those values are ${1, 2, 3, 4, 5, 6}$, i.e. the number of pips on each die face. Let’s call that random variable $D$ for die.

Next, we’d try to model a single roll of this dice pool, which is just the sum of all the random die variables. Since we have $n$ dice, let’s call the roll $R_n$, and thus $R_n = D_1 + D_2 + ... + D_n$.

Now, we can finally ask a question like “when rolling 4 dice, what are the odds of rolling a 7?” Or, in a more mathy parlance, what is the value of $R_n$’s probability mass function (PMF) $P(R_n = 7)$? The problem, of course, is we don’t know what the PMF is yet, so we can’t evaluate it at anything!

Probability mass functions are (in my opinion) terribly named due to a tortured metaphor of probability “densities”, but conceptually they’re actually really simple: they’re just functions which return the probability of getting a value for a given discrete random variable. For example, for a single die, the function is just $\dfrac{1}{6}$ for all values.

There’s a few ways we can go about calculating the PMF, and Grant Sanderson (aka 3Blue1Brown) has a fantastic video on convolutions which demonstrates some of the traditional approaches. But as I was researching the subject matter, I discovered another way that’s both stranger and more elegant.

Generating functions: a prelude

To spoil the ending a bit, we’ll be using things called generating functions to analyze these dice pool distributions. But I have to admit, when I first learned this approach, it felt extremely bizarre. Generating functions can often seem like total non-sequiters in their applications, and if you’ve never dealt with them before, my goal in this post is to motivate their usage from first principles, and explain why they’re a great fit for this kind of problem. But to quote another Grant Sanderson video:

There’s a time in your life before you understand generating functions, and a time after, and I can’t think of anything that connects them other than a leap of faith.

Back to our roll of $n$ dice and its result, $R_n$. To make things a bit simpler, let’s consider the case of two dice ($R_2$), and write down all of 36 possible sums of the two rolls:

As expected, $2$ and $12$ occur just once to account for the unique rolls (1, 1) and (6, 6) that produce them, and $7$ is the most frequent outcome. Since each individual cell of this chart has a $\dfrac{1}{6} * \dfrac{1}{6} = \dfrac{1}{36}$ chance of occurring, we can simply multiply the number of occurrence of each value by $\dfrac{1}{36}$ to get the probability of that outcome:

And hey, just like that we’ve just built a PMF! To calculate the probability of some roll, just look up the outcome and read out its corresponding probability.

Before we proceed, let’s take a step back and generalize the steps we took here. For ease of reference, I’m also going to give each step a name:

1. Enumeration: Given the faces on each die, we enumerated the collection of all possible rolls
2. Combination: For each possible combination of rolls $D_1 = a$ and $D_2 = b$:
   1. We calculated the outcome’s value: $a + b$
   2. We calculated the outcome’s probability: $P(D_1 = a) * P(D_2 = b)$ (which in our example was just $\dfrac{1}{6} * \dfrac{1}{6}$, but worth writing out for later)
3. Consolidation: We added together the probabilities of all rolls with equivalent outcomes

Now for the leap of faith. Suppose we wanted a nice, compact, closed-form equation that performs each of these three steps. Luckily, that’s exactly what generating functions allow us to do, though it’s not so clear from the outset how they manage to do it.

Discovering our generating function

Instead of diving into generating functions head-first, let’s approach them a bit more cautiously, and see if we can stumble across one just by trying to design a process that reproduces the 3 above steps: Enumeration, Combination, and Consolidation. For the rest of this section, we’ll be considering the rolls of two standard six-sided dice, $D_1$ and $D_2$.

First off, Enumeration. What we’re basically looking for is something called a Cartesian product of both die’s set of face values. This would give us all possible pairs of faces from the two dice. One idea that might occur to us is that regular old multiplication can do something like this, which many of us learned as FOIL (First, Out, Inner, Last):

So if we could somehow encode each die as a sum of somethings representing each face, then multiplying those two sums together would give us a giant FOIL’d sum representing every combination of dice faces. For example if we say $D_1$’s somethings are $D_1 = a_1 + a_2 + a_3 + a_4 + a_5 + a_6$, and $D_2$’s are $D_2 = b_1 + b_2 + b_3 + b_4 + b_5 + b_6$, then:

would give us all combinations of $a$’s and $b$‘s. But simply setting those somethings to be the face values (e.g. $D_1 = 1 + 2 + 3 + ...$) clearly wouldn’t work, since we’d just up with the product of two numbers. What else might work?

Well, whatever those somethings are, we know we’re going to be multiplying them together, so let’s recall what we want from our Combination step: the product of two faces should somehow a) add the face values, and b) multiply their respective probabilities. At first, this might seem like something that could only be done in two separate operations. But suppose we encode two outcomes, say $D_1 = 2$ and $D_2 = 6$, like this:

What we’ve done here is take the probability of rolling each outcome ($\dfrac{1}{6}$), and set it as the coefficient of a single-term polynomial (a.k.a. a monomial) whose degree is equal to the face’s value. Why would we possibly do that? Let’s see what happens when we multiply them together:

Sure enough, we arrive at a new monomial whose coefficient is the probability of the two-dice outcome, and whose degree is equal to the sum of the two rolls. We’ve taken advantage of the unique property that exponents are added when their bases are multiplied to arrive at Combination’s second property, while also multiplying the probability coefficients to get the first property. Pretty convenient!

For the final step, Consolidation, we’d like to add up the probabilities of all outcomes with equivalent values. Luckily enough, our monomial-based encoding scheme handles this for us automatically, since any outcomes with matching degrees will add together naturally:

Now we can start putting the pieces together. Since all faces $1$ through $6$ of a standard six-sided die have an equal chance of being rolled, it can be described by the polynomial:

This is called a generating function, and although it seems odd to bring this seemingly unrelated polynomial into our problem, remember that we’re just using it to associate probabilities to outcomes. And since, as we’ve seen, multiplying polynomials reproduces our 3 steps, if we multiply $f(x)$ by itself we should arrive at a generating function that encodes the probability distribution of rolling two dice:

If we match each exponent-value with the outcome/probability table above, we’ll find that all of the coefficients indeed match the expected probabilities. Moreover, by multiplying our generating function together repeatedly, we can arrive at a compact, closed-form description for an arbitrarily sized dice pool. And so, at last, we can derive the values of the PMF for $R_n$ simply by expanding $f^n(x)$.

An interlude on $x$

“Cool functions”, I can hear you saying, “but what are they functions of?” And you’re right to be leery. If the coefficients of our function represent probabilities, and the exponents represent dice faces, what meaning does $x$ have?

Well in short, it’s just a symbol. When using generating functions to represent our PMF, we’re not really evaluating our $f(x)$ for any values of $x$. As Herbert Wilf said in the excellent generatingfunctionology, “a generating function is a clothesline on which we hang up a sequence of numbers for display”. The variable $x$ is merely the clothespin holding up the coefficients that we’re interested in, and isn’t necessarily important.

That said, you can definitely treat these critters like real functions and evaulate them at various points to arrive at some really neat insights into your subject. As we’ll see in the next post, there’s some clever evaluation we can do to cheaply pull out our coefficients. A simpler example of this would be to evaluate $f(1)$, which for our generating function above would simply equal the sum of the coefficients (a.k.a. probabilities). And since all probabilities in a distribution must add to equal $1$, we know that $f(1) = 1$.

A more interesting example of this would be $f(-1)$. What do you think this might do? Well, $(-1)^n$ for even powers of $n$ is just $1$, and for odd powers it’s $-1$, so we end up with:

In other words, it subtracts the probability of rolling an odd face from the probability of rolling an even face. In our case, this obviously cancels out to 0, since a 6 sided die has an equal number of even and odd faces. But it also tells us that rolling any number of standard six-sided dice and adding the result has an equal chance of giving an even or odd number, since:

For more on this, be sure to check out Grant Sanderson’s video on generating functions for solving a tough puzzle that I referenced above.

Non-standard dice

So what if we have dice with different numbers of sides, or different allocations of pips? No problem, generating functions got your back. Simply follow the rules of generating functions for PMFs:

1. The sum of all coefficients must equal 1
2. No coefficients can be negative

With that, let’s try creating the generating function $g(x)$ for a 4 sided die with faces ${0, 3, 7, 7}$:

Since we only have 4 sides, we adjust the coefficients to be $\dfrac{1}{4}$, and since one side has 0 pips, we straightforwardly enough assign its probability to $x^0$, a.k.a. 1. And as you might hope, you can simply multiply $g(x)$ with our friend $f(x)$ from above to get the generating function for a dice pool with this die and a standard 6 sided die:

Arcs!

We just need one more tool before tackling the dice in Arcs: a way of handling multiple types of pips. In Arcs, each dice can have any number of 5 different symbols. I’ll assign each of them a letter, which will be useful for us going forward:

Arcs dice symbols

Symbol	Name	Letter
	Hit	$h$
	Building hit	$b$
	Self-hit	$s$
	Intecept	$n$
	Key	$k$

And for ease of reference, here are the layouts of each die:

How can we represent these? One possiblity might be to create separate generating functions for each type of symbol appearing on each die. So the Assault die would have a hit function, a self-hit function, and an intercept function. But this approach incorrectly treats the different pip types as independent from one another, and would fail to account for the fact that the 1 intercept symbol on Assault dice can only ever be paired with the single hit symbol.

Instead, we make our generating functions multivariate, i.e. they are functions of more than one variable. In this model, each type of die gets its own function on five variables: $A(h, s, b, n, k)$ for Assault dice, $S(h, s, b, n, k)$ for Skirmish, and $R(h, s, b, n, k)$ for Raid:

Note that constant values represent empty faces, and that the probabilities of common terms have been summed together. For brevity’s sake, I’ll refer to these functions by just their capital letters from here on out.

And now we finally have a way to compute the general PMF of any given roll for an arbitrary Arcs dice pool: for a pool of $x$ Assault dice, $y$ Skirmish dice, and $z$ Raid dice, we compute $A^xS^yR^z$, and then lookup the coefficient of a given roll.

Let’s try a simple example. For a pool with two Assault dice and one Skirmish die, we’d multiply and expand $A^2S^1$:

As you can see, our (checks notes) “simple” example has give us a pretty unweildy polynomial. But, if you wanted, you could add up all of the coefficients and verify they equal $1$ (I certainly did). And although it’s a bit painful to look at, we can fairly easily notice a few things:

• There’s a $\dfrac{1}{72}$ chance of rolling nothing
• All other $\dfrac{71}{72}$ possible outcomes include at least one Hit
• The most likely roll is 3 Hits, 2 Self-hits with probability $\dfrac{8}{72}$

We can also draw more interesting statistics from this by combing through the terms. For example, the question “what are the chances of rolling more than 3 hits and up to 1 self-hit” is just a matter of adding up the probabilities for every term with a factor of $h^ns^m$ where $n \geq 3$ and $m \leq 1$.

But as you can see, expanding out and interpreting these polynomials is pretty unweidly, both practically and computationally. Polynomial multiplication is a fairly intensive process, and sifting through the combinatorial explosion of monomials to sum up the coefficients is kind of a nightmare to program. Luckily, as I hinted before, there’s a clever trick we can use to pull out our coefficients in a more efficient and elegant manner. Stay tuned for the next post to learn how!