Monday, May 31, 2021

Errata: What's the toughest unit in Memoir '44?

I was preparing to revisit what the toughest unit in Memoir '44 is by looking at it using a Markov chain model. Then I discovered that I had an error in my earlier calculation. I'll fix my calculation and derive the expected number of dice needed to eliminate each type of unit. Recall that I derived the following equation for the expected number of dice needed to eliminate a given unit, $N$, as follows. \begin{align} \mathbb{E} N &= \sum_{n=0}^\infty 1 - F_N(n) \end{align} Here $F_N(n)$ is the CDF of $N$, meaning that $F_N(n) = P(N \leq 0)$. See the previous analysis for the derivation of the CDF. The error came in the range of the summation for $\mathbb{E} N$, which starts at zero. However, my code to the computation stored the CDF starting at $n=1$, since it is known to be 0 at $n=0$; it's impossible to eliminate a unit without rolling any dice. This means that I should add one to the previous estimates, as shown below. \begin{align} \widehat{\mathbb{E} N_\text{infantry}} & \approx 8.000000000000002 \\ \widehat{\mathbb{E} N_\text{armor}} & \approx 8.999999999999932 \\ \widehat{\mathbb{E} N_\text{artillery}} & \approx 11.999998659711212 \\ \end{align} 

Figure 1: Estimating expected value with finite sum

This means that our guess as to the true expected values are below and the updated formula would be $\mathbb{E} N = f/p$. \begin{align} \mathbb{E} N_\text{infantry} & = 8 \\ \mathbb{E} N_\text{armor} & = 9 \\ \mathbb{E} N_\text{artillery} & = 12 \end{align} This makes a lot more sense and perhaps I should have caught the previous error. Without the odd $-1$ hanging off the back end of the equation, this means that the expected value of proportional to the number of starting figures. This makes sense, especially in our one die at a time analysis. If it takes an average of $1/p$ dice to remove one figure, then it should take an average of $f/p$ dice to remove $f$ figures. First, we remove one figure, then the second, and then so on $f$ times. Each time takes an average of $1/p$ dice, so $f/p$ dice in total. The expectation is also inversely proportional to $p$. While clearly in the correct direction, it'll take a little more analysis to establish this precise relationship. If we increase the probability of hitting with each die, it'll decrease the number of dice we need to roll before getting a hit. Let's analysis the expected number of dice rolled to get the first hit, $N_\text{hit}$, for a unit with a probability of getting hitting one die $p$. To get a hit on the $n$-th die, after missing previously, the probability is, \begin{align} P(N_\text{hit} = n) = (1-p)^{n-1} \cdot p. \end{align} While we could use this, we can use the same shortcut to find the expected value as before. \begin{align} \mathbb{E} N_\text{hit} = \sum_{n=0}^\infty P(N_\text{hit} > n) \end{align} The probability that we haven't gotten a hit in $n$ dice, $P(N_\text{hit} > n)$ is the probability that we roll a miss all $n$ times. \begin{align} P(N_\text{hit} > n) = (1-p)^n \end{align} Thus, the expected value is, \begin{align} \mathbb{E} N_\text{hit} = \sum_{n=0}^\infty (1-p)^n . \end{align} This is a familiar infinite series, although it might not be immediately recognizable in this form. If we instead substitute $a = 1-p$ and notice that $a < 1$ for $p > 0$, then it becomes more familiar. \begin{align} \mathbb{E} N_\text{hit} &= \sum_{n=0}^\infty a^n \\ &= a^0 + a^1 + a^2 + a^3 + \ldots \\ & = \frac{1}{1-a} \end{align} This is very similar to the analysis done related to rolling for actions in First Martians. Finally, we substitute back in that $a = 1-p$. \begin{align} \mathbb{E} N_\text{hit} &= \frac{1}{1-a} \\ &= \frac{1}{1 - (1-p)} \\ & = \frac{1}{p} \end{align} Combining this result for a single figure with the previous analysis we find that indeed $\mathbb{E} N = f/p$.

Monday, May 24, 2021

Link: Special Hunt Tiles in War of the Ring

I found the above analysis of the special red and blue hunt tiles in War of the Ring by Ira Fay to be interesting.  Also see the linked simulator here:

For my taste, I'd want to figure out how to do this without relying on a Monte Carlo simulation, but it's probably a lot easier and seems to run pretty fast.

Note: Ira also has several videos on his channel of him going through games of War of the Ring that he goes through and comments on.

Monday, May 17, 2021

Should I roll or use two pawns in First Martians?

In my review of First Martians, I included a table showing the expected number of pawns required for each type of action when rolling (see Table 1). Here's I'll go through the math behind that table. 

Table 1: Expected pawns when rolling for actions

First, let me establish the relevant rules and constraints of the analysis. In general, actions may completed by using two pawns on them for an automatic success, or only using one pawn but having to roll three dice that determine a number of possible outcomes. Some actions require additional dice, which I'll discuss briefly later. The first die determines whether the action succeeds or the player gains two morale tokens (which power special abilities), the second die determines whether or not the character receives a wound, and the third die determines whether the character has an adventure, which entails requesting a the app for the game to explain some additional event which generally harms the character in some way or provides some additional obstacle. Since these are three separate dice being rolled they are all independent and any combination of outcomes is possible. Further, the distributions of the types of sides on the three dice depend on the type of action. Each die determines only one of two sets of outcomes, Table 1 shows the probabilities for the three outcomes of interest: success, wound, and adventure. We'll denote these as $p_s$, $p_w$, and $p_a$, respectively. While morale tokens can be useful, I have ignored them here, as they do not necessarily translate into success in a given action. Next, let's look at how many times we'll have to roll in order to succeed at the action, given by the random variable $N$. A useful way to calculate this for non-negative random variables is the following equation. \begin{align} \mathbb{E} N = \sum_{n=0}^\infty P(N > n) \end{align} While I won't do a full proof, I'll note that there's some discussion of it here. The following illustration will help to see why this is true. We can write $P(N > n)$ in terms of all the relevant $P(N = n)$. \begin{align} P(N>n) &= \sum_{i=n+1}^\infty P(N=i) \\ &=P(N=n) + P(N=n+1) + P(N=n+2) + \ldots \\ \mathbb{E} N &= \sum_{n=0}^\infty \sum_{i=n+1}^\infty P(N=i) \\ \end{align} We can expect and regroup this to see how it's equal to the expected value. \begin{alignat}{9} \mathbb{E} N =& P(N = 1) &&+& P(N = 2) &&+& P(N = 3) &&+& P(N = 4) &&+&\ldots \\ & &&+& P(N=2) &&+& P(N = 3) &&+& P(N = 4) &&+&\ldots \\ & &&& &&& P(N = 3) &&+& P(N = 4) &&+&\ldots \\ &\underbrace{\phantom{P(N = 1)}}_{1\cdot P(N=1)} &&& \underbrace{\phantom{P(N = 2)}}_{2\cdot P(N=2)} &&& \underbrace{\phantom{P(N = 3)}}_{3\cdot P(N=3)} &&+& \underbrace{P(N = 4)}_{4\cdot P(N=4)} &&+& \ldots \\ \end{alignat} This matches the expected value, which is the average, given by the sum of all possible outcomes weighted by the probability that they occur. \begin{align} \mathbb{E} N = \sum_{n=1}^\infty n \cdot P(N = n) \end{align} Here, the number of rolls must be at least one, so the range of the summation is set accordingly. However, note that this also works for random variables which are non-negative ($N\geq 0$) instead of strictly positive ($N>0$), because the 0 term is always zero ($0 \cdot P(N= 0) = 0$). Now let's look at the relevant probabilities in this case. Given a probability of success, $p_s$, we can find the probability that the number of rolls, $N$, is more than $n$. It is the probability that the first $n$ rolls fails, which each occur with probability $1-p_s$. These are independent, so we can multiply all the probabilities together. \begin{align} P(N > n) &= (1-p_s)^n \end{align} Thus, the expected value is, \begin{align} \mathbb{E} N = \sum_{n=0}^\infty (1-p_s)^n . \end{align} This is a familiar infinite series, although it might not be immediately recognizable in this form. If we instead substitute $a = 1-p_s$ and notice that $a < 1$ for $p_s > 0$, then it becomes more familiar. \begin{align} \mathbb{E} N &= \sum_{n=0}^\infty a^n \\ &= a^0 + a^1 + a^2 + a^3 + \ldots \\ & = \frac{1}{1-a} \end{align} If you haven't seen this before, first, let's remember that $a^0 = 1$. \begin{align} \mathbb{E} N &= 1 + a^1 + a^2 + a^3 + \ldots \end{align} Next we can multiple both sides by $a$ and then add 1 to both sides. \begin{align} a \cdot \mathbb{E} N &= a^1 + a^2 + a^3 + \ldots \\ 1 + a \cdot \mathbb{E} N &= 1 + a^1 + a^2 + a^3 + \ldots \\ \end{align} At this point we notice that the right hand side is equal to our original infinite series for $\mathbb{E} N$. From there we can employ some algebra to find the expected value in question. \begin{align} 1 + a \cdot \mathbb{E} N &= \mathbb{E} N \\ 1 &= \mathbb{E} N \cdot (1 - a) \\ \frac{1}{1-a} &= \mathbb{E} N \end{align} Finally, we substitute back in that $a = 1-p_s$. \begin{align} \mathbb{E} N &= \frac{1}{1-a} \\ &= \frac{1}{1 - (1-p_s)} \\ & = \frac{1}{p_s} \end{align} This means that expect to roll 1.2 times and 1.5 times for $p_s = 5/6$ and $p_s = 4/6$, respectively. If this were the only die in consideration, perhaps this would make a good game. In general it would be more efficient to roll, but sometimes it be important to guarantee success now. However, there are two other dice in the picture, related to wounds and adventures. To deal with a wound costs 1 pawn in 1--3 player games and 2 pawns in 4 player games; I'll use the lower 1 pawn cost, even though sometimes a wound can trigger a condition token which usually costs a pawn to remove. Based on my experience with the game (20+ plays), I estimate the cost of dealing with an adventure to average out to about 1 pawn also, though this in more variable. In both cases, you may or may not have to pay these costs. If the game is close to the end, or it affects an abundance resource, you may not have to. However, wounds usually need to be healed to avoid potential death. Any cost here is borne in subsequent rounds, which can make a difference, but is not quantified here. Wounds occur with probability, $p_w$, of $3/6=1/2$ or $2/6 = 1/3$, while adventures occur with probability, $p_a$, of $3/6=1/2$ for all action types. Since the cost is 1 pawn, the additional pawns expected for each roll is $1\cdot p_w + 1\cdot p_a = p_w + p_a$. Note that this is per roll, not overall. To get the overall expected number of pawns when rolling, we have to look at expectation of the number of rolls times the number of pawns used for that roll (including resolving wound and adventure consequences). The number of pawns when rolling (still assuming a base cost of 1 pawn to declare the action), is $1+C$, where $C$ is a random variable of the cost in pawns of wounds and adventures determined by the roll. For the $n$-th roll, we can label the corresponding cost $C_n$. The total pawn cost, $T$, is $1+C_n$ for the $n$-th roll and summed over all $N$ rolls. \begin{align} T &= \sum_{n=1}^N 1 + C_n \\ & = N + \sum_{n=1}^N C_n \end{align} The average cost is given by the expected value. \begin{align} \mathbb{E} T &= \mathbb{E} \left (N + \sum_{n=1}^N C_n \right )\\ &= \mathbb{E} N + \mathbb{E}\sum_{n=1}^N C_n \\ &= \frac{1}{p_s} + \mathbb{E}\sum_{n=1}^N C_n \\ \end{align} To simplify the expectation above, we can recognize that the all $C_n$ are independent and identically distributed, so we can turn the summation into multiplication. \begin{align} \mathbb{E}\sum_{n=1}^N C_n &= \mathbb{E}\left ( \underbrace{C + C + \ldots + C}_{N \text{terms}} \right ) \\ &= \mathbb{E} \left (N \cdot C \right ) \end{align} Because $N$ is set by the rolls of the one of the dice and $C$ is set by a roll of the other two dice, they are independent. That means we can distribute the expectation across the two random variables. \begin{align} \mathbb{E} \left (N \cdot C \right ) &= \mathbb{E} N \cdot \mathbb{E} C \end{align} We already computed the expected pawn cost due to wounds and adventures. \begin{align} \mathbb{E} C &= p_w + p_a \end{align} Putting this all together, we find the average total cost as the expected value of $T$. \begin{align} \mathbb{E} T &= \mathbb{E} N + \mathbb{E} N \cdot \mathbb{E} C \\ &=\mathbb{E} N \cdot \left ( 1 + \mathbb{E} C \right )\\ \mathbb{E} T &= \frac{1}{p_s} \cdot \left ( 1 + p_w + p_a \right) \end{align} When the is computed for each of the action types, we get the expected pawns listed in Table 1. Note that in all cases this value is greater than the 2 pawns required to guarantee success. This means that on average, you are better off using 2 pawns to guarantee success rather than using 1 initial pawn and rolling. For actions that have a higher base cost, requiring additional pawns, this effect continues, and is even more pronounced. This is because the additional pawns are required in every roll, the number of which still averages to $1/p_s$. Thus, for $k$ pawns required to roll, the average total cost, $T_k$ is, \begin{align} \mathbb{E} T_k &= \frac{k + p_w + p_a}{p_s} \end{align} Ignoring the cost of wounds and adventures, just the pawns spent to attempt the action average to $k/p_s$, which should be compared to $k+1$. For $k=2$, $k/p_s$ is 2.4 and 3.0 for $p_s$ of $5/6$ and $4/6$, respectively. The total costs are $\mathbb{E} T_2$ are shown in Table 2. 

\begin{align*} \begin{array}{c|c|c|c|c} \text{Action} & p_s & p_w & p_a & \mathbb{E} T_2 \\ \hline \text{Explore} & 5/6 & 3/6 & 3/6 & 3.6 \\ \text{Gather} & 5/6 & 2/6 & 3/6 & 3.4 \\ \text{Research} & 4/6 & 2/6 & 3/6 & 4.25 \\ \text{Build} & 4/6 & 2/6 & 3/6 & 4.25 \\ \end{array} \end{align*} 
Table 2:Expected pawns with one additional pawn to roll

 In fact, for any base cost $k$, the expected number of pawns when rolling is larger than the number of pawns required to guarantee success. We can see this by showing that $\mathbb{E} T_k > k+1$. For all actions types $p_s < 1$, which means that $k/p_s > k$. Furthermore, $(p_w+p_a) / p_s \geq 1$ for all action types. \begin{align} \mathbb{E} T_k &= \frac{k + p_w + p_a}{p_s} \\ \mathbb{E} T_k &\geq \frac{k}{p_s} + 1 \\ \mathbb{E} T_k &> k + 1 \end{align} Thus, the expected number of pawns when rolling is higher than the number of pawns needed to guarantee success.