Monday, November 30, 2020

Who has an advantage in Risk, attacker or defender?

Let's first assume that we're talking about the frequent case where the attacker is rolling 3 dice, while the defender can only roll 2 dice, but ties go to the defender. More dice is better. Winning ties is better. But which of those wins out? Let's see.

One thing that's tricky here is that we compare the highest attacker die to the highest defender die, and the second highest attacker die to the lowest defender die. So we have to consider the joint probability distribution of the two attacker dice and the two defender dice. We can treat the attacker and defender separately, though, since they are independent.

Let's start by working with the defender, and looking at the CDF of the better roll of 2d6. Recall the CDF $F_X(x) = P(X \leq x)$. Let's say $D_1$ is the the higher die of the defender, with $D_2$ being the lower die. Let's say that X is the result of rolling a 1d6.

\begin{align} F_{D_1}(d) = P(D_1 \leq d) = P(X \leq d)^2 \end{align}

That is, the probability that the highest die is less than or equal to $d$ is the probability that both dice are less than or equal to $d$.

\begin{align} F_{D_1}(d) = \left ( \frac{d}{6} \right)^2 \end{align}

What about $F_{D_2}(d)$? Similar to above, we can say that

\begin{align} F_{D_2}(d) &= P(D_2 \leq d) \\ &= 1 - P(D_2 > d) \\ &= 1 - P(X > d)^2 \\ &= 1 - \left ( \frac{6-(d+1)+1}{6} \right)^2 \\ &= 1 - \left ( \frac{6-d}{6} \right)^2 \\ &= \frac{6^2}{6^2} - \frac{6^2-12d+d^2}{6^2} \\ &= \frac{6^2-6^2+12d-d^2}{6^2} \\ &= \frac{12d-d^2}{6^2} \\ &= \frac{d}{6}\cdot \frac{12-d}{6} . \end{align}

Those make sense, though we should check that they work out at say $d=1$ and $d=6$. But those are assuming that they're independent. Given that the highest die comes out to be $d_1$, what's the distribution of $D_2$? Or what is $P(D_2 = d_2 | D_1 = d_1)$. Well, it's certainly 0 if $d_2 > d_1$.

This seems to be a hard one.

It may just be easier to calculate the joint probability directly.

\begin{align} P(D_1=d_1, D_2=d_2) = \begin{cases} 0 & d_1 < d_2 \\ P(d_1\text{ and }d_2\text{ on 2d6}) & d_1 = d_2 \\ P(d_1\text{ and }d_2\text{ on 2d6}) & d_1 > d_2 \end{cases} \end{align}

Let's drill down more, in the $d_1=d_2$ case, it's just the probability of getting both of that value when rolling 2d6.

\begin{align} P(d_1\text{ on 1d6}) &= \frac{1}{6}\\ P(d_1\text{ on both of 2d6}) &= P(d_1\text{ on 1d6})^2 \\ &=\left ( \frac{1}{6} \right ) ^2 \\ &=\frac{1}{36} \\ P(D_1=d_1, D_2=d_2) & = \frac{1}{36}, \quad d_1=d_2 \end{align}

Okay, now the $d_1 > d_2$ case. If we have two different values, there's two ways we could get them. Let's say we have two dice $A$ and $B$. We roll $d_1$ on $A$ and $d_2$ on $B$, or $d_1$ on $B$ and $d_2$ on $A$. The probability of rolling $d_1$ on a particular die is $1/6$, similarly for $d_2$. Thus, the probability of getting $D_1=d_1$ and $D_2=d_2$ is twice the probability of rolling $d_1$ and then $d_2$.

\begin{align} P(D_1=d_1, D_2=d_2) & = 2\cdot\frac{1}{6}\cdot\frac{1}{6}, \quad d_1>d_2\\ & = 2\cdot\frac{1}{36}, \quad d_1>d_2\\ & = \frac{1}{18}, \quad d_1>d_2 \end{align} \begin{align} P(D_1=d_1, D_2=d_2) = \begin{cases} 0 & d_1 < d_2 \\ \frac{1}{36} & d_1 = d_2 \\ \frac{1}{18} & d_1 > d_2 \end{cases} \end{align}

This makes some sense, and we can see that the probabilities are going to add up to one, though we should probably check more explicitly. You can think of this as rolling two dice in order. Then, if the second one came out larger, we switch the order. Thus, all the probabilities for $d_1 < d_2$ went from $1/36$ to 0, and all the probabilities for $d_1 > d_2$ went from $1/36$ to $2/36=1/18$. I think, ultimately, this last explanation is probably the way to think about it.

So let's take that kind of thinking and apply it to the attacker. Here we have three dice, but only use two. If we use this algorithmic approach we can conceive of rolling three dice, and then reordering them to be from largest to smallest. With two dice, we reordered, or we didn't. With three dice, there are more cases. Let's assume that we have three distinct results on our rolls. Then there are $3! = 3 \cdot 2 \cdot 1 = 6$ ways to order them. Thus,

\begin{align} P(A_1=a_1, A_2=a_2, A_3=a_3) &= 3! \cdot \left ( \frac{1}{6} \right ) ^3\\ &= 6 \cdot \frac{1}{6^3}\\ &= \frac{1}{6^2}\\ &= \frac{1}{36}. \end{align}

Interestingly, we only care about two of the values. So we want to sum up for all possible $a_3$. However, we've assumed here that $a_1 > a_2 > a_3$. Thus, the number of cases to sum is limited. The number of cases where $a_3 < a_2$ is equal to $a_2 - 1$.

\begin{align} P(A_1=a_1, A_2=a_2) &= \sum_{a_3 < a_2} P(A_1=a_1, A_2=a_2, A_3=a_3) \\ &= (a_2-1) \cdot \frac{1}{36} \\ &= \frac{a_2-1}{36} \end{align}

Oops, we left out one above. We left one case out. We were assuming $a_3 < a_2$, but that doesn't show up in the equation as we wrote it. We only really need to assume $a_3 \leq a_2$ (otherwise, it won't occur at all and the probability is zero). Thus, we can fix our equation as follows.

\begin{align} P(A_1=a_1, A_2=a_2) &= \sum_{a_3 \leq a_2} P(A_1=a_1, A_2=a_2, A_3=a_3) \\ &= a_2 \cdot \frac{1}{36} \\ &= \frac{a_2}{36} \end{align}

Oops, now I think I've done some double counting. Because if $a_1 > a_2 = a_3$ then there aren't $3!=6$ orderings There are only $(3!)/(2!) = 6/2 = 3$ ways. Thus,

\begin{align} P(A_1=a_1, A_2=a_2, A_3=a_2) &= 3 \cdot \frac{1}{6^3}\\ &= \frac{1/2}{36}. \end{align}


\begin{align} P(A_1=a_1, A_2=a_2) &= P(A_1=a_1, A_2=a_2, A_3 < a_2) + P(A_1=a_1, A_2=a_2, A_3=a_2) \\ &= \sum_{a_3 < a_2} P(A_1=a_1, A_2=a_2, A_3=a_3) + P(A_1=a_1, A_2=a_2, A_3=a_2) \\ &= (a_2-1) \cdot \frac{1}{36} + \frac{1/2}{36}\\ &= \frac{a_2-1/2}{36} \end{align}

We now have more cases to consider. As before, we need to consider the all equal case $a_1=a_2=a_3$, which, similar to before, occurs with probability $1/6^3 = 1/216$. We also have to consider all the cases where two of the dice are equal, but not to the third. We considered the $a_1 > a_2=a_3$ case above. But we also have $a_1=a_2 > a_3$. Again, we only have 3 orderings, so

\begin{align} P(A_1=a_1, A_2=a_1, A_3 < a_1) &= 3 \cdot \left ( \frac{1}{6} \right ) ^3\\ &= \frac{1/2}{36} . \end{align}

Note: I'm writing this weird fraction to keep a common denominator of 36. Perhaps we should really be working with a denominator of 72. Again we combine to get the probability independent of $a_3$.

\begin{align} P(A_1=a_1, A_2=a_1) &= P(A_1=a_1, A_2=a_1, A_3 < a_1) + P(A_1=a_1, A_2=a_1, A_3=a_1) \\ &= \sum_{a_3 < a_1} P(A_1=a_1, A_2=a_1, A_3=a_3) + P(A_1=a_1, A_2=a_1, A_3=a_1) \\ &= (a_1-1) \cdot \frac{1/2}{36} + \frac{1}{216}\\ &= (a_1-1) \cdot \frac{3}{6^3} + \frac{1}{6^3}\\ &= \frac{3\cdot (a_1-1) + 1}{6^3} \\ &= \frac{3 a_1-2}{6^3} \end{align}

Do these all add up to 1?

\begin{align} \sum_{a_1} P(A_1=a_1, A_2=a_1) + \sum_{a_1 > a_2} P(A_1 = a_1, A_2 = a_2) &= 1 \\ \sum_{a_1=1}^6 \frac{3 a_1 - 2}{6^3} + \sum_{a_1=2}^6 \sum_{a_2=1}^{a_1-1} \frac{a_2-1/2}{36} &= 1 \\ \sum_{a_1=1}^6 \frac{3 a_1 - 2}{6^3} + \sum_{a_1=2}^6 \sum_{a_2=1}^{a_1-1} \frac{a_2-1/2}{36} &= 1 \end{align}

Recall that,

\begin{align} \sum_{k=1}^n k = \frac{n(n+1)}{2}. \end{align}

Thus, continuing on, we have as follows.

\begin{align} \frac{3 \cdot \frac{6(6+1)}{2} - 2\cdot 6}{6^3} + \sum_{a_1=2}^6 \left (\frac{(a_1-1)a_1}{2}-\frac{1}{2}\cdot (a_1-1)\right) \cdot \frac{1}{36} &= 1 \\ \frac{51}{6^3} + \sum_{a_1=2}^6 \frac{a_1^2-2a_1+1}{2} \cdot \frac{1}{36} &= 1 \end{align}

Now we have the sum of a squared term, which is given by,

\begin{align} \sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}. \end{align} \begin{align} \frac{51}{6^3} + \frac{\left(\frac{6(6+1)(12+1)}{6}-1\right)-2 \cdot \left(\frac{6(6+1)}{2}-1\right) + 5}{2} \cdot \frac{1}{36} &= 1 \\ \frac{51}{6^3} + \frac{\left((6+1)(12+1)-1\right)-2 \cdot \left(3(6+1)-1\right)+5}{2} \cdot \frac{1}{36} &= 1 \\ \frac{51}{6^3} + \frac{(90)-2 \cdot (20)+5}{2} \cdot \frac{1}{36} &= 1 \\ \frac{51}{6^3} + \frac{(90)-(40)+5}{2} \cdot \frac{1}{36} &= 1 \\ \frac{51}{6^3} + \frac{55}{2 \cdot 36} &= 1 \\ \frac{51}{6^3} + \frac{55}{2 \cdot 36} &=1 \\ \frac{3 \cdot 17}{6^3} + \frac{55}{2 \cdot 36} &=1 \\ \frac{17}{2 \cdot 6^2} + \frac{55}{2 \cdot 36} &=1 \\ \frac{17+55}{2 \cdot 6^2} &=1 \\ \frac{72}{72} &=1 \end{align}

Wow, we've made a big mistake here somewhere!  Yay, I fixed it. 

Note, that the first time I did this, I made a few mistakes. First, I copied the wrong expression in for one of the terms, then I made some algebra and arithmetic mistakes. That's why it's helpful to do these kinds of checks. It is also possible that I could have made such a mistake deriving the expressions themselves instead of in the check combining them.

Let's summarize our result for the attacker.

\begin{align} P(A_1=a_1, A_2=a_2) = \begin{cases} 0 & a_1 < a_2 \\ \frac{3a_1 - 2}{6^3} & a_1 = a_2 \\ \frac{a_2 - 1/2}{36} & a_1 > a_2 \end{cases} \end{align}

Recall the result for the defender.

\begin{align} P(D_1=d_1, D_2=d_2) = \begin{cases} 0 & d_1 < d_2 \\ \frac{1}{36} & d_1 = d_2 \\ \frac{1}{18} & d_1 > d_2 \end{cases} \end{align}

Also, I could use a computer to help me evaluate the expression to confirm that my mistake was in the evaluation and not in deriving the probabilities. A computer simulation could also be helpful, but less conclusive. I draw the distinction as this. You can use a computer to evaluate or to simulate. When you have a computer evaluate, you're using it as a glorified calculator or a plotting tool. Maybe you use it to solve some transcendental equations. If you use a computer to simulate, then you aren't doing much thinking, you're just setting up the problem, running one or more experiments, and hoping the result tells you something both correct and meaningful. Here, though, we can also brute force all the combinations. This is still using the computer like a calculator, but not bothering to simplify before chugging away.

With the probability distributions for both the attacker's and the defender's dice rolls, we can do the comparison and see what the outcome of a round of combat is. In this case there are three outcomes,

1) attacker loses two units,

2) defender loses two units, or

3) attacker and defender each lose one unit.

These cases come from the results of our die rolls.

\begin{align} P(\text{attacker loses two units}) &= P(A_1 \leq D_1, A_2 \leq D_2) \\ P(\text{defender loses two units}) &= P(A_1 > D_1, A_2 > D_2) \\ P(\text{both lose one unit}) &= P(A_1 \leq D_1, A_2 > D_2) + P(A_1 > D_1, A_2 \leq D_2) \end{align}

Note the use of $\leq$, corresponding to the fact that ties go to the defender. Also note that there are two ways that both can lose one unit: attacker can win with the top die and lose with the lower die, and vice versa.  We can compute these by looking at all the cases.

\begin{align} P(A_1 \leq D_1, A_2 \leq D_2) &= \sum_{d_1=1}^6 \sum_{d_2=1}^{d_1} P(A_1 \leq d_1, A_2 \leq d_2) \cdot P(D_1 = d_1, D_2 = d_2) \end{align} \begin{align} P(A_1 \leq d_1, A_2 \leq d_2) = \sum_{a_1=1}^{d_1} \sum_{a_2=1}^{d_2} P(A_1 = a_1, A_2 = a_2) \end{align} \begin{align} P(A_1 \leq D_1, A_2 \leq D_2) &= \sum_{d_1=1}^6 \sum_{d_2=1}^{d_1} \sum_{a_1=1}^{d_1} \sum_{a_2=1}^{d_2} P(A_1 = a_1, A_2 = a_2) \cdot P(D_1 = d_1, D_2 = d_2) \end{align}

Because our expressions for $P(A_1=a_1, A_2=a_2)$ and $P(D_1 = d_1, D_2 = d_2)$ depend on whether $a_1=a_2$ and whether $d_1=d_2$, respectively, we can break up the sum to look at the four cases.

\begin{align} 1: & \quad a_1=a_2 \quad d_1=d_2 \\ 2: & \quad a_1=a_2 \quad d_1>d_2 \\ 3: & \quad a_1>a_2 \quad d_1=d_2 \\ 4: & \quad a_1>a_2 \quad d_1>d_2 \end{align}

We can label the summations related to these cases at $s_1$--$s_4$.

\begin{align} P(A_1 \leq D_1, A_2 \leq D_2) &= s_1 + s_2 + s_3 + s_4 \end{align}

In many of the cases, collapsing some terms to be equal simplifies the summation.

\begin{align} s_1 &= \sum_{d_1=1}^6 \sum_{d_2=d_1}^{d_1} \sum_{a_1=1}^{d_1} \sum_{a_2=a_1}^{a_1} P(A_1 = a_1, A_2 = a_2) \cdot P(D_1 = d_1, D_2 = d_2) \\ &=\sum_{d_1=1}^6 \sum_{a_1=1}^{d_1} P(A_1 = a_1, A_2 = a_1) \cdot P(D_1 = d_1, D_2 = d_1) \\ &=\sum_{d_1=1}^6 \sum_{a_1=1}^{d_1} \left (\frac{3a_1-2}{6^3} \right) \cdot \frac{1}{36} \\ &=\sum_{d_1=1}^6\frac{3 \frac{d_1 \cdot (d_1+1)}{2}-2d_1}{6^5}\\ &=\sum_{d_1=1}^6\frac{\frac{3}{2}d_1^2 -\frac{1}{2}d_1}{6^5}\\ &= \frac{1}{6^5} \cdot \left ( \frac{3}{2}\cdot \frac{6 \cdot (6+1) \cdot (2\cdot 6 +1 )}{6} - \frac{1}{2} \cdot \frac{6 \cdot (6+1)}{2} \right ) \\ &=\frac{6\cdot 7 \cdot 13 - 6 \cdot 7 }{2^2 \cdot 6^5}\\ &=\frac{6\cdot 7 \cdot 2 \cdot 6 }{2^2 \cdot 6^5}\\ &= \frac{7}{2 \cdot 6^3}\\ &\approx 0.0162 \end{align}

Now on to the next term.

\begin{align} s_2 &= \sum_{d_1=1}^6 \sum_{d_2=1}^{d_1-1} \sum_{a_1=1}^{d_1} \sum_{a_2=a_1}^{a_1} P(A_1 = a_1, A_2 = a_2) \cdot P(D_1 = d_1, D_2 = d_2) \\ &=\sum_{d_1=1}^6 \sum_{d_2=1}^{d_1-1} \sum_{a_1=1}^{d_1} P(A_1 = a_1, A_2 = a_1) \cdot P(D_1 = d_1, D_2 = d_2) \\ &=\sum_{d_1=1}^6 \sum_{d_2=1}^{d_1-1} \sum_{a_1=1}^{d_1} \left (\frac{3a_1-2}{6^3} \right) \cdot \frac{1}{18} \\ &=\sum_{d_1=1}^6 \sum_{d_2=1}^{d_1-1}\frac{3 \frac{d_1 \cdot (d_1+1)}{2}-2d_1}{3 \cdot 6^4}\\ &=\sum_{d_1=1}^6 (d_1-1) \cdot \frac{3 d_1^2 -d_1}{6^5}\\ &=\sum_{d_1=1}^6 \frac{3 d_1^3 -4d_1^2+d_1}{6^5}\\ \end{align}

To solve this part, we need to know what the sum of a sequence of cubed terms is.

\begin{align} \sum_{k=1}^n k^3 = \frac{n^2(n+1)^2}{2^2}. \end{align}

I will avoid proving the above, as I did with the previous summations. This is not one I had known existed, but it was easy to find. A proof by induction should work here easily as well.

\begin{align} s_2 &= \frac{3 \cdot\frac{6^2 \cdot 7^2}{2^2} - 4\cdot\frac{6 \cdot 7 \cdot 13}{6} + \frac{6\cdot7}{2}}{6^5}\\ &= \frac{3 \cdot 3^2\cdot7^2 - 4\cdot7\cdot13+3\cdot7}{6^5}\\ &=\frac{2^2\cdot5\cdot7^2}{6^5}\\ &\approx 0.126 \end{align}

Alright, I'm trying to make a point, but this is getting too tiresome. We haven't even completed one of the scenarios! Let's just write a program to run all the cases, there aren't that many, only $6^5=7776$, and then be done with it.

The construction is this: we'll run 5 loops, one for each of the 5 dice, each taking the values from 1 to 6 to cover all possible cases. The first three loops correspond to the attacker's dice, the last two to the defender's dice. Then we sort the values and compare to see which of the three scenarios we end up in. We'll initialize three counters to zero before the loops and use them to keep track of how many times each case occurs. After the loops complete, we can check that they sum to the required 7776 cases as a basic check that we didn't skip any outcomes. From the counts, we can divide by 7776 to get the probabilities of each case.

\begin{align} P(\text{attacker loses two units}) &= \frac{2275}{7776} \approx 0.293 \\ P(\text{defender loses two units}) &= \frac{2890}{7776} \approx 0.372 \\ P(\text{both lose one unit}) &= \frac{2611}{7776} \approx 0.336 \end{align}

As we can see, all three outcomes are quite likely, but the probability that the defender loses two units is the highest, which gives the edge to the attacker.

Note that while I have used a computer to obtain this result (and indeed to compute several values and generate many plots in the past), we have not performed a simulation. That is, we are not limited here by the randomness of the computer and the number of trials run. On the other hand, we've used the same technique as when we first looked at the distribution of 2d6: counting all the cases. This can be an exhaustive tedious method, but in cases where we can make the computer do it for us it is often the most efficient path to a solution. It doesn't necessarily give us a lot of insight here, but neither was all the analysis we did above.

Monday, November 23, 2020

The Haunt Roll in Betrayal Games

I'll get to the Betrayal games in a minute, but let me share some background for how I'm approaching it.

There was a recent question on BoardGameGeek that asked about a mechanic for finding a spy amidst a group of senators. The proposal was to use a bag with 11 tokens, 2 of which are spy tokens, with the remaining 9 being senators. Both spy tokens need to be drawn to find the spy.

I would like the average resolution to be about 6-7 attempts, hopefully landing in the neighborhood of 4-9 attempts, beyond some extreme flukes.

First, let me say that I love the framing here in terms of the desired average and extremes. We can evaluate the mechanic much better with a design criteria as described above.

As to the problem, we can simplify the problem by turning it around, which avoids having to consider the combinatorics of order. This approach is similar to how I've solved the game length in High Society. Let's analyze the problem as if the order the chits is known or determined ahead of time (even though it isn't). The question then becomes, what is the probability that the second spy chit is in round $r$ counting from the front? That's the same as looking for the first spy chit from the back of the line. For the last round,$r=9$, that's easy,

\begin{align} P(r=9) = \frac{2}{11}, \end{align}

as there are 2 spies out of 11 total tokens. Let's count this as round $n=1$ from the back.

\begin{align} P(n=1) = \frac{2}{11} \end{align}

For earlier rounds, we must have drawn all senators "first" (again, we're starting at the back). The probability of drawing a senator in a round $n$ from the back is based on the number of tokens that weren't drawn yet. If we've yet to draw a spy, in round $n$, there are $11-(n-1)=12-n$ total tokens. Two of them are spies, so $12-n-2$ are spies. Thus the probability of drawing a senator in round $n$ (from the back) given no previous spies is as follows.

\begin{align} P(\text{senator in round } n | \text{ no spies in rounds} < n) & = \frac{11 - (n-1) - 2}{11 - (n-1)} \\ &= \frac{10-n}{12-n} \end{align}

So first $\frac{9}{11}$, then $\frac{8}{10}$, and so on. Similarly, the probability of drawing the "first" spy in round $n$ from the back is,

\begin{align} P(\text{spy in round } n | \text{ no spies in rounds} < n) & = \frac{2}{11 - (n-1)} \\ &= \frac{2}{12-n}. \end{align}

We can combine the above in order to get the probability of finding a spy in round $n$. To be able to write the probabilities in a more compact way, such that we can fit our equations on one line, let's make use of the following events.

\begin{align} S_n &= \text{senator in round } n \\ Y_n &= \text{spy in round } n \end{align}

We can rewrite the above probabilities using these events.

\begin{align} P\left(S_n \:\middle\vert\: \bigcap_{i<n} S_i\right) &= P(\text{senator in round } n \mid \text{no spies in rounds} < n)\\ P\left(Y_n \:\middle\vert\: \bigcap_{i<n} S_i\right) &= P(\text{spy in round } n \mid \text{no spies in rounds} < n) \end{align}

Here $\bigcap_{i<n} S_i$ refers to the intersection of all events $S_i$ when $i<n$. Basically, that means $S_1$, $S_2$, $\ldots$, $S_{n-2}$, and $S_{n-1}$ all occur. Note that because senators and spies are mutually exclusive and the only options,

\begin{align} P(Y_n) = 1- P(S_n). \end{align}

Using this more compact notation, we can combine our previous equations to get the total probability of drawing the first spy in round $n$ from the back.

\begin{align} P(Y_n) &= P\left(Y_n \:\middle\vert\: \bigcap_{i<n} S_i\right) \cdot P\left(\bigcap_{i < n} S_i\right) \end{align}

Recall that $P(S_i)$ depends on what was previous drawn, meaning that $S_i$ are not independent. Because of this, we cannot simply break up $P\left(\bigcap_{i < n} S_i\right)$ as a product of the probabilities.

\begin{align} P\left(\bigcap_{i < n} S_i\right) &\neq \prod_{i=1}^n P(S_i) \\ \end{align}

Instead, we use the conditional probabilities that we found earlier.

\begin{align} P(Y_n) &=P\left(Y_n \:\middle\vert\: \bigcap_{i<n} S_i\right) \cdot\prod_{i=1}^n P\left(S_i \:\middle\vert\: \bigcap_{k<i} S_k\right) \\ &= \frac{2}{12-n}\frac{9}{11} \cdot \frac{8}{10} \cdot \ldots \cdot \frac{10-(n-1)}{12-(n-1)} \\ &= \frac{2 \cdot 9 \cdot 8 \cdot \ldots \cdot (10-(n-1))}{11 \cdot 10 \cdot \ldots \cdot (12-n)} \\ &= 2 \cdot \frac{9!}{11!} \cdot \frac{(12-(n+1))!}{(10-n)!} \end{align}

At this point, we can turn things back around to count from the front. We know that $n=1$ is equivalent to $r=11$ and $n=11$ is equivalent to $r=1$. From this we can write the equations defining the relationship between the number of rounds from the front, $r$, and the number of rounds from the back, $n$.

\begin{align} n = 12-r \end{align}

Thus the probability of finding the spy chit in round $r$ is as follows.

\begin{align} P(\text{spy revealed in round } r) &= P(Y_{12-r}) \\ &= 2 \cdot \frac{9!}{11!} \cdot \frac{(12-(12-r+1))!}{(10-(12-r))!}\\ &= 2 \cdot \frac{9!}{11!} \cdot \frac{(r-1)!}{(r-2)!} \\ &= 2 \cdot \frac{9!}{11!} \cdot (r-1) \\ &= \frac{2}{11\cdot 10} \cdot (r-1) \end{align}

The result of this equation is shown in Figure 1, which shows a linearly increasing probability as each new token is drawn, starting with a probability of 0 in round 1. This makes sense, as the second spy token must be drawn to actually find the spy. A numerical check confirms that the values for all value $r$ sum to 1. As clearly shown in the plot, this favors the last rounds, which does not match the desired properties.

Figure 1: Probability of finding the spy

Now, let's turn to the haunt roll mechanics found in the various Betrayal games, including Betrayal at the House on the Hill, Betrayal at Balder's Gate, Betrayal Legacy, and Betrayal at Mystery Mansion. We'll actually set the legacy version aside, as the legacy aspects of the game can influence the roll.

In the original game (Betrayal at the House on the Hill), each time an omen is drawn the active player rolls 6 dice and if the result is less than the number of omen cards then the haunt starts (the example in the rulebook actually says equal to or less than number of omen cards, which I'll assume is an error). The dice in all betrayal games are the same: custom six-sided dice with two sides each of 0, 1, and 2. This means the probability mass function (pmf) of each die is $1/3$ for values on the dice, and $0$ elsewhere. We'll denote the result of one of the betrayal dice as a random variable $D$ with pmf $f_D(d)$.

\begin{align} f_D(d) = \begin{cases} \frac{1}{3} \quad & d \in {0, 1, 2} \\ 0 \quad &\text{else} \end{cases} \end{align}

We can get the pmf of the entire hunt roll of six dice, $f_H(h)$ by convolving the pmf of each die with itself enough times to account for the six dice that a player rolls.

\begin{align} f_H(h) = f_D(h) * f_D(h) * f_D(h) * f_D(h) * f_D(h) * f_D(h) \end{align}

Because convolution is associative, we don't have to worry about the order of the convolutions. The result is shown in calculation in Figure 2. We get what we expect after convolving a reasonable number (even if it is only six here) of independent identically distributed (i.i.d.) random variables, which is a roughly Gaussian, or normal-looking distribution.  (Due to the Central Limit Theorem. There are probably some comments I should be making about whether them being identically distributed matters here, but I'll omit them for ease and brevity.) We expect a minimum value of 0 and maximum value of 12, each corresponding to the extreme values on all dice. These are possible, but with low probability. The distribution is also symmetric.

Figure 2: Probability mass function of haunt roll

By computing the cumulative distribution (CDF) of the haunt roll result, $F_H(h)$, we can easily compute the probability that the haunt starts in any given round. Finding the CDF is a straightforward computation based on the pmf.

\begin{align} F_H(h) &= P(H \leq h) \\ &= \sum_{i=0}^h f_H(i) \end{align}
Figure 3: Cumulative distribution function of haunt roll

Note that here, the minimum possible value on a haunt roll is 0. The resulting CDF is plotted in Figure 3. Because the haunt starts whenever the haunt roll is less than the number of omens drawn, the probability of a haunt being triggered when making a haunt roll is equal to the CDF evaluated at one less than the number of omens, $o$.

\begin{align} P(\text{haunt starts} \mid o \text{ omens}) = F_H(o-1) \end{align}

The next step is to assemble the probability distribution of the number of omens drawn before the haunt starts. We use the distribution of the haunt roll to do this, noting that we only consider drawing more omens if the haunt starts. Therefore, the probability that the number of omens when the haunt starts, $O$, is 1 is equal to the probability that we roll less than 1 on the first haunt roll.

\begin{align} f_O(1) &=P(O=1)\\ &= F_H(1-1)\\ & = F_H(0)\\ &=f_H(0)\\ &=f_D(0)^6\\ & \left( \frac{1}{3} \right)^6 \\ &\approx 0.00137 \end{align}

In this case, as shown above, the probability shakes out to the probability of rolling 0 on all six haunt dice, which occurs with a probability of about 0.00137.

When looking at the probability that $O>1$, we must consider the result of all previous haunt rolls. That is, we only make a haunt roll with $o$ omens, where $o>1$, if all previous haunt rolls failed to start the haunt.

\begin{align} P(\text{make haunt roll with $o$ omens}) &= 1 - P(O < o)\\ &= 1- F_O(o-1)\\ & 1 - \sum_{i=0}^{o-1}f_O(i) \end{align}

This gives us an equation to compute the distribution of $O$ where we can compute each term one at a time, using the one term to compute the next.

\begin{align} f_O(o) &= \left ( 1 - \sum_{i=0}^{o-1}f_O(i) \right) \cdot F_H(o-1) \end{align}

Now that we've gone all the way through this exercise, we can turn to the other versions of the game. Betrayal and Balder's Gate and Betrayal at Mystery Mansion both function similarly (though the latter game uses the term clue instead of omen, it functions the same). Instead of rolling a constant number of dice and adjusting the target number, the number of dice rolled is equal to the number of omen cards drawn and a constant target number is used. In Balder's Gate, if the haunt roll is 6 or higher the haunt starts, whereas Mystery Mansion uses a threshold of 5 or higher.

To compute the distribution of dice, we can use a similar method as above, but varying the number of haunt dice pmfs which are convolved. The resulting pmfs and CDFs are plotted in Figures 4 and 5.

Figure 4: Probability mass function of haunt roll by omen

Figure 5: Cumulative distribution function of haunt roll by omen

We can reuse the same equation to find the pmf and CDF of the number of omens drawn before the haunt starts for the three games, which are plotted in Figures 6 and 7. We can note a couple differences. Most evident is that each iteration on the game tends to make the haunt start sooner, as shown most clearly in the CDFs. Second, the possibility of a very early haunt with the original game, with only 1 or 2 drawn, has been completely eliminated in Balder's Gate and Mystery Mansion. For the later games, rolling one or two dice is insufficient to get a sum or 5 or 6 to trigger the haunt. On the other hand, these games have a non-zero probability of an arbitrarily long game according to the probabilities shown. Mystery Mansion has a special rule that the haunt always starts after the 9th omen (clue) card is drawn.

Figure 6: Probability of triggering the haunt when drawing current omen

Figure 7: Cumulative probability of triggering the haunt

We could modify the dice so that they naturally provide both an upper and lower bound, as originally desired for the spy search mechanism, by using a similar mechanism to the later Betrayal games but having a non-zero minimum value on the dice. Doing this sets a maximum number of turns needed for the search, equal to the ratio between the target sum and the minimum value on the dice.

Recall that we want between 4 and 9 searches, averaging 6-7. Let's use a minimum value of 1 on the dice and decide on the number of values to include to achieve the properties above. With a minimum of 1 and max 9 rounds, the target sum must be 9. To prevent 3 searches from being successful, there must be at most 2 sides on the dice. This gives the distributions functions shown in Figures 8 and 9. While these center more on 6 searches, they demonstrate the feasibility of this type of mechanism. The particular type of dice and target numbers can be adjusted to get the desired probability properties.

Figure 8: Probability of finding the spy in the current round (pmf)

Figure 9: Cumulative probability of finding the spy by round (CDF)