I wondered how this could possibly work, then found this sentence. Basically their generalisations have to go far beyond what these games are (the NES mario games had everything be forgotten when you scrolled along).<p>&gt; For example, recall that in Super Mario Bros. everything substantially off screen resets to its initial state. Thus, if we generalize the stage size in Super Mario Bros. but keep the screen size constant, then reachability of the goal can be decided in polynomial time: