14
$\begingroup$

The Ultimate Battle is a turn-based two-player game.

Player $i$ (1 or 2) has three stats: initial hit point $P_i$, attack $A_i$, and heal $H_i$. The values can differ between players. All values are positive integers.

When the game begins, player 1 has hit point $P_1$ and player 2 has $P_2$. Player 1 plays first. On player $i$'s turn, they can choose either to attack or heal. If they attack, the opponent's hit point is reduced by $A_i$. If they heal, their own hit point increases by $H_i$. At any point, a player wins if the opponent's hit point is 0 or lower. There is no upper limit for players' hit points; specifically, they can go above the initial hit points.

Both players play optimally: if they can win, they always make a move that leads to a win; otherwise, they make a move that leads to an infinite game if possible. Identify the condition for each player to win.

$\endgroup$

2 Answers 2

12
$\begingroup$

Solution

Define the recovery ratios $R_i$ for player $i$ $$R_1 = \frac{H_1}{A_2} \text{ and }R_2 = \frac{H_2}{A_1}$$ and the "turns-to-die" $T_i$ for player $i$ $$T_1=\Big\lceil\frac{P_1}{A_2}\Big\rceil \text{ and } T_2 = \Big\lceil\frac{P_2}{A_1}\Big\rceil.$$

A trivial case when player $1$ wins is $A_1 > P_2.$ We will ignore this case in further discussions.

Also define the dominating attack conditions $D_1$ a (true/false value) $$D_1=\big( T_1\ge T_2\big),$$ and $D_2 = \text{ not }D_1$.

Then the result can be summarised by the following table (subscript indicates the part of the proof)

$$ \begin{array}{c|c|c|c} R_1 \backslash R_2 & >1 & =1 & <1 \\ \hline\\ >1 & \infty_{a} & \infty_{a} & 1_{b} \\ \hline\\ =1 & \infty_{a} & \infty_{a} & \begin{array}{} D_1\Rightarrow 1_c\\ D_2\Rightarrow \infty_b \end{array} \\ \hline\\ <1 & 2_{b} & \begin{array}{} D_1\Rightarrow \infty_c\\ D_2\Rightarrow 2_c\end{array} & \begin{array}{} D_1\Rightarrow 1_a\\ D_2\Rightarrow 2_a\end{array} \end{array} $$

Reasoning

The trivial case of $A_1 > P_2$ leads to player $1$'s win on the first move. As above, we will ignore this case in the following.

The part $\infty_a$ is clear, because if both players' recovery ratios are $\ge 1$, then no persistent decrease in the hit-points of either player can be made.

The part $1_a$: If $R_1 < 1 \text{ and } R_2 < 1$, then no player should choose to heal. Since it takes $T_i$ hits to kill player $i$, we have that player $1$ wins if and only if $T_1\ge T_2$.

Symmetry in $1_a$ also proves $2_a$.

The part $1_b$ (see the Appendix as to why this part is so complex): Let $R_1 > 1 \text{ and } R_2 < 1$. Note that an infinite game is not possible, so if player $1$ does not win, then player $2$ must win. Notice that player $2$ is strictly worse if it does the opposite action as player $1$. If $D_1$ is not satisfied at the beginning of the game, player $1$ will heal (and force player $2$ to heal). The condition to have $D_1$ (on player $1$'s turn) eventually is $$\Big\lceil \frac{P_1 + nH_1}{A_2}\Big\rceil\ge \Big\lceil\frac{P_2+nH_2}{A_1}\Big\rceil$$ for some $n$. Since $R_1=\frac{H_1}{A_2}>1$ and $R_2=\frac{H_2}{A_1}<1$, the left hand side will increase faster than the right hand side. When this happens, player $1$ will start always attacking (and force player $2$ to attack) and win according to $1_a$.

Symmetry in $1_b$ also proves $2_b$.

Edge cases

It remains to check the cases when one of $R_i$ is $1$ and the other is $<1$. Essentially, the solution is the same as that of $R_1 < 1 \text{ and } R_2 < 1$, except the player with $R_i = 1$ can force an infinite game by healing (thank you @Tom Sirgedas for this concise summary).

Part $1_c$: If $R_1=1$ and $R_2<1$ and $D_1$, then player $1$ will win the game by constantly attacking, according to arguments in $1_a$ and $1_b$.

Part $\infty_b$: If $R_1=1$ and $R_2<1$ and $D_2$, then player $1$ cannot win immediately by attacking, according to arguments in $1_a$. Notice that player $1$ can guarantee that it will not lose. But if player $1$ attempts to heal, then player $2$ will attack, bringing everything to where we started. So the game is infinite.

Part $2_c$: If $R_1<1$ and $R_2=1$ and $D_2$, then player $1$ will not heal to start, because then player $2$ will attack, and player $1$ is strictly worse. So player $1$ must attack and lose to an all-attack battle due to $D_2$.

Part $\infty_c$: If $R_1 < 1$ and $R_2 = 1$ and $D_1$, then player $2$ can guarantee to not lose. As in part $(2.3)$, player $1$ will not heal to start. But when player $1$ attacks, then player $2$ will heal, which brings everything back to the beginning.

Appendix

To see why part $1_b$ is so complex, consider the following example:

$$\begin{array}{c|rr} & 1 & 2\\ \hline H & 10 & 50 \\ A & 51 & 9 \\ P & 10 & 1000 \\ \end{array} $$

where $R_1=10/9>1$ and $R_2=50/51<1$ but $H_1<H_2$. Obviously player $1$ cannot lose because $R_1>1$, though it is not intuitive that player $1$ can win by healing, as the opponent can heal five times more per turn and has a huge lead in HP. However, the condition in the proof is still satisfied as $$\Big\lceil \frac{10 + 10n}{9}\Big\rceil\ge \Big\lceil\frac{1000+50n}{51}\Big\rceil$$ is satisfied if $n\ge 142$ (I ignored the ceiling functions to make calculations easier).

$\endgroup$
9
$\begingroup$

If $A_1>P_2$, player 1 wins on their first turn.

Otherwise,

Let's categorize both players.

$$ \text{A player is} \begin{cases} \text{an }\textbf{over-healer} & \text{if their heal is greater than the opponent's attack} \\ \text{an }\textbf{exact-healer} & \text{if their heal is equal to the opponent's attack} \\ \text{a }\textbf{bad-healer} & \text{if their heal is less than the opponent's attack} \\ \end{cases} $$

Then, the outcome of the battle is

$\begin{array}{|c|c|c|} \hline \text{} & \text{Player 1 is over-healer} & \text{Player 1 is exact-healer} & \text{Player 1 is bad-healer} \\ \hline \text{Player 2 is over-healer} & \text{Draw} & \text{Draw} & \text{Player 2 wins} \\ \hline \text{Player 2 is exact-healer} & \text{Draw} & \text{Draw} & \text{Special Scenario} \\ \hline \text{Player 2 is bad-healer} & \text{Player 1 wins} & \text{Special Scenario} & \text{Fight Scenario} \\ \hline \end{array}$

Notes:

  • Only bad-healers can be forced to lose.
  • Healing is never helpful for a bad-healer (the opponent can reply with an attack), so we can assume that a bad-healer always attacks.

Scenario details:

If neither player is a bad-healer: (Draw)
Neither player can force a win. The battle will be a Draw.

bad-healer vs bad-healer: (Fight Scenario)
Player 1 requires $W1=\lceil\frac{P_2}{A_1}\rceil$ attacks to win.
Player 2 requires $W2=\lceil\frac{P_1}{A_2}\rceil$ attacks to win.
If $W1 \leq W2$, player 1 wins, otherwise player 2 wins.

Over-healer vs bad-healer: (over-healer wins)
The bad-healer never heals, and the over-healer has effectively unlimited hit points by healing. The over-healer can safely attack whenever their hit points exceed the opponent's attack. The over-healer wins.

Exact-healer vs bad-healer: (Special Scenario)
The result is the same as the bad-healer vs bad-healer scenario, except that this time exact-healer has the option to force a draw by always healing.

$\endgroup$
5
  • 4
    $\begingroup$ What about the case where (A,H,P) of (5,0,5) and (4,5,6). Player 1 is not invincible because he cannot outheal Player 2. Player 2 is invincible because Player 1 cannot kill him (but not sure if this is necessarily "Outheal"). However, Player 2 does not have the tempo to defeat Player 1. $\endgroup$
    – LeppyR64
    Commented May 28 at 14:33
  • 1
    $\begingroup$ Good catch. That's a special case I'm not currently handling. $\endgroup$ Commented May 28 at 14:48
  • 1
    $\begingroup$ I fixed it, but now I think it's just a less formal version of Benjamin Wang's answer. $\endgroup$ Commented May 28 at 17:55
  • 1
    $\begingroup$ There's value in the simplicity if it's accurate. I haven't even read Benjamin's whole answer yet. $\endgroup$
    – LeppyR64
    Commented May 28 at 19:53
  • 1
    $\begingroup$ @TomSirgedas thank you for your answer which inspired me to make mine neater and more symmetrical! I added an Appendix to my answer which explains why the over-healer vs bad-healer scenario may not be as intuitive as one might think. $\endgroup$ Commented May 29 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.