Posted: 6/3/2016 1:44 AM
Post subject: CS researchers claim SMB1 levels are PSPACE-hard
Quote
Personman
Other
Joined: 4/20/2008
Posts: 465
Article here. It would be interesting to get in touch with the authors and see if they considered TAS techniques when designing the spiny-lock. Seems reasonably likely that a walljump would break it, though of course it's hard to know without actually seeing the setup. Anyone happen to know them?
A warb degombs the brangy. Your gitch zanks and leils the warb.
Posted: 6/4/2016 6:57 AM
Quote
Warp
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Asymptotic complexity usually considers the worst-case scenario, ie. the upper bound for the complexity (although some notations may instead consider the average scenario, but this needs to usually be stated explicitly.) Thus it doesn't matter if in some situations you could find a solution much faster than the worst-case. That doesn't change the complexity of the problem.
Posted: 6/5/2016 1:10 AM
Quote
ais523
Editor, Player (44)
Joined: 7/11/2010
Posts: 1029
The previous paper along those lines contains quite a few mistakes in terms of what's possible in the games. For example, they mention a device for Metroid which relies on you not being able to enter a morph ball tunnel from the side while jumping/falling, then say it applies to Super Metroid too. Of course, given that we have techniques like the Alcatraz escape, that isn't actually the case. This invalidates the proof because it relies on there being no easy way to perform certain tasks (thus forcing you to do things a difficult way instead). However, it doesn't invalidate the result; for example, you can use pipes like the one that goes between the top and bottom of Maridia to construct crossovers instead.
Posted: 6/5/2016 1:52 AM
Quote
Personman
Other
Joined: 4/20/2008
Posts: 465
Warp, you appear to have completely misunderstood what I said. If their construct is indeed not a lock because of a walljump, then the worst case is not as bad as they claim, and their analysis is wrong. It kind of seems like you're saying that sorting is O(n^2) because bubblesort exists.
A warb degombs the brangy. Your gitch zanks and leils the warb.
Posted: 7/19/2016 4:29 AM
Quote
HHS
Active player (286)
Joined: 10/8/2006
Posts: 356
I believe that the spiny-lock looks something like this: 
OOOOOOOOOOOOOOOO
      OOO
OOOOO  O  OOOOOO
O   OO O OO   OO
  O    f    O  O
OOOOOObObOOOOO
       O       O
OOOOOOOOOOOOOOOO
O = solid block f = fire bar b = brick and fire bar When the spiny is to the left of the 'f', the lock is closed. When it is to the right of the 'f', the lock is open and the player can pass between the upper left and middle left paths. The lock is opened by hitting the left brick to throw the spiny to the right, and closed by hitting the right brick to throw the spiny to the left. Closing it allows the player to reach the upper right path.
Posted: 7/19/2016 7:38 PM
Quote
JSmith
Joined: 8/1/2006
Posts: 428
http://erikdemaine.org/papers/Mario_FUN2016/paper.pdf "if every tile is encoded explicitly, then we show that Super Mario Bros. becomes solvable in polynomial time" Notably, the paper cites TASvideos in its bibliography.
Trying 127.0.0.1... telnet: connect to address 127.0.0.1: Connection refused telnet: Unable to connect to remote host
Posted: 7/20/2016 6:49 AM
Quote
Personman
Other
Joined: 4/20/2008
Posts: 465
the paper wrote:
Both of our hardness proofs are resilient to known glitches [2, 5], where the implementation of Super Mario Bros. is counter to the intuitive Mario physics with which most players are familiar. Figure 1 shows examples of such glitches; see Section 2 for details. By contrast, the previous NP-hardness proof [1] breaks when such glitch behaviors are permitted.
Awesome!
A warb degombs the brangy. Your gitch zanks and leils the warb.
Posted: 7/21/2016 7:41 PM
Quote
jlun2
Skilled player (1741)
Joined: 9/17/2009
Posts: 4981
Location: ̶C̶a̶n̶a̶d̶a̶ "Kanatah"
GBA TASer of 2010
The fact there's a serious paper on a video game of any type amazes me. In my real life experiences, to this day I see people put down video games as kid shit. :| So thanks for linking that. :)
LLCoolDave wrote:
This seems to be competing for the "Worst looking TAS of 2011" Award.
Posted: 7/21/2016 7:46 PM
Quote
JorWat25
He/Him
Player (18)
Joined: 1/15/2015
Posts: 79
Location: United Kingdom
We also implemented the two gadgets of Section 4 in Super Mario Maker, although with some minor modifications to cope with the slightly different physics. The level IDs are 92F8-0000-005D-F452 (crossover gadget) and A8B5-0000-005D-E79A (open-close door gadget).
Not something you expect to see in many papers...
Posted: 7/23/2016 1:54 AM
Quote
Bobthefloater
He/Him
Joined: 11/20/2015
Posts: 31
jlun2 wrote:
The fact there's a serious paper on a video game of any type amazes me.
In theory, due to NP-completeness, work on Tetris could win you a million-dollar maths prize. This is basically due to optimizing Tetris for different groups of tiles is as 'hard' (genuine technical term) as other problems, and the 'hardness' can be transferred between problems such that making one 'easy' makes all of them 'easy'. The Mario paper seems very similar, but with level design instead of tiles. The amusing part is that this means work on TASes could potentially collapse Internet security, by making encryption algorithms 'easy' to break. This is only likely to happen for Mario Maker (due to the different level designs), but it is an interesting thought.