What Makes Mario NP-Hard? (Polynomial Reductions)
ฝัง
- เผยแพร่เมื่อ 27 ม.ค. 2019
- We think of Mario as an influential platforming game, but it also has interesting connections to complexity theory. In this video, we explore what makes Mario NP-hard.
Twitter: / ubehavior
Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Zachary Greenberg
Music: Gravity Sound ( / @gravitysound )
-
References:
Paper: arxiv.org/abs/1203.1895
Reduction: en.wikipedia.org/wiki/Reducti...)
3-SAT: en.wikipedia.org/wiki/Boolean...
P vs NP Playlist: • P vs NP - วิทยาศาสตร์และเทคโนโลยี
someone has to make a level like this in mario maker if it doesnt already exist
Was thinking the same thing! The video gave me huge Mario Maker vibes.
I see a lot of softlock opportunities and game style inconsistencies. If you can ground pound, you can also wall jump and cheese vertical gaps. Big Mario can damage-boost through a set of firebars and cheese one assertion. One-ways to the rescue, I think, though they are best avoided as much as possible.
When I’ve followed the course _Complexity,_ in about three months, I’ll work on it. I’ll share the level code when I’m done.
@@casperdewith You can't damage boost to cheese an assertion because there is a breakable block before the flag, you must be big
@@AssemblyWizard Hmm, good one. I overlooked that.
@@casperdewith My biggest concern was whether the stars would despawn...
Amazing! I really like your animations, "Undefined Behavior" channel helped me so much understanding complexity :)
Also, how do you only have 13k subs? Your content is amazing
You make good and interesting videos. I just discovered your channel. I hope you didn't quit making them.
Does this make Mario NP-complete?
We should be able to check in polynomial time whether a given solution is correct. First, simplify a bit by introducing doors. this makes the whole process more linear. Then we get a simple input sequence of "Door > left/right > ground pound > door > left/right > ... > grab star > run through fire > grab star > ... > flag" which should be checkable in poly time.
This only applies to our simplified Mario version. However, on a lower level you might even argue that checking whether a given inpute sequence in a game, say Mario Maker, beats the level. This should also be polynomial since the time required in linear in the number of frame inputs (i.e. frame amount/60).
So I believe Mario is in NP and, given the NP-hardness, also NP-complete.
A later proof showed that Mario is PSPACE-complete, and so unless NP = PSPACE, it's unlikely that Mario is NP-complete also.
The original paper relaxed the constraints on level design slightly by allowing levels more than one screen (13 tiles) high, and allowing scrolling to the left. An interesting question is the complexity of the original NES SMB1 with its original mechanics, without these generalizations.
my thought is somehow converting the level into a boolean expression of every input on every frame (upframe1, downframe1, leftframe1, rightframe1, aframe1, bframe1, upframe2, etc.) because smb1 has a time limit, there are a finite, albeit very large (6 possible inputs per frame, 60 fps, 500 secs, plus freeze frames from powerups and taking damage and pauses from going into pipes Kosmic probably explains it better than i do in his slowrun which I'm not sure i can link without getting my comment deleted) number of literals.
the run in question, if this comment doesn't get deleted, can be found at th-cam.com/video/ww_rRwfIsB0/w-d-xo.html
Love this paper, and the explanation here was really solid and helped me to understand some of the finer points of the crossover gadgets. I'm curious...did you write code to create the level for (x OR y) AND (not x OR not y), or did you make that manually?
yoo, now in my last class of computability theory, and this is unironically helpful! :)
6:05
Classic Mario can't ground-pound
Respect! Respect! great job
came here with no understanding of np and got out with a vast knowledge on a game that I've never played, thank u my broski
From a practical standpoint, I would have the problem work backward. Can any part of the pole be reached from the play area? If yes, then continue to work backward to the start line.
So we reduce an NP-Hard problem to 3SAT in polynomial time. One can try to solve it by asking the verifier, which we were able to reduce it to 3SAT in polynomial time, whether the problem can be solved in each step. Since the answers to these decision problems in each step can be found in ExpTime can we say that NP-Hard⊊ExpTime?
this video is great
Hm, but is the reduction doable in polynomial time? I imagine managing the crossings such that everything works out as intended might get complicated after some time, possibly making us unable to construct the level from a given 3SAT formula in polynomial time.
To fix this, you might simply use doors tho ;)
The reduction doesn't need to be doable in polynomial time.
@@elli6220 actually, it needs. Otherwise it wouldn't be "as hard"
For example:
given a random problem A and a random NP-hard problem B
1- suppose you've found a reduction from some problem NP-hard B to A
This means that if you can solve A, you can solve B
2- suppose you've found a way to solve A in polynomial time
if you can solve A in polynomial time, you can convert problem B into problem A and solve B
If your reduction is in polynimial time, this means that you can solve ALL of the NP-hard in polynomial time
If you reduction is not in polynomial time... you've proved nothing, so you didn't prove that B is AS HARD as A(in, at least, the same time complexity)
@@elli6220 And, in fact, you can convert EVERY possible problem to a simple circuit verification problem that can be done in polynomial time... but the reduction would not be polynomial time
@@99temporal Thanks for informing me!
awesome.
this is pretty interesting
sounds like a tool you could use to make puzzle levels
It would be amazing if you did a video on molten salt reactors
9:00 2-sat ?
great!
If Mario is NP-Hard, then what's up with those people claiming that AIs are winning mario? How can you train a computer, which is a Deterministic Turing Machine to complete Mario levels simply by feeding information into it?
An AI can win the base game (which mostly involves just going to the right); it would probably struggle a lot with a level like designed like this, especially if you added more variables.
Also, NP hard doesn't mean impossible, it just means it takes a long time. There are 3-SAT solvers, but there exist long strings of logical clauses that will take the 3-SAT solver a long time to figure out.
There are also long strings of clauses it will solve nearly instantly, if it's any good - NP hard just means there ARE hard problems of that type, not that all such problems are hard. The same is true of Mario.
@@MarkChimes Thanks for answering! I got everything except for the fact that you said 'NP hard doesn't mean impossible'. Since Non-Deterministic FSAs can't exist, and this en.wikipedia.org/wiki/NP_(complexity) article on Wikipedia implies that it can only be solved by such a machine, how can you 'reduce' such a problem to solvable in polynomial time?
@@kinertia4238 The AIs designed to beat Mario run on deterministic machines yes, but it doesn't mean that they are doing it in a polynomial time. Its like cracking a password. A computer program can guess a 4-character long password in an instant but it would need millions of years to guess a 40-char long one. In both instances it just brute-forced the solution in a non polynomial time. Non polynomial just doesn't mean short or long. In the case of Super Mario Bros for example if you know the last stage 8-4 before you meet the princess Mario has to get into a specific squence of tubes to get to the boss or else he will respawn at the start of the level. If you don't know the right path you really have to try all possible combinations to solve it. So you either have to brute force it using a non polynomial algorithm or you'll need a non deterministic "oracle" to guess the right path for you. In that stage there were only 3 correct "doors" to guess so it was easy to solve but imagine a stage where you have to decide 3000 times between door A or door B. And each time you make the wrong decision you start from the beginning. Good luck solving that, even with a computer.
@@wajaism thanks a lot!
The answer is that AIs are using heuristic techniques, not algorithmic ones. The PCs are literally running an algorithm, but that algorithm isn't itself a solution to Mario, it's a way to find a close enough approximation of a solution to Mario, where "close enough" mean able to beat any of the given levels in a Mario game, but not necessarily any given level. You might say that the AIs are capable of solving particular Mario games, but not the generalized Mario problem.
hmmm got any level idea?
08:37 He can also run left and land on the flag
Lol
Given you only used two variables per clause, doesn't this make it 2-sat which is in p ? Shouldn't you have used a three like structure for this ?
Whenever you reduce problem A to problem B this only shows problem B is at least as hard as problem A. Here, problem B is Mario. If problem A is 2SAT this shows that Mario takes at least polynomial time. However, it does not show it is *in* P. For the video, 3SAT is NP-hard, so Mario is NP-hard, too. However, Mario isn't necessarilly in NP, it could as well be in any class above NP,like PSPACE or 2EXPTIME.
anyone got some good books on this?
3:49 *animation plays*
brain: *MUSIC ON*
There's been Turing Machines, calculators, 51-checkpoint levels, near-impossible levels with 1 nonvigintillion chance of guessing a correct combination, and more in Super Mario Maker 2!
Around 8 minutes can't Mario run fast and slide to get under and through the path? Thought I remember doing something like that but that was a few years ago.
Isnt 3SAT NP-Complete, making Mario NP-Complete?
After watching this video, my brain is no more.
Unfortunately, this level is impossible in Super Mario Bros, because Mario cannot ground pound in that game.
On the other hand, he can probably clip through the wall on the left side of the first vertical shaft and then drift to the left over the firebars to the flag.
On the OTHER other hand, the camera cannot scroll to the left in Super Mario Bros, so the level is impossible to complete in any case since the flagpole is to the left of Mario's starting location.
ground pounding is not a mechanic in Super Mario Bros for NES which this reduction was written for
Fireballs are spinning the wrong way; I'm out.
Theres a game called bounce which is actually much more accurate representation of 3 sat than mario
what is NP?
Undefined Behavior explains the concept in his other videos: m.th-cam.com/play/PLlwsleWT767dnN25K_QgvdKkovK_t4K6-.html
Dang
hey :D
The stars dissappear tho. Its jot no complete because with certainty the level is unwinnable.
7:32 you forgot that Mario can sit and walk at the same time.
Mario can crouch and jump, but not crouch and walk. So one could replace some of the blocks with spikes to ensure Mario will take damage from crouch jumping. (This also prevents Mario from accidentally killing the goomba too soon and getting soft-locked.)
Super Mario Bros. is actually undecidable because you can simulate a Turing machine powered by shells. There is no way to decide whether an arbitrary Super Mario Bros. contraption halts.
I already finished the whole playlist and don't understand a think that I can write an article about it in my own words. I'm either stupid or his explanation is not good enough or I need to dig deeper and needed a technical book.
I feel like my time has been wasted
I'm not an expert but doesn't this just prove that NP-Hard problems can be expressed in Mario so: NP-Hard ⊆ Mario. But it doesn't prove that NP-Hard is a proper subset of Mario (NP-Hard ⊂ Mario). I'm pretty sure that most normal levels in Mario are not Np-Hard, but that doesn't mean you can't create NP-Hard problems in Mario. So I'd say for the most part, Mario is not NP-Hard
You're right, but the claim is that the following decision problem is NP hard: "Given a Mario level, is it possible to beat it?"
The point of the video is that this problem must be NP-Hard since solving a level like the one shown is as hard as solving 3SAT
Given *any possible* Mario level - which indeed would include levels like this. So an algorithm that could solve any possible Mario level would indeed be able to solve these sorts of problems.
Completing all levels in Super Mario is NP-Hard to me.
poor mario
I'm pretty sure any real level in any real Mario game has way less complexity than NP-hard. :P
A real Mario level would be just an instance from the Mario-Problem. He has just shown that its impossible to write an algorithm that can decide, in a polynomial number of steps, if "any" given Mario level is solvable (assuming P/=NP). The decision time will grow exponantially with the number of variables in the level. If it were possible to solve Mario, we could use the Mario simulation of sat3 to solve sat3, which is known to be unsolvable in a polynomial time.
@@wajaism I wish he explained this. I'm not smart enough to ponder and come up with consequences on my own. It's awesome what the video proved, but I didn't get why it was useful. Thank you
that doesn't mean the normal mario gameplay IS np-hard, it just means you can create an np-hard problem simulator using mario mechanics. the 'proof' is absolutely misleading. you can also create the same problem with a circuit board, does it mean circuit boards are np-hard too?
Yes
They are
This prove shows that you can create a Mario level such that it is at least as hard as solving 3-sat. That means that you cannot create a program that runs in polinomial time to solve "any" mario level.
So there are levels that are easy, there are levels that are NP.
We could also try to see if we can make levels that are uncomputable. Making mario undecidable
Mathematics is so Wack.
In school they teach you the quadratic equation.
As a career, you need to solve the Mario equation.
You are not showing that Mario is NP-Hard, you are just using graphics from Mario to describe a NP-Hard problem. There is no Mario level that looks like this. That's not how the actual mechanics of the game work. I actually can't even really say that because it doesn't seem like you took all the game elements from the same version of Mario and the mechanics vary by game.
that’s a reduction, you use these to prove that problems are NP hard
I have herpes