# The Ultimate Battle of two players

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.

## 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. 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).

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.

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.