The Computational Complexity of Fire Emblem Series and 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Victory Probability in the Fire Emblem Arena
We demonstrate how to efficiently compute the probability of victory in Fire Emblem arena battles. The probability can be expressed in terms of a multivariate recurrence relation which lends itself to a straightforward d…
RelationMirror Mode in Fire Emblem: Beating Players at their own Game with Imitation and Reinforcement Learning
Enemy strategies in turn-based games should be surprising and unpredictable. This study introduces Mirror Mode, a new game mode where the enemy AI mimics the personal strategy of a player to challenge them to keep changi…
Reinforcement LearningAppStreamer: Reducing Storage Requirements of Mobile Games through Predictive Streaming
Storage has become a constrained resource on smartphones. Gaming is a popular activity on mobile devices and the explosive growth in the number of games coupled with their growing size contributes to the storage crunch. …
EnsembleMOT: A Step towards Ensemble Learning of Multiple Object Tracking
Multiple Object Tracking (MOT) has rapidly progressed in recent years. Existing works tend to design a single tracking algorithm to perform both detection and association. Though ensemble learning has been exploited in m…
Ensemble LearningMultiple Object Trackingobject-detectionObject Detection+1WildfireSpreadTS: A dataset of multi-modal time series for wildfire spread prediction
We present a multi-temporal, multi-modal remote-sensing dataset for predicting how active wildfires will spread at a resolution of 24 hours. The dataset consists of 13607 images across 607 fire events in the United State…