The Computational Complexity of Fire Emblem Series and similar Tactical Role-Playing Games
This work addresses the computational complexity of tactical role-playing games, providing foundational hardness results that are incremental but rigorous for game theory and AI planning.
The paper proves that a simplified version of Fire Emblem is PSPACE-complete, indicating the actual game is at least as hard, and shows that a poly-round variant is NP-complete under specific constraints, with results applying to similar tactical role-playing games.
Fire Emblem (FE) is a popular turn-based tactical role-playing game (TRPG) series on the Nintendo gaming consoles. This paper studies the computational complexity of a simplified version of FE (only floor tiles and wall tiles, the HP and other attributes of characters are constants at most 8, the movement distance per character each turn is fixed to 6 tiles), and proves that: 1. Simplified FE is PSPACE-complete (Thus actual FE is at least as hard). 2. Poly-round FE is NP-complete, even when the map is cycle-free, without healing units, and the weapon durability is a small constant. Poly-round FE is to decide whether the player can win the game in a certain number of rounds that is polynomial to the map size. A map is called cycle-free if its corresponding planar graph is cycle-free. These hardness results also hold for other similar TRPG series, such as Final Fantasy Tactics, Tactics Ogre and Disgaea.