Probability that a character kills the boss in a 3 versus 1 fight

In a RPG game, your three characters A, B and C fight a boss. The boss has $1000$ hp. The attacks are sequential: A attacks then B attacks then C attacks then A attacks again, etc. Character A can do any integral amount of damage between $25$ and $50$ with equal probability. Character B can do any integral amount of damage between $30$ and $70$ with equal probability. Character C can do any integral amount of damage between $10$ and $80$ with equal probability. Assuming that the boss is not strong enough to kill any of the characters before it dies, what is the probability that player A will be the one to deliver the final blow and kill the boss? Same question for players B and C.

Unfortunately I don't even know how to get started on this problem, any hint would be helpful.

Solution 1:

Here's a way to think about it: imagine initializing a "total damage counter" as $D_0=0$, and on the $n$th turn, when $d_n$ damage is done to the boss, increment it to $D_n=D_{n-1}+d_n$ and color the interval $(D_{n-1},D_n]$ according to which player attacked. If we allow this to continue forever, it will color the whole number line with a random pattern of three colors.

Notice that the player who kills the boss is the one whose color covers the point 1000. Since this point is far away from 0, we can think of it as being randomly aligned with our color pattern, so it's as though we're picking a random point on the number line and asking what color it is. This only depends on the ratio of paint colors that our pattern uses, and (by the law of large numbers) this is approximately just the ratio among the expected values of the players' attacks. So e.g. the probability that player A kills the boss is about $37.5/(37.5+50+45)$.

Solution 2:

I think this problem can only be solved either approximately (asympotically exact) or numerically. Karl's approximation is the most natural answer, and I'd go for it. If you instead want an exact result, here's an efficient numerical procedure (computer assisted, though).

Letting $g_A(n)$ be the probability that player $A$ wins given that the boss has power $n$, we have the recursion

$$ g_A(n) = \sum_{j=n}^\infty p_A(j) + \sum_{j=1}^{n-1} p_{ABC}(j)g_A(n-j)$$

where $ p_A(j)$ is the probability mass function of the damage inflicted by player $A$ and $p_{ABC}(j)$ is the same for the three players summed.

Solved numerically in Octave (or Matlab) this gives

$$g_A(1000) = 0.28347$$ pretty near Karl's approximation ( $0.28302$)

The graph shows that that approximation is quite good after $N\approx 900$

Code:

pa = [1:100];
pa = pa >= 25 & pa <= 50;
pa = pa/sum(pa);
pb = [1:100];
pb = pb >= 30 & pb <= 70;
pb = pb/sum(pb);
pc = [1:100];
pc = pc >= 10 & pc <= 80;
pc = pc/sum(pc);
pab = [0, conv(pa,pb)];
pab = [0, conv(pa,pb)];
pac = [0, conv(pa,pc)];
pbc = [0, conv(pb,pc)];
pabc = [0, conv(pab,pc)];
N=1000;
pabc(N)=0;
ga = zeros(1,N);
ga(1)=1;
for n=2:N
  ga(n) = sum(pa(n:100)) +  flip(ga(1:n-1)) * pabc(1:n-1)';
endfor
ga(N)

For completeness, here are the other probabilities

gb = zeros(1,N); % prob of B winning, if B has next turn
gb(1)=1;
 for n=2:N
 gb(n) = sum(pb(n:100)) +  flip(gb(1:n-1)) * pabc(1:n-1)';
endfor
gbb=zeros(1,N);  % prob of B winning, if A has next turn
pa(N)=0;  % extend pa size
for n=2:N
 gbb(n)= flip(gb(1:n-1)) * pa(1:n-1)';
endfor
gcc = 1 - (ga+gbb);

Notice that the period of the quasioscillations is around the mean value of the whole turn : $(25+50+30+70+10+80)/2 = 132.50$

Solution 3:

Here is yet an other answer, targeting the exact fractions that give the needed probabilities, it combines simple combinatorics and simple coding (sage is my weapon of choice), based on the fact that there is a (very) limited amount of complete turns $N$ till the total of $1000$ points can be randomly reached.

The player $A$ wins in a situation like $(ABC)^N\;A$, i.e. there are $N$ complete turns, then $A$ plays and the total sum of points so far is for the first time $\ge 1000$. We denote by $P(A,N)$ this probability.

Similarly, $B$ wins in a situation like $(ABC)^N\; AB$, and we denote by $P(N,B)$ the corresponding probability, and $C$ wins with the remained probability, but for the check, let this be in a situation like $(ABC)^N\; ABC$, and we denote by $P(N,C)$ the corresponding probability.

Now we compute. The first one who can win is $C$, since $5(50+70+80)=1000$, but the corresponding probability $$ P(5,C)= {\underbrace{\left(\frac 1{26}\right)}_p\ }^5 {\underbrace{\left(\frac 1{41}\right)}_q\ }^5 {\underbrace{\left(\frac 1{79}\right)}_r\ }^5 $$ is tiny. We have denoted by $p=1/26$,$q=1/41$, $r=1/79$ the corresponding probabilities for each individual result for $A$, $B$, respectively $C$. After this warming up, let us start.

Now let $N$ be fixed (between $4$ and $15$). Consider the polynomials (possibly taken modulo $x^{1001}$): $$ \begin{aligned} Q_A &= p(x^{25}+\dots+x^{50})\ ,\qquad Q_A(1) =1\ ,\\ Q_B &= q(x^{30}+\dots+x^{70})\ ,\qquad Q_B(1)=1\ ,\\ Q_C &= r(x^{10}+\dots+x^{80})\ ,\qquad Q_C(1)=1\ ,\\[3mm] % F_A(N) &= Q_A^N\; Q_B^N\; Q_C^N\ ,\\ F_B(N) &= Q_A^{N+1}Q_B^N\; Q_C^N\ ,\\ F_C(N) &= Q_A^{N+1}\; Q_B^{N+1}\; Q_C^N\ ,\\[3mm] % &\qquad\text{ and isolate relevant coefficients:}\\ F_A(N) &= \dots + a_{950} x^{950} + a_{951} x^{951} + a_{999} x^{999} + \dots\\ F_B(N) &= \dots + b_{930} x^{930} + b_{931} x^{931} + b_{999} x^{999} + \dots\\ F_C(N) &= \dots + c_{920} x^{920} + c_{921} x^{921} + c_{999} x^{999} + \dots\qquad \ . \end{aligned} $$ Above, the $a$, $b$, $c$ - coefficients in some degree $k$ are probabilities to reach $k$ short before being self on fire. Then the probability to get on or over $1000$ after turn $N$ for $A,B,C$ is respectively $$ \begin{aligned} P_A(N) &= p(a_{950} + 2a_{951} + 3a_{952} + \dots + 25 a_{974}) \\ &\qquad\qquad+ ( a_{975} + a_{976}+\dots+a_{999})\ , \\[2mm] P_B(N) &= q(b_{930} + 2b_{931} + 3b_{932} + \dots + 40 b_{969}) \\ &\qquad\qquad+ ( b_{970} + b_{971}+\dots+b_{999})\ , \\[2mm] P_C(N) &= r(c_{920} + 2c_{921} + 3c_{922} + \dots + 70 a_{974}) \\ &\qquad\qquad+ ( c_{990} + c_{991}+\dots+c_{999})\ . \end{aligned} $$ These sums can be calculated. Let us get the explicit fractions.

p, q, r = 1/26, 1/41, 1/71
R.<x> = PowerSeriesRing(QQ, default_prec=1001)
QA = p*sum([x^k for k in [25..50]]) 
QB = q*sum([x^k for k in [30..70]])
QC = r*sum([x^k for k in [10..80]])
Q = QA * QB * QC + O(x^1000)

def PA(N):
    QAN = Q^N + O(x^1000)
    return p * sum([ (k-949) * QAN.dict().get(k, 0) for k in [950..974]]) + \
               sum([           QAN.dict().get(k, 0) for k in [975..999]]) 
           
def PB(N):
    QBN = Q^N * QA + O(x^1000)
    return q * sum([ (k-929) * QBN.dict().get(k, 0) for k in [930..969]]) + \
               sum([           QBN.dict().get(k, 0) for k in [970..999]]) 
           
def PC(N):
    QCN = Q^N * QA * QB + O(x^1000)
    return r * sum([ (k-919) * QCN.dict().get(k, 0) for k in [920..989]]) + \
               sum([           QCN.dict().get(k, 0) for k in [990..999]]) 
           
pa = sum([PA(N) for N in [0..16]])
pb = sum([PB(N) for N in [0..16]])
pc = sum([PC(N) for N in [0..16]])

print(f"p_A &= {latex(pa)}\\\\&\\approx {pa.n(200)}\\ ,\\\\[2mm]")
print(f"p_B &= {latex(pb)}\\\\&\\approx {pb.n(200)}\\ ,\\\\[2mm]")
print(f"p_C &= {latex(pc)}\\\\&\\approx {pc.n(200)}\\ .")

Let us print the obtained values explicitly in an aligned block: $$ \begin{aligned} p_A &= \frac{334033901864090379613127803175076008061329503244624264537089105546493539}{1178392443307351590334920499763343901461744782823432598226397490500042752}\\&\approx 0.28346575350277151214602996031038557893379483738585896702069\ ,\\[2mm] p_B &= \frac{6309830943686662816904113123282509708706840969580727479884347191047819}{16597076666300726624435499996666815513545701166527219693329542119718912}\\&\approx 0.38017724871382680616769939159810617375709726053541809298534\ ,\\[2mm] p_C &= \frac{604208147014494132197561989078063573296081662711244943014511790227369}{1796329944066084741364208078907536435155098754304013107052435198932992}\\&\approx 0.33635699778340168168627064809150824730910790207872293999396\ . \end{aligned} $$

$\square$

A final check:

sage: pa + pb + pc
1

Solution 4:

This problem can be modelled as a Markov chain and we can use known results about hitting probabilities to calculate the exact answer. I will first explain how to model it as a Markov chain and then give the exact answer as implementation in matlab.

Let $S$ denote the set of states: For each player $P$ and each possible HP value $x$ of the boss (between $0$ and $1000$) we add the state ($P$, $x$) to $S$ (note that $0$ is representative of any HP value less or equal to $0$ here). The random variable $X_i$ is the state of the system after $i$ rounds. The state transition probabilities (i.e. the probability $P[X_{i + 1} = (P, x) | X_i = (P', x')]$) are now given by the problem description.

As an example, assume we know already that $X_i = (A, 1000)$ and we want to compute the (conditional) probability that $X_{i + 1} = (B, x)$. Since $A$ can do damage between $25$ and $50$ we have that $P[X_{i + 1} = (B, x) \, | \, X_i = (A, 1000)] = \frac{1}{26}$ for $x \in \{950, \dots, 975 \}$ and it is $0$ for other values of $x$. Of course, the probability of reaching any state with player $C$ next is $0$.

The hitting probability of a state $(P, x) \in S$ is the probability that we ever reach $(P, x)$ in this random process. Thus the hitting probability of the state $(A, 0)$ is exactly the probability that $C$ delivered the killing blow. Similarly, the hitting probability of $(B, 0)$ and $(C, 0)$ are the probabilities of $A$ and $B$ respectively delivering the killing blow.

These probabilities can be computed as the solution of a linear system of equations. I have coded this up in matlab, see below. States are represented as numbers from $1$ to $3003$. If a state $s$ satisfies $s =_3 0$ it is a state where $A$ attacks next. Similarly, $B$ and $C$ are associated with states in residue classes $1$ and $2$ respectively.

The HP of the boss in state $s$ is encoded as $ \lceil s / 3 \rceil - 1$. For example, state $3003$ is a state where $A$ attacks next and where the boss has $1000$ hitpoints.

Matlab has a built-in function for finding hitting probabilities which I use here. If you run the code below, it will tell you that we get probabilities $0.2835, 0.3494, 0.3671$ for players $A, B$ and $C$ respectively.

Let me know if you have any questions.

% build transition matrix P for N hitpoints
N = 1000;
P = zeros(3*(N + 1), 3*(N + 1));
% states 1, 2, 3 are endstates (i.e. random process loops there)
for i = 1:3
    P(i, i) = 1;
end
% all other transitions
for i = 4:(3*(N + 1))
    % player A
    if mod(i, 3) == 0
        for j = 25:50
            P(i, max(2, i - 1 - (3 * j))) = P(i, max(2, i - 1 - (3 * j))) + 1/26;
        end
    % player B
    elseif mod(i, 3) == 1
        for j = 30:70
            P(i, max(1, i + 2 - (3 * j))) = P(i, max(1, i + 2 - (3 * j))) + 1/41;
        end
    % player C
    else
        for j = 10:80
            P(i, max(3, i - 1 - (3 * j))) = P(i, max(3, i - 1 - (3 * j))) + 1/71;
        end
    end
end
% build markov chain from transition matrix
mc = dtmc(P);
% find hitting probabilities for player A, B, C
C = hitprob(mc, 1);
A = hitprob(mc, 2);
B = hitprob(mc, 3);
% output
A(3*(N+1))
B(3*(N+1))
C(3*(N+1))