Monday, October 25, 2021

Should everyone always lose semi-coop games?

Unfortunately, in order to answer this question, we have to do a bit of taxonomy first, as "semi-coop", short for semi-cooperative, means different things to different people.

Some people call hidden team games like Battlestar Galactica and/or cooperative games with a possible traitor like Shadows over Camelot semi-coops. I can see the motivation for this as they look like a "cooperative, but ..." game, yet it doesn't seem necessary to differentiate these from other team games like Space Cadets: Dice Duel, Codenames, and The Resistance.

Instead, we are talking about games like CO2, Legendary, and Dead of Winter. The through-line seems to be that these are games where players do not always win together (like a cooperative game), but they may all lose together. However, that definition includes games like Galaxy Trucker, which I don't think anyone would consider a semi-coop. A more precise definition would be that there is a condition that if not met means that none of the non-traitor players are eligible to win and instead lose. I specify non-traitor because many, but not all, of these games feature a traitor, who is essentially on a team with the game trying to make the rest of the players lose.

Within this definition I see three types of semi-coop, which have important distinctions that we'll get to.

In type I semi-coops, or single-winner semi-coops, either all players lose or one player wins while all other players lose. Examples include CO2 (in "mostly competitive" mode), Robin Hood and the Merry Men, Castaways, and Divided Republic. Examples that include a possible traitor are AuZtralia, Homeland, and Republic of Rome (which has an opt-in traitor).

In type II semi-coops, or group-win semi-coops, there are two types of winning. Either all players lose or all players win, but if all players win there is also an individual winner. Examples include Legendary, Castle Panic (although it only uses the word "win" for the group win), Arkham Horror (group win plus "honorary title of First Citizen of Arkham"), Horizon Zero Dawn (although the terminology is confusing "Although all players have won..., the player with the most victory points...emerges as the winner of the game"), and Tomorrow (mentions "win" for both, but in separate sections of the rulebook). Archipelago is an example with a possible traitor.

Type III semi-coops, or separate-goal semi-coops, have separate win conditions for each player in addition to the group loss. An example is Forgotten Waters. Examples with a possible traitor include Dead of Winter, Nemesis, and New Angeles. Dead of Winter labels itself as a "meta-cooperative" game, but the term doesn't seem to have caught on, though it may be useful to describe type III semi-coops.

Games that don't fit this definition but some may call semi-coops include Cutthroat Caverns, Crisis, Bag of Dungeon (using an optional advanced rule), Hellapagos (whoever gets rescued wins, which can be any subset of players), Fog of Love (each player's performance is determined individually), Pax Emancipation (which has a first phase after which the game may end with any number of players may win except all, as well as a possible second phase which is purely competitive) and Core Space (which has the odd combination of a group win if an objective is completed and an individual win if it is not). While these games do feature the possibility of everyone losing, this is usually still determined on a per-player basis.

Type I: single-winner semi-coops

Let's look at a simplified model of a three player type I semi-coop game. Each player has two moves and chooses simultaneously: cooperate (C) or defect (D). If at least two players cooperate, this prevents the all lose scenario. If one player defects, that player is the winner. If all players cooperate, then the winner is randomly select from them.  This is depicted in Table 1, where each row represents an outcome based on the first player's move (P1), while each column represents the combined moves of the second and third players (P2 & P3).

\begin{align*} \begin{array}{c |c|c|c} \text{P1 \\P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline D & \text{All lose} & \text{All lose} & \text{P1 wins} \\ C & \text{All lose} & \text{P2 or P3 wins} & \text{P1 may win} \end{array} \end{align*} 
Table 1: A simple type I semi-coop game

Type I semi-coops have the issue that the best move is to defect, as defecting is a weakly dominant strategy, meaning that defecting is sometimes better but never worse than cooperating. This is perhaps more clear in Table 2, which is focused on the first player. Additionally, if players put any positive value to have fellow players also lose (that is, any preference for all lose to someone else wins), then defecting is even more incentivized, but remains a weakly dominant strategy.

\begin{align*} \begin{array}{c |c|c|c} \text{P1 \P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline D & \text{Lose} & \text{Lose} & \text{Win} \\ C & \text{Lose} & \text{Lose} & \text{May win} \end{array} \end{align*}

Table 2: First player's outcomes simple type I semi-coop game

Note that this model only holds if two players cannot easily spoil the victory of another. Additionally, it assumes individual victory and avoiding group loss are at odds with each other. This trade-off is not inherent. For example, suppose you have a game where players earn points throughout the game and all players lose if the sum of the points of all players is not sufficiently high. Now, consider two metrics for individual victory. In the first, the player with the fewest number of points is the individual winner. Here, as long as you lack the ability to manipulate other player's points, the lessons we learned above hold and we wouldn't expect there to be a winner (depending on the total point threashold), as all players tries to minimize their own scores. However, in the second metric, the player with the most number of points is the individual winner. Here, actions that avoid a group loss and obtain individual victory are likely perfectly aligned (there are likely some exceptions due to interactions with other players). Since players are trying to maximize their own scores to be the individual winner, the group loss condition is easily avoided. Of course, in such a situation, you may ask why a group loss condition is included in the game. (While I doubt such a game exists, you could include the rule to avoid dominant strategies that end the game very quickly and are not satisfying in some way. There may be better solutions than making the game semi-cooperative.) The defect or cooperate paradigm does not match with this second metric for an individual win.

Type II: group-win semi-coops

Let's move onto the more interesting type II semi-coop. Table 3 shows another model of a simple simultaneous-play semi-coop game. This time we've adjusted the values both to represent a type II semi-coop, but also to look at the payoffs for the first player, so that we can make use of a game theory analysis. We will assume that all lose is valued at 0, while group win or all win ($AW$) and individual win ($IW$) each have some positive unknown value (but common to all players).

\begin{array}{c |c|c|c}
\text{P1 \P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW+\frac{1}{3}IW
Table 3: A simple type II semi-coop game

First, let's acknowledge some fragility to this system. Akin to how competitive games can break down if any of the players are not trying to win (it seems relevant to quote Reiner Knizia: "Remember: When playing a game, the goal is to win, but it is the goal that is important, not the winning..."), semi-cooperative games can break down if players do not accept the payoffs given by the game. While competitive games have their payoffs generally accepted and understood by most people, semi-cooperative games are more rare, especially type II semi-coops, which have multiple types of winning. Some players may ignore one or the other type of winning. If $IW$ is valued at 0, then the game is essentially cooperative, and all players will cooperate as it is a weakly dominant strategy. If $AW$ is valued at 0, then the game reverts to a type I. Some people also reject the idea that a group win is better than a group loss in a type II semi-coop (the interpretation is that in the case of a group loss, all players do as well as each other and so the game ends in a draw, which is preferable to a group win where you are losing to another player; the latter is interpreted as a simple loss), essentially valuing $AW<0$. In that case, as in type I, defecting is a weakly dominant strategy (it's better if exactly one other player cooperates, but doesn't matter if both others either cooperate or defect together). Under such a valuing of the outcomes the game breaks down as it does in a Type I semi-coop. Conversely, players of a Type I semi-coop may value avoiding the all-lose condition such that they effectively add a group win, turning it into a type II semi-coop. We will proceed assuming all players accept the value of both types of winning, while also acknowledging there is some ambiguity in that these games do not specify how much to care about the two types of winning relative to each other.

In this type II semi-coop there is no obviously best move. If both other players defect, it doesn't matter what the first player does. If one other player defects but one cooperates, then cooperation is preferred as this ensures that all win (including player one). On the other hand, if both other players cooperate, then defection is preferred, as that move guarantees obtaining the individual win.

This type II semi-coop has several Nash Equilibria. The first three pure-strategy Nash Equilibria are the cases where one player defects while the other two cooperate. There are three, because there's one for each player being the defector. This is a Nash Equilibrium because no player can do better by changing strategy. Suppose the first player is defecting while the other two are cooperating. This puts us in the third column. The first player is better off with a definite individual win than a one-third chance of an individual win. In both cases, the group win condition is guaranteed. The second and third players each face the choice between a group win and a group loss. Neither can unilaterally do anything to do better given the strategies of the other players. A lesson that we can take from this model is that if you can be the first to convince other players that you either have or will defect, you will likely be the individual winner. As such, these games may have a strong first-player advantage, depending on how quickly a player can establish defection.

Another pure strategy Nash Equilibrium is if all players defect. With all players defecting, the all lose outcome occurs, but no single player is in a position to change it. Here it is evident that the Nash Equilibrium is really about stability not about a how good a set of strategies is. Note that in this situation, though, any player may deviate from a defection strategy without detriment.

There is also a mixed-strategy (a mixed-strategy employs one of a number of pure strategies with a given set of corresponding probabilities) Nash Equilibrium of cooperate and defect. The mix depends on the relative valuing of the different outcomes. To find this Nash Equilibrium, we'll make use of the fact that we know that each component strategy must be a best response and have the same average payout. So the payout of defect and cooperate must be the same. Assume in the equilibrium that each player cooperates with probability $p$, and thus defects with probability $1-p$. The probability that both players 2 and 3 cooperate is $p^2$. The probability that they do one of each is $2 \cdot p \cdot (1 - p)$. Recall that the 2 comes from the fact that either player could be the one that cooperates, so there are two ways that it happens. The payoff for player one are thus as follows.

u(D) &= p^2 \cdot \left ( AW + IW \right ) \\
u(C) &= 2 p(1-p) \cdot AW + p^2 \cdot \left ( AW +\frac{1}{3} IW \right )

So let's set these equal to find $p$.
u(D) &= u(C) \\
p^2 \cdot \left ( AW + IW \right ) &= 2 p(1-p) \cdot AW + p^2 \cdot \left ( AW +\frac{1}{3} IW \right ) \\
p^2 \cdot \left (\frac{2}{3} IW \right ) &= 2 p(1-p) \cdot AW \\
p\cdot \frac{2}{3} IW &= 2 (1-p) \cdot AW \\
p\cdot \left (\frac{2}{3} IW + 2AW \right ) &= 2\cdot AW \\
p &= \frac{2 AW}{\frac{2}{3} IW + 2AW}

We can see our earlier conclusions about the simplified cases fall out from this. If $AW=0$, then $p=0$, as we're in the type I semi-coop case. If $IW=0$, then the game is cooperative and $p=1$. For positive values of both AW and IW, though, we find $0 < p < 1$. Note that this works even if having everyone win is valued significantly above having the individual win, as an individual win requires a group win. We can rewrite this based on the ratio of the two values, $r = AW / IW$.

p &= \frac{2 AW}{\frac{2}{3} IW + 2AW} \\
p &= \frac{2 \frac{AW}{IW}}{\frac{2}{3} + 2\frac{AW}{IW}} \\
\require{cancel}p &= \frac{\cancel{2}\cdot 3 \frac{AW}{IW}}{\cancel{2} + \cancel{2}\cdot3\cdot\frac{AW}{IW}} \\
p& = \frac{3r}{1 + 3r}

This is a monotonically increasing function, as shown in Figure 1, so the more we care about the group win compared to the individual win, the more we cooperate (this is expected and perhaps obvious).

Figure 1: Probability of Cooperation in a Type II Semi-cooperative Game with Equal Player Standing

Suppose we value them equally, such that achieving individual victory has twice the total utility as being part of a group win. This means that we'll cooperate with probability $p=3/4$ or 75% of the time.

Operating under this strategy, we can find the probability that the group wins. This occurs when at most one player defects. The probability that all players cooperate is $p^3$. The probability that one player defects is $3\cdot p^2 \cdot (1-p)$. For $p=3/4$, this means the probability of a group win is,

P(AW) &= p^3 + 3 \cdot p^2 \cdot (1-p) \\
&= 3p^2 - 2p^3 \\
&= 3 \cdot \left (\frac{3}{4} \right ) ^2 - 2 \cdot \left ( \frac{3}{4} \right ) ^3\\
&\approx 0.84.

This is shown in Figure 2 as a function of the ratio $r$.

Figure 2: Probability of Successful Cooperation in a Type II Semi-cooperative Game with Equal Player Standing

Type II with unequal standing

Now, let's consider a case where the players do not have equal standing. This perhaps models the end of the game. Let's assume players 1, 2, and 3 are in that rank, such that if all cooperate, then player 1 will win. However, if any one player defects (with the other two cooperating) the defecting player wins.

\begin{array}{c |c|c|c}
\text{P1 \ P2 & P3} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW+IW \\

Table 4: A simple type II semi-coop game for player 1 while ahead

Here, for player 1, cooperate is weakly dominant, since the individual win is ensured if all player cooperate. Thus, player 1 likely cooperates.

\begin{array}{c |c|c|c}
\text{P2/3 \ P1 & P3/2} & 2 D & 1D, 1C & 2C \\ \hline
D & 0 & 0 & AW+IW \\
C & 0 & AW &AW

Table 5: A simple type II semi-coop game for players 2 or 3 while behind

However, players 2 and 3 are much more like the earlier analysis. We can check the previous Nash Equilibria to see if they still hold. All defect still is, as well as cases where any one player defects while the other two cooperate. However, player 1 defecting and others cooperating is now a weak Nash Equilibrium, as player 1 is no worse off for cooperating.

Due to the asymmetry introduced, when looking for an updated mixed-strategy Nash Equilibrium, let's say that the first player cooperates with probability $p_1$ and the second and third players each cooperate with probability $p_2$. We can now employ similar techniques as before, however, we'll have more equations as we have a new variable. We'll still assume that $AW$ and $IW$ are valued equally between all players. First, let's look at the payoffs for player 1.

u(D_1) &= p_2^2 \cdot \left ( AW + IW \right ) \\
u(C_1) &= 2 p_2(1-p_2) \cdot AW + p_2^2 \cdot \left ( AW + IW \right ) \\
u(D_1) &= u(C_1)

From this point, we just do some algebra.

\require{cancel}\cancel{p_2^2 \cdot \left ( AW + IW \right )} &= 2 p_2(1-p_2) \cdot AW + \cancel{p_2^2 \cdot \left ( AW + IW \right )}\\
0 &= 2 p_2(1-p_2) \cdot AW

Here there are two solutions, $p_2=0$ and $p_2=1$. This is somewhat of a contradiction, as we assumed a mixed-strategy for players 2 and 3, yet here we get pure strategies. If we look at the payoffs for player 1, we see the incorrect assumption that we made: that player 1 plays a mixed strategy. Cooperating is always as good as defection for player 1, and sometimes better. If players 2 and 3 are playing mixed strategies, then we should expect that sometimes one will cooperate and one will defect, which means that the only way for player 1 to have a best response 100% of the time is to cooperate.

Knowing this, we can actually simplify the game from, since we know player 1 will cooperate.

\text{P2/3 \ P3/2} & D & C \\ \hline
D & 0 & AW+IW \\
C & AW &AW

Table 6: A simple type II semi-coop sub-game for players 2 & 3 if player 1 cooperates

Again using $p_2$ for the probability of cooperation for only players 2 and 3, we can find the payoffs for each move. We'll repeat the same method of setting the payoffs equal to each other.

u(D) &= u(C)\\
p_2 \cdot \left (AW+IW \right ) &= AW\\
p_2 &= \frac{AW}{AW+IW}\\
p_2 &= \frac{r}{1+r}

We find a probability of cooperation which is lower than before (assuming the same values of ratio of the value of the group win AW to the individual win IW). For equal values ($r=1$), $p_2=0.5$, only 50%! This makes sense, as there's less incentive now to cooperate. A graphical comparison is presented in Figure 3.

Figure 3: Probability of Cooperation in a Type II Semi-cooperative Game with 2 Players Behind a Leader compared to Equal Standing

However, did this decrease the probability of a group win?

P(AW) &= p_2^2 + 2\cdot p_2 \cdot (1-p_2) \\
&=2p_2 - p_2^2\\

This did somewhat decrease the probability of a group win, but perhaps not by as much as we might have thought. As shown in Figure 4, there are even some cases where the probability of successful cooperation is higher than with equal standing, although this is only when the group win is valued at a small fraction of the individual win.

Figure 4: Probability of Successful Cooperation in a Type II Semi-cooperative Game with 2 Players Behind a Leader compared to Equal Standing

Type III: separate-win semi-coops

Since type III semi-cooperative games, or meta-cooperative games, do not rank players to determine a winner, there is not the same kind of concept of cooperating vs. defecting as in the analyses we performed thus far. There may still be tension between avoiding the all-lose outcome and achieving personal goals, but this tension is not directly influenced by the situation of other players.


To recap, we saw that in a simple type I semi-coop game, where either all lose or there is one winner, we somewhat expect that all players lose.  (Note that while this may be a strategically unsatisfying play experience, it may be interesting art or commentary.) This is the only Nash Equilibrium and defecting is a weakly dominant strategy. If we add a group win, thus converting to a type II semi-coop, we can avoid this, as there are stable states where all players win. However, this is subject to the strategies employed by the players. If a majority of the players demand to get advantage for the individual win by defecting, then all will lose, and all players defecting is also a Nash Equilibrium. Additionally, even in the case where the group win is achieved, this could be because a certain player is defecting while the others cooperate. Such a condition may be unpleasantly static.  

So the answer is no, as players in a group-win semi-coop may be able to rationally achieve cooperation.

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.

Thursday, April 1, 2021

Are there really 504 games in 504?

The game 504 is actually many games. You assemble each one by selecting one of nine modules for the top, middle, and bottom of the rules, which flip around separately to accommodate the selection.

You may think that there should be $9^3=729$ games, because for each of the three sections of the rules you have nine options. However, you cannot pick the same module for more than one section.

Considering that, you may adjust to think that there should be ${9 \choose 3} = \frac{9!}{3! \cdot (9-3)!} = 84$ games. You're selecting three modules out of a total of nine, it sounds like a combination problem. However, the order here matters. It matters if module 9 is the top or the bottom of the rules, as they describe different aspects of the game.

Thus, there are indeed $\frac{9!}{(9-3)!} = 9\cdot 8 \cdot 7 = 504$ games. This is a permutation problem. For the first, you have nine options. The second, you have eight remaining choices, and seven for the third.