On Paper Mario: The Thousand Year Door, Mario's partners have HP, can guard and superguard like Mario, and when their HP drops to 0, they will get restored to 10 HP if Mario has a life shroom, otherwise they will be defeated, and while the battle will not be considered lost and the game over screen will not be displayed, the defeated partner will not be able to take actions until Mario heals them by using an item. In Paper Mario 64, if Mario successfully guards against an attack, his partner will also guard against it, but unlike Mario, if one of his partners guards against an attack, they will take no damage. In Paper Mario 64, Mario's partners do not have HP - once they take damage, they are unable to take actions or be switched out for the number of turns equal to the damage taken. Note that some attacks cannot be guarded or superguarded - for more information, see the Mario Wiki article about superguarding. If a Pokey throws a body segment at Mario or his partner and the player successfully superguards, the body segment is bounced back to the Pokey, dealing the same amount of damage to the Pokey as the body segment throw attack would normally deal. In Paper Mario: The Thousand Year Door, he can superguard, which prevents him from taking any damage, and deals 1 damage to the enemy that attacked him if it was a direct attack. Mario can guard against attacks, which decreases the damage he takes by one, and prevents status effects from being inflicted by attacks. Some enemies are take more damage from certain attacks, for example fire-based enemies take additional damage from ice-based attacks. Some enemies are immune against certain attack types, for example rock-based enemies are immune to fire-based attacks, so for example, Vivian's Fiery Jinx will do no damage. Some attacks, like Watt's (Paper Mario 64) Electro Dash and Vivian's (Paper Mario: The Thousand Year Door) Fiery Jinx, are piercing, which means that they ignore defence. Mario and his enemies each have a certain amount of defence which reduces the amount of damage they take when attacked the damage taken is the attack power minus the defence. The battle system is turn based: first Mario and his partner attack (either Mario first or partner first, the player can choose), then the enemy closest to Mario attacks, then the next enemy, all the way to the last enemy. Items can also be used to attack enemies. Both HP and FP can be recovered by eating items. "Basic" attacks, like Mario's regular jump and hammer attacks, Goombario's (Paper Mario 64) Headbonk, etc., can be done for free, but more complex attacks require FP (Flower Points). Mario has a partner that can aid him in battle. Cortez from Paper Mario: The Thousand Year Door has different forms, switching to the next form when his HP goes down to 0). If an enemy's HP drops to zero, the enemy is defeated, except in some special cases (e.g. When Mario HP drops to zero, the battle is lost and the game over screen is displayed, unless Mario has a life shroom, in which case he is restored to 10 HP. Mario and his enemies have a certain amount of HP (Heart Points). Can Mario guarantee a win in $N$ turns?įor those of you on the Computer Science Stack Exchange who are not familiar with these games, I'll now give a brief explanation of the two games' battle systems.Of course, we could also consider the corresponding decision problems: The minimum number of turns that Mario can guarantee a win in.The minimum number of turns that Mario can win in.What is the time complexity and space complexity of working out, in suitably generalised versions of the battle systems of both Paper Mario 64 and Paper Mario: The Thousand Year Door: