# A Truel - Exit Probability

Survival game: Consider $3$ players, $A, B$ and $C$, taking turns shooting at each other. Any player can shoot at only one opponent at a time (and each of them has to make a shot whenever it is his/her turn).

Each shot of $A$ is successful with probability $1/3$, each shot of $B$ is successful with probability $1$, and each shot of C is successful with probability $1/2$ (with all the outcomes being independent).

$A$ goes first, then $B$, then $C$, then $A$, and so on, until one of them dies. Then, the remaining two will be shooting at each other, so that nobody ever makes two shots in a row: e.g. if $A$ gets $C$ shot, then $B$ goes next.

The game continues until only one player is left. Assume that every player is trying to find a strategy that maximises his/her probability of survival. Assume also that every player acts optimally and knows that the other players will act optimally too.

Who should player A shoot at first? What is the probability of survival of $A$ (assuming he/she acts optimally)?

*Hint. A strategy is a sequence of decisions on who to shoot at at any given turn, given who is still left in the game. It is clear that, after $B$ shoots for the first time, there will be at most two players left, and, hence, for the remaining players, there will be no need to make any choices. Therefore, it is convenient to solve the problem recursively, starting from the decision of $B$, and assuming that all players are alive by the time $B$ shoots (otherwise, again, there are no decisions for $B$ to make).

It is clear that, given a choice between $A$ and $C$, $B$ will shoot at $C$, because playing against $A$ only will give $B$ a higher probability of survival than playing against $C$ only (i.e. $2/3$ vs. $1/2$). Knowing this, A needs to choose whether it is optimal to shoot at $B$ or at $C$. Considering the possible outcomes produced by each of the two choices, you will notice that, in one case, the survival probability can be computed by hand, and, in the other case, it can be reduced to the computation of an exit probability of a simple Markov chain.

My trial:

1. if $A$ shoots $C$: $P$($A$ hits $C$ *$B$ misses $A$ * $A$ hits $B$) + $P$ ($A$ misses $C$ * $B$ hits $C$ * $A$ hits $B ) = 0 +1/3*1*1/3 = 1/9$

2. if $A$ shoots $B$: $P$($A$ hits $B$ *$C$ misses $A$ * $A$ hits $C$) + $P$ ($A$ misses $B$ * $B$ hits $C$ * $A$ hits $B ) = 1/3*1/2*1/3 +2/3*1*1/3 = 5/18$

So A should shoot B, is it correct?

• en.wikipedia.org/wiki/Truel – Marcus Andrews Feb 10 '17 at 17:58
• There is a third option for $A$ that turns out to be optimal. – Arthur Feb 10 '17 at 18:20
• @Arthur You mean A shoule shoot into the air right? But from what's written in the hint I don't think the problem counts that as an option. – Betty Feb 10 '17 at 18:29
• It's clearly the optimal choice. None of the other strategies have $1/3$ probability of $A$ winning. But maybe that's too outside the box for whoever wrote this specific problem. – Arthur Feb 10 '17 at 18:37
• @MarcusStuhr Thank you for your efforts! – Betty Feb 10 '17 at 21:38

It has already correctly been noted that the best strategy for $A$ in this game - assuming no possibility of shooting into the air - is to begin by shooting at $B$. I would add some details on this.

The case in which $A$ decides to shoot at $C$ is relatively simple, since the only possibility for him to survive is to fail the first shot to $C$, to wait for $B$ killing $C$, and to have success in his second shot to $B$. Because $B$ does not fail, in this case there are no other possibilities for $A$ to survive: this directly leads to a probability of $2/3 \cdot 1 \cdot 1/3 =2/9 \,\,\,\,$ (note that for this case there is a typo in the OP, which reports a probability of $1/9 \,$).

The case in which $A$ decides to shoot at $B$ is a bit more complex. Since the game continues until only one player is left, in the first subcase, that where $A$ kills $B$, the possibilities for $A$ to survive in the subsequent shots between $C$ and him include any successive sequence of failures that ends with a successful shot by $A$. Calling $P_n$ the probability of occurrence for a sequence of this type that ends with a successful $n^{th}$ shot by $A$, we have

\begin{align*} P_1= & \frac {1}{2} \cdot \frac {1}{3}\\ P_2= & \frac {1}{2}\cdot \left( \frac {2}{3} \cdot \frac {1}{2} \right) \cdot \frac {1}{3}\\ P_3= &\frac {1}{2}\cdot \left( \frac {2}{3} \cdot \frac {1}{2} \right) \cdot \left ( \frac {2}{3} \cdot \frac {1}{2} \right) \cdot \frac {1}{3} \end{align*}

and so on (here $n$ does not include the initial shot of $A$ to $B$). So we get the sum

$$\sum_{k=0}^\infty \, \frac {1}{2} \cdot \left(\frac {2}{3} \cdot \frac {1}{2} \right)^k \cdot \frac {1}{3} \\ = \sum_{k=0}^\infty \, \frac {1}{6} \cdot \left(\frac {1}{3} \right)^k =\frac {1}{4}$$

Multiplying this to $\frac {1}{3}$ (probability that in the initial shot $A$ kills $B$), we get for this first subcase a survival probability of $\frac {1}{12}$.

The second subcase, that where $A$ shoots at $B$ but misses him, is again rather simple. The only possibility of $A$ to survive in this subcase is to wait for $B$ killing $C$, and then to kill $B$ in the successive shot. This can occur with probability $2/3 \cdot 1 \cdot 1/3=2/9\,\,\,\,$.

Collecting these results we have that, in the case in which $A$ decides to begin by shooting at $B$, his survival probability is $$\frac {1}{12} + \frac {2}{9} = \frac {11}{36}$$

This problem has appeared in 'the literature' before. If one assumes that each player is allowed to miss deliberately at any time, then A can do better by deliberately missing his first shot. Analysis of this action is just like analysis of A initially shooting at C, except the case where A kills C is avoided; this raises A's probability of survival to a full 1/3.