Simplifying Combat

Many "dudes on a map'' games, involve combat mini-games that mostly consist of taking a break from the normal game, and taking turns rolling lots of dice, losing some units, and repeating until only one player has units left. Sometimes you may be able to target specific units (e.g. Buck Rogers), play a card that influences the dice rolling that round (e.g. Star Wars: Rebellion), or decide whether to retreat or give up (e.g. War of the Ring).

This is similar to combat in many RPGs, or skill challenges in D&D 4th edition.

However, some games (e.g. Bottom of the 9th) don't offer any choices in between rounds of rolling dice. My contention is that such a game is likely bad design, simply based on the math. That is, you could replace any decision-free process with a single-step process with equivalent probabilities. Even for games with choices in between rounds of combat, the value of having such a choice should outweigh the cost of game time and complexity.

Let's look at a theoretical game. Suppose in this game when you move a number of units into an enemy territory you engage in rounds of combat. Each round you roll one die for each attacker and destroy one defender with probability $p$. Similarly, your opponent rolls one die for each defender and destroys one attacker with the same probability $p$. Each round is simultaneous; that is, remove destroyed units at the end of each round. If only one player has units at the end of a round, then stop. Suppose you start with $A$ attackers, and your opponent starts with $D$ defenders.

The combat will end with either the attacker remaining with 1 to $A$ units, the defender will remain with 1 to $D$ units, or both armies will be destroyed. If we could compute the probability of each of these results, then we could simply use the result instead of all the dice rolling.

What's tricky is that there's a probability of $(1-p)^{(A+D)}$ that no units are destroyed in a round. This comes from all $A+D$ units missing, which occurs with probability $1-p$, since $P(\text{hit}) + P(\text{miss}) = 1$. That means that the combat could go on for a long time. In fact, it's not guaranteed to ever end. So, while it's relatively easy to show the probability distribution of the state of combat after $r$ rounds, the end of the combat is not so clear.

Well, let's start by looking at what happens in round $r$ and see what the distribution is first. Let's denote $a_r$ and $d_r$ as the number of attackers and defenders, respectively, remaining at the end of round $r$. Let's also just say that $a_0 = A$ and $d_0 = D$.

Actually, let's look at the simple case of one attacking unit and one defending unit. After the first round of combat, there are four possible outcomes: both units are destroyed, the defender is destroyed, the attacker is destroyer, or neither are destroyed. In the first three outcomes the combat ends. In the last, another round commences with the same possible outcomes and the same probabilities, since the combat starts in the same state. The probabilities are,

\begin{align} P(\text{both destroyed in first round}) &= p^2 \\ P(\text{attacker destroyed in first round}) &= p\cdot (1-p) \\ P(\text{defender destroyed in first round}) &= p\cdot (1-p) \\ P(\text{neither destroyed in first round}) &= (1-p)^2 . \end{align}

Then, the probability of what happens in the second round is the same as the first, multiplied by the probability that you get to the second round.

\begin{align} P(\text{both destroyed in second round}) &= p^2\cdot (1-p)^2 \\ P(\text{attacker destroyed in second round}) &= p\cdot (1-p)^3 \\ P(\text{defender destroyed in second round}) &= p\cdot (1-p)^3 \\ P(\text{neither destroyed in second round}) &= (1-p)^4 . \end{align}

The probability that the combat ends with both destroyed is equal to the probability that it happens in the first round, plus the probability that it happens in the second round, and so on.

\begin{align} &P(\text{both destroyed at end of combat}) = \sum_{r=1}^\infty P(\text{both destroyed in round } r)\\ &= \sum_{r=1}^\infty P(\text{both destroyed in a round}) \cdot P(\text{get to round } r)\\ &= \sum_{r=1}^\infty p^2 \cdot (1-p)^{2(r-1)} \\ &= p^2 \sum_{r=1}^\infty \cdot \left((1-p)^2\right)^{r-1} \\ &= p^2 \sum_{r=0}^\infty \cdot \left((1-p)^2\right)^r \end{align}

Recall that (Honestly, right now I'm just relying on Wikipedia, but I'm pretty sure I have derived or will derive this.)

\begin{align} \sum_{i=0}^\infty a^i &= \frac{1}{1-a} \end{align}

Thus,

\begin{align} P(\text{both destroyed at end of combat}) &= p^2 \sum_{r=1}^\infty \cdot \left((1-p)^2\right)^r \\ &= p^2 \cdot \frac{1}{1 - (1-p)^2} \end{align}

Similarly,

\begin{align} P(\text{attacker destroyed at end of combat}) &= p \cdot (1-p) \cdot \frac{1}{1 - (1-p)^2} \\ P(\text{defender destroyed at end of combat}) &= p \cdot (1-p) \cdot \frac{1}{1 - (1-p)^2} \end{align}

As a check, do these probabilities add up to one? Let's find out.

\begin{align} &P(\text{both destroyed at end of combat}) \\ &+ P(\text{attacker destroyed at end of combat}) \\ &+ P(\text{defender destroyed at end of combat}) = \\ &=p^2 \cdot \frac{1}{1 - (1-p)^2} + p \cdot (1-p) \cdot \frac{1}{1 - (1-p)^2} + p \cdot (1-p) \cdot \frac{1}{1 - (1-p)^2} \\ &=p \cdot (p + 2\cdot (1-p)) \frac{1}{1 - (1-p)^2} \\ &=p \cdot (p + 2\cdot (1-p)) \frac{1}{1 - (1-2p+p^2)} \\ &=p \cdot (p + 2\cdot (1-p)) \frac{1}{2p-p^2} \\ &=p \cdot (p + 2\cdot (1-p)) \frac{1}{p\cdot(2-p)} \\ &=(p + 2\cdot (1-p)) \frac{1}{2-p} \\ &=(p + 2-2p) \frac{1}{2-p} \\ &=(2-p) \frac{1}{2-p} \\ &=1 \end{align}

So we're correct. (Initially I had $(1-p)^2$ in the numerator because I had $r$ instead of $r-1$ in the early equations above. As indicated by my errata, these checks are important.) That's mostly algebra, but I need a lot more explanation here.

We used an infinite series above, but we could instead argue that we can simply ignore the case where neither are destroyed in a round since we only care about the end state. Getting such a result simply delays the final outcome. Thus, we take the probabilities of the remaining three cases and divide by their sum to get the probability of ending in the corresponding states.

\begin{align} P(\text{both destroyed at end of combat}) &= \frac{P(\text{both destroyed in first round})}{P(\text{something destroyed in first round})} \\ P(\text{attacker destroyed at end of combat}) &= \frac{P(\text{attacker destroyed in first round})}{P(\text{something destroyed in first round})} \\ P(\text{defender destroyed at end of combat}) &= \frac{P(\text{defender destroyed in first round})}{P(\text{something destroyed in first round})} \end{align}

Where $P(\text{something destroyed in first round})$ is the sum of the three first-round probabilities above.

\begin{align} &\begin{split} P(\text{something destroyed in first round}) &= P(\text{both destroyed in first round}) \\ &+ P(\text{attacker destroyed in first round}) \\ &+ P(\text{defender destroyed in first round}) \end{split} \\ &= p^2 + p\cdot (1-p) + p\cdot (1-p) \\ &= p^2 +2\cdot p - 2\cdot p^2 \\ &= 2 \cdot p - p^2 \\ &= p \cdot (2-p) \end{align}

Plugging in, we find that,

\begin{align} P(\text{both destroyed at end of combat}) &= \frac{p^2}{p \cdot (2-p)} \\ P(\text{attacker destroyed at end of combat}) &= \frac{p\cdot (1-p)}{p \cdot (2-p)} \\ P(\text{defender destroyed at end of combat}) &= \frac{p\cdot (1-p)}{p \cdot (2-p)} \end{align}

These are the same probabilities that we calculated earlier. Note that the two different versions of the equations are written a little differently, but $1-(1-p)^2 = p\cdot (2-p)$.

That's enough for now. I'll later expand this same idea to more complicated combat mechanics.