Search Monster Battle Strategies

Problem Statement

You are designing an AI agent for a turn-based combat game. You control a player character fighting against a boss. Both combatants act in sequential turns until one is defeated. You must determine the minimum number of turns required for the player to defeat the boss, or return -1 if it is impossible to win.

Rules of Engagement

1. Initial State:

   • The boss starts with boss_hp health.
   • The player starts with player_max_hp health.
   • The player possesses exactly one single-use revive item.

2. Turn Order: Each turn t (0-indexed, starting at t = 0):

   • Player Action: The player chooses exactly one move from a given list of moves. Each move is represented as a tuple (damage, heal):
     • The boss takes damage damage.
     • The player heals by heal HP, capped at player_max_hp.
     • If the boss's HP drops to <= 0, the player immediately wins, and the total turns taken is t + 1.
   • Boss Action: If the boss survives, the boss attacks, dealing boss_attacks[t % len(boss_attacks)] damage to the player.
   • Revive Check: If the player's HP drops to <= 0:
     • If the player has not yet used their revive, the revive is consumed, and the player's HP is immediately set to revive_hp.
     • If the player has already consumed their revive, the player is defeated and this state cannot be explored further.

Find the optimal strategy (minimum turns to win) across all possible sequences of valid actions.

Function Signature

def min_turns_to_defeat(
    boss_hp: int,
    player_max_hp: int,
    revive_hp: int,
    boss_attacks: list[int],
    moves: list[tuple[int, int]]
) -> int:
    pass

Constraints

• 1 <= boss_hp <= 150
• 1 <= player_max_hp <= 100
• 1 <= revive_hp <= player_max_hp
• 1 0 or heal > 0.

Examples

Example 1

Input:
boss_hp = 30
player_max_hp = 20
revive_hp = 10
boss_attacks = [15, 10]
moves = [(10, 0), (0, 8)]

Output: 3
Explanation:
- Turn 0: Player attacks (10 dmg -> Boss HP: 20). Boss attacks for 15 dmg (Player HP: 5).
- Turn 1: Player heals (+8 HP -> Player HP: 13). Boss attacks for 10 dmg (Player HP: 3).
- Turn 2: Player attacks (10 dmg -> Boss HP: 10)... wait, if Player attacked each turn:
  - Turn 0: Attack (Boss: 20). Boss deals 15 (Player: 5).
  - Turn 1: Attack (Boss: 10). Boss deals 10 (Player: -5 -> triggers revive -> Player: 10).
  - Turn 2: Attack (Boss: 0 -> Player wins!).
Minimum turns: 3.

Example 2

Input:
boss_hp = 50
player_max_hp = 10
revive_hp = 5
boss_attacks = [20]
moves = [(5, 0)]

Output: -1
Explanation:
The boss deals 20 damage each turn. The player cannot survive past turn 1 even with the revive, and cannot deal 50 damage before dying. Returning -1 is required.