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.

No comments:

Post a Comment