PSPACE-Hard 2D Super Mario Games: Thirteen Doors
arxiv(2024)
摘要
We prove PSPACE-hardness for fifteen games in the Super Mario Bros. 2D
platforming video game series. Previously, only the original Super Mario Bros.
was known to be PSPACE-hard (FUN 2016), though several of the games we study
were known to be NP-hard (FUN 2014). Our reductions build door gadgets with
open, close, and traverse traversals, in each case using mechanics unique to
the game. While some of our door constructions are similar to those from FUN
2016, those for Super Mario Bros. 2, Super Mario Land 2, Super Mario World 2,
and the New Super Mario Bros. series are quite different; notably, the Super
Mario Bros. 2 door is extremely difficult. Doors remain elusive for just two 2D
Mario games (Super Mario Land and Super Mario Run); we prove that these games
are at least NP-hard.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要