Thread where we attempt to prove that Lemmings is NP-complete (split from birthday thread)

[ccexplore]

I haven't forgotten about exponential-time level, but probably don't have time at the moment to create an actual level to illustrate.  I do have a pretty concrete idea though of how to create a level involving nuking that has the "chain reaction" setup geoo talks about, though it does make use of some particulars of DOS game mechanics.   I'll attempt to verbally describe below:

The basic construction looks something like this (note: distances shown are not accurate at all, this is just to show the general look):

         X      X
         XXXXXXXX
X     X
XXXXXXX
         X    X
         XXXXXX
  X   X
  XXXXX
         X  X
         XXXX
    X X
    XXX

A sequence of platforms alternating left and right, with exactly 1 lemming per platform walking back and forth on it.  Length of each platform follows the description geoo gave (eg. N-th prime etc.).  The walls and walkway of each platform are all exactly 1 pixel thick.

We will take advantage of the following details of DOS (DOSLemm or CustLemm) game mechanics:

A) if lemming is on top of a pixel inside a steel area, his explosion takes out nothing, otherwise it takes out the entirety of the usual area, including any pixels that are inside a steel area.

B) when a lemming transitions from walker to faller, he will move down exactly 4 pixels for that initial fall.  This fits well with the minimum size of 4 pixels for height of steel area.

C) falling lemming explode immediately when countdown reaches 0, without the "oh-no" part

The general idea is to make it so that, given a left platform (A), the next right platform (B) above the left platform, and then the next left platform above (C), we are enforcing a chain reaction by making A fall and explode in a particular way to free B, which then falls and explodes in a particular way to free C, and so forth.  Specifically:

i) each walkway is protected by steel area, but the steel area is only 4 pixels tall.  So a lemming standing/walking on the walkway will take out nothing when exploded, but as soon as they can be made to fall off the walkway, their explosion will then take out terrain.  That's because their initial fall of 4 pixels will ensure that they are off the steel area, even with the alignment and size restrictions for positioning of steel area in DOS mechanics.

ii) we arrange the horizontal distance between the right end of A, and the left end of B, in a particular way, as well as the vertical distance between A and B.  Namely, we want it so that the lemming from A must fall off at the right, from the very edge of platform A (ie. upon falling, lemming is at the column of pixels making up the right wall of A), and must explode right after the initial 4-pixel fall, to take out just enough pixels to allow B to perform a corresponding fall.  If A doesn't fall, then his explosion has no effect due to the steel on the walkway.  If A falls past the initial 4-pixel fall, then he is too low for his explosion to take out any pixels of platform B.  If A is falling not from the very edge of platform A, then the explosion doesn't reach to the right far enough to take out any pixels of platform B.

It's not hard to see that with this arrangement, it's also not possible for lemming A to directly free lemming C (B is already barely low enough for A to affect, so C at roughly twice the vertical distance is simply too high).

I hope this is descriptive enough for you to see the chain reaction, and how each lemming has to be at a very particular, pixel-precise location to trigger the next lemming in the chain.

What's left is a lemming to start off the chain reaction (ie. someone below the lowest platform, whose explosion will allow the lowest-platform lemming to fall and start the chain), as well as some way to allow the last lemming in the chain to either get himself or another lemming to reach the exit.
 

I've also read through the paper geoo referenced that has the 1-lemming construction for NP-hardness.  Interestingly, in that paper they resorted to asserting that the time limit is polynomially bounded by the level size, and conjectured that it is so (but no proof or even the slightest justification attempt), in contradiction to geoo's N-th prime construction.  On the other hand, we resorted to nuking to make geoo's exponential-time construction work.  So naturally the question is, if we are not allowing solutions involving nuking, is it still possible to come up with a scheme where required time limit is exponential to level size, or does it become polynomial then?  Note that with nuking, you have a move that is applied one-time only and affects all lemmings at once.  This is quite different from your usual skill assignments, which affects only 1 lemming at a time, and which you have nearly full control of timing of when to assign.

[ccexplore]

So naturally the question is, if we are not allowing solutions involving nuking, is it still possible to come up with a scheme where required time limit is exponential to level size, or does it become polynomial then?  Note that with nuking, you have a move that is applied one-time only and affects all lemmings at once.  This is quite different from your usual skill assignments, which affects only 1 lemming at a time, and which you have nearly full control of timing of when to assign.

I thought about it a little more, and I think I can modify my chain reaction scheme above so that instead of nuking, you assign exploders explicitly, but the timing requirement is still such that everyone needs to be at the right place (in order to enforce the "product of N primes" aspect).  At least that's my hope, please read this over and see if you spot a hole in this approach.

(I'm not going to bother with spoiler tags, I don't think they are necessary for the very limited audience of this thread. )

[edit: clarified description in certain places]

--------------

This time the chain reaction goes downwards instead of upwards, and instead of alternating platforms, you simply have a series of platforms from top to bottom, each slightly offset to the left from the previous platform above.  For those who haven't read the description of the nuke chain reaction, each "platform" is simply 1 one-pixel thin horizontal walkway with 1-pixel thin walls at each end, with exactly one lemming walking back and forth per platform.  In other words, the general shape of the platform is:

X   X
XXXXX

At the top, you can explode one lemming to release another, causing it to fall down.  However, that lemming needs to be released just before he turns around at the right end of the platform he is walking at, so that when he starts falling he is doing so at the column of pixels of the wall at the right end.  If he falls anywhere else, his fall will be cut short by splatting on some terrain below.  (Terrain which is still well above the walkway of the next lemming in the chain.)  Because the exploder simultaneously take out a bunch of pixels, in the case where he is nowhere near the explosion area when the explosion occurs, he will still not be able to subsequently reach where he is required to start falling, due to the gap form by the explosion on the walkway.

If you successfully allow that lemming to start falling at the right place, he will still end up splatting, but at a much lower position then if he started falling at the wrong place.  This gives him a chance to reach the next "link" in the chain, but doesn't give him so much time that you can wait for the next lemming in the chain to get to the right place.

Now we need to enforce that the falling explosion happens only at a particular desired position.  We will do so as follows.  First, note that the bottom-left portion of the explosion mask looks something like this:

+++++++
 ++++++
  +++++
    +++

So there are 3 cases:  exploded too early in the fall, just right, or too late.

Too early (| is column of pixels for wall):

+++++++
 ++++++
  +++++
XXX|+++
    ^

The lemming ends up falling at location marked ^, just one pixel horizontally past where the wall at the right end of the platform is located.  He will splat prematurely if he falls at that position.

Just right (recall that each frame of falling changes y by 3):

XXX|+++
 ++++++
  +++++
    +++
  ^* 

Obviously the "xxx|" will be taken out by the explosion as well, I just leave them in there to show the relative position of the explosion mask to the platform.  In this case, the to-be-released lemming must be standing horizontally at column of pixels marked by ^ when the explosion happens, in order to fall at *.  Otherwise if he doesn't fall at *, he splats prematurely during the fall.  If he is nowhere near the explosion area, then he is simply unable to reach ^ and fall at * subsequently, since the explosion takes out more pixels to the left than that.  And if you are sneaky and try to make the lemming "oh-no" while standing at * so he does fall there, well, there's only a limited (and fixed) amount of time before "oh-no" explodes, and that amount of time is too short for the released lemming to fall to where he needs to be for next part of the chain.

Finally, if even one frame too late, then the exploding faller lemming splats before he can explode, failing to release the next lemming in the chain.  If I recall correctly, splatting will cancel an impending explosion.  If not, I'm sure you can do something with traps or steel areas to make sure the lemming can never explode below the "just right" point.

So in summary:

1) Each lemming falls and explodes to release the subsequent lemming in the chain.

2) When you release a lemming via explosion to make him start falling, there is only a finite amount of time before he splats, no matter where he is falling at.  So you can't wait indefinitely for the next lemming in the chain to be at the right place.

3) when you release a lemming via explosion to make him start falling, if he is not falling at the exact correct x position, he splats prematurely before reaching the next part of the chain, thus stopping the chain reaction.

4) There is only one correct x-position the next lemming in the chain should be at, before he gets released.  If he is at the wrong x-position within the explosion area during release, he falls at the wrong x-position and splats prematurely ending the chain.  If he is nowhere near the explosion area, he can't subsequently reach the right x-position to fall.

5) The falling lemming has to explode at precisely the right time.  If he explodes too early, either he is too high to take out any terrain of the next part of the chain, or even if he is high enough, he doesn't take out the pixels needed to allow the next lemming in the chain to fall at the right place, instead causing the next lemming to fall one more pixel to the right of the correct falling position, resulting in eventual splat and premature end to chain.  He can't explode too late because one frame past "just right", and he splats (or otherwise gets killed immediately in some fashion) instead of exploding.  Only at the "just right" position will he take out all the terrain pixels that needs to be taken out for the next lemming to have a chance at continuing the chain.

6) It should also be easy to ensure a nuking solution won't work (or won't help much).  When you nuke each lemming explodes one after another (more or less), we can simply ensure that the falling to next part of the chain takes too long for a nuking solution--the next lemming in the chain explodes himself before the previous lemming is able to release him via explosion.

-----------------------

The one aspect I'm not confident on (and perhaps this applies to the nuking version as well, I don't know) is that there's a bit of delay going from one part of the chain to the next, due to the falling (which has to be high enough to accomodate the various splatting required to enforce the chain).  That delay should be constant however at each "link" of the chain, and I'm hoping that is enough to ensure that mathematically you can still create the product of N prime condition, instead of having some other earlier timing that also happens to work out.

If anyone actually wants to create a level based on my description, you'll probably need L++, since the limited vertical span of DOS levels may make it impossible to create a meaningful version in Lemmix/LemEdit.  On the other hand, some aspects of my solution are based on details of DOS game mechanics, and may need to be modified to carry over to L++.  Hopefully it still works in L++ mechanics!

[geoo]

Ah, your second realization of the idea looks very clean, and I think it should also work in L++ and other physics. Nice! Hahaha, we should make and release this level for the Clones site!
So this conclusively proves that polynomially bounded levels can still take exponential time to solve, contrary to the conjecture in the paper.

However, this doesn't prove that Lemmings as we defined it isn't in NP: A friend of mine suggested that our solution verifier could, if there's only polynomially many moves to the solution, simulate it as follows in poly: Assuming that the terrain doesn't change unless a skill is assigned (whose completion will only take polynomial time; that doesn't take into account e.g. bashers caught between blockers, but they don't change the terrain after more than a poly amount of time either), the terrain in the level doesn't change, and thus lemmings will walk in a cycle, and not affect each other (I just realized that the latter assumption is precarious, because you might set up an exponential bunch of lemmings and a polynomial amount of traps in a very clever way that it's difficult to simulate the behaviour). Then you could detect the cycle length (which is poly as the level size is poly), and calculate ahead where the lemming will be at the point in time the next move is performed.
Of course, this doesn't automatically prove that these levels could still be simulated in poly time, as you could try a setup with exponential skills, or some trap setup like I insinuated, but then again you could adapt the solver for these special cases as well. Therefore I think it's generally hard to prove that Lemmings is not in NP (if that is even right), as the problem (find a solution format that describes every solution in a way that it takes poly space and can be verified in poly time) reminds me a lot of Kolmogorov complexity, which is uncomputable. In the same way, should the problem be in NP, I think it'd be very difficult to provide such a format, having to consider all kind of things, unless some useful abstraction can be found.

Interesting.  Another way ordering matters with DOS-like game mechanics is that the lemmings are processed in a strict order, and the terrain additions/removals of one lemming is immediately visible to subsequent lemmings even inside the processing of a frame update.  If I understood you correctly, you got around this for nuking by stipulating that if 2 lemmings entered the level at the same frame, they will start their nuke countdown at the same frame also.  We can do that too for general frame updates, stipulating that the 2 lemmings cannot see each other's terrain effects within the processing of the frame update (ie. they both only see the terrain the way it was before the frame update started).  However, in doing so, we now introduce a new issue:  what if one lemming is adding terrain to a pixel while the other lemming is removing terrain at the exact same pixel?  Does the pixel end up with or without terrain after the frame update?  It's not hard to resolve this issue, but it does add some new rules to the game mechanics that aren't needed when there's a strict processing order.

I was thinking of just picking a bunch of lemmings from the equivalence class to get assigned the skill, and taking the ordering within the class just as it fits our needs, to establish a strict ordering, but I'm not quite sure whether that'd actually work, because could it be if we do this twice to a group with the same priority (e.g. split it up and reunite it), that our priority choices could be contradictory? I'm trying to wrap my head around this idea to setup such a scenario, but it's kinda confusing, and I'm also not that intimate with the precise happenings between two lemmings that affect each other during the same frame (e.g. does a lemming that is dug under by another lemming that gets processed earlier transform into a faller right in that frame, or only the next frame and could thus still be assigned a builder?).

[ccexplore]

I'm trying to wrap my head around this idea to setup such a scenario, but it's kinda confusing, and I'm also not that intimate with the precise happenings between two lemmings that affect each other during the same frame (e.g. does a lemming that is dug under by another lemming that gets processed earlier transform into a faller right in that frame, or only the next frame and could thus still be assigned a builder?).

The former, under DOS game mechanics.  The changes in terrain by the earlier-processed lemming are fully visible to the later-processed lemmings.  If the ordering is switched so that the digger is processed later, then the earlier lemming doesn't see the effect of the later digger until next frame update, and therefore you can still assign builder.

[viglietta]

Hi, I recently wrote a paper discussing the computational complexity of Lemmings.  Inicidentally, it answers the questions you were asking in this thread.
http://www.di.unipi.it/~vigliett/files/papers/lemmings.pdf

Regards.

P.S.  I would greatly appreciate your comments and corrections, especially concerning my description of the game mechanics (Section 2).
P.P.S.  The PSPACE-completeness proof in my paper builds upon another result of mine, contained in this other paper:
http://www.di.unipi.it/~vigliett/files/papers/gaming.pdf

[geoo]

Very nice work! Yeah, we got the NP-hardness and existence of exponential time solutions independently here in the forum, but not the question regarding PSPACE-completeness. I was perhaps going to look into it at some point, but it seems that you beat me to it.
And have fun at Fun with Algorithms.

I read through your papers, and the results and proofs seem sound to me, except for some details related to peculiarities in the mechanics. But well, that's what you get for not using a simplified model like Cormode and Forisek did, right?
Also one thing I noticed is that you restricted the amount of Lemmings to be polynomial (which I think is reasonable), while Cormode sneakily got around encoding values in unary by just encoding each Lemming's start position individually. If we're on about entrances already, DOS lemmings also has some quirks in this regard, not always spawning them cyclically, but if there's two entrances it uses the order ABBA, and if there's three, the order ABCB.

Oh, and I think the link to the Lemmings wiki in your references is dead by now, didn't notice it got taken down until now.


Anyway, I'm not sure how strictly you want to adhere to the original physics, but I'll describe some things that require revisions in some parts if you want to take these quirks into account:

First off, it is possible to assign miners and bashers turning them around without removing any terrain. The first two levels in the attached level pack display that: If you assign a basher at the right time shortly before the gap, or a miner before the small pit, they will turn around without removing terrain.
This makes Lemma 1 wrong (assuming you mean an encoding of all actions as the size of a solution, without any compression): For instance, you can design a level using synchronization (prime sized platforms like described in this thread or by Forisek), placing steel in such a way that it's impossible to bash for delay. Have e.g. the smallest of the platforms require to use the basher trick/glitch shown in my attached level to have the lemming stay on the platform. It takes exponential time to synchronize all lemmings, and the one on the smallest platform will have to do exponentially many basher strokes.
Of course, this basher's action will be periodic as well, and so you can predict it as well without having to simulate every single step, so Theorem 1 still holds, with some adjustments to the proof.

In this section there's another statement that isn't quite accurate (page 7, 3rd paragraph): "In order to offset l's phase within its own period by any desired amount, just polynomially many Basher skills are sufficient, and may be assigned at any time."
Perhaps I'm a bit nit-picky here, but any desired amount might not be possible, because the greatest common divisor of the cycle length and the offset gained from bashing once might not be 1. You can't assign them at an arbitrary point either, but have to do it at some point where bashing has no effect. It should be noted that the offset by bashing is not necessarily constant due to the behavior of the basher turning without removing terrain as described above, but in any case it should be possible to achieve the offset that was achieved in the original solution using only O(cycle length) bashers (in addition to those that might be applied periodically, as described in the previous paragraph).

Another quirk that has some effect on your construction for the PSPACE-completeness proof is that in the original game, trigger areas overwrite steel (and blockers overwrite both until removed, but that's a different story). You can check this out in your level showing off the path gadget, allowing to turn around. This should have no effect or at least be easily amended, and shouldn't affect the end result.

The third level in the attached pack shows another quirk, namely that builders are asymmetric depending in which direction you build. I don't think this has any effect though, as you don't need to mirror your gadgets.


Then a few more general notes on Lemmings physics as described in Section 2:

You describe the assignment priority in Lemmings, but then never reference it again. I think it's ok not taking it into account, as it just makes proofs more technical if you want to be sure not to run into issues with it. Also, if there's a worker lemming (builder, basher, etc) under the cursor and a walker, then the worker will get the assignment priority (even if the worker is "younger"), unless you hold the right mouse button while clicking.

Describing a blocker as acting like a wall might be a bit misleading. It only acts somewhat like a wall to walkers walking against it, while fallers can fall into the blocker just fine (i.e. without landing on something like a wall), and blockers also turn builders, miners, fallers, etc. around, which walls don't.

And finally, the basher check. It's pretty weird, I'm just gonna ccexplore on this one (hope he doesn't mind):

It checks 4 pixels, and yes, 6 px above ground.  More precisely, for DOS Lemmings anyway (details for Amiga/SNES etc are likely similar) when basher is at (x,y) [location being the pixel he's actually standing on] it will check pixels (x+8, y-6) thru (x+11, y-6) [analogously if facing left].to be all empty to stop bashing.  This check is done only on every other stroke starting with the first.

I'm not exactly sure when or how the steel check occurs though.

[viglietta]

Wow, you are certainly an expert in Lemmings and the related literature.   
Thanks for taking the time to write such a comprehensive comment, I sincerely appreciate your effort!

I was aware that I was omitting some details of the game mechanics: I did it due to space limitations (12 pages), and only if they didn't matter for the later proofs.  The only thing that I really need for the NPO part is that the configuration transition between time units can be computed in polynomial time, which is abuntantly true regardless of the details.  On the other hand, I describe Builders and Bashers as thoroughly as I can, because I am going to need them for the PSPACE-completeness part.

However, I was unaware of many aspects of the game that you pointed out, mainly because I tried to figure them out by experimentation and trial and error.  So your contribution is extremely helpful there.  I also wonder if there is any standard "tool" to discover such things, because right now I am only using the game itself and the Lemmix editor, but I have a hard time pausing the game after each frame, for instance...

Luckily enough, most of my misconceptions don't seem to substantially affect the paper's main results.  I also extensively tested all my gadgets, and they all seemed to work even when I tried my best to "break" them (making such a "robust" Door gadget took me quite a lot of time, actually...).

I will take into account all your comments, and see where I have to correct the paper.  Hopefully I can keep it within 12 pages, which is my main concern right now...

Cheers!   

P.S.  The Lemmings Wiki was there just a couple of days ago, when I last checked!  Maybe it's just temporarily offline?  Can some admin confirm this?

[Simon]

Yep, you already did extensive trial-and-error on the physics.

Your notion of time interval seems to be equal to two game updates, not just one. This seems somewhat random, but if you use it consistently, it's perfectly fine.

I wrote an essay about the location behavior of the pin for walkers (I called the pin "effective coordinate"). Most notably, the pin isn't symmetric for left/right walkers.

Since you describe builders extensively: The placement of a builder's brick has been amended to look nice with the sprite. Since the pin isn't symmetrical w.r.t the sprite, the brick isn't placed symmetrically w.r.t. the pin either. In bridges built by a right-facing builder, the pin on brick-placement is in the leftmost pixel of the brick. In bridges built by a left-facing builder, the pin on brick-placement is in the second-to-rightmost pixel of the brick.

As a result, if the player waits as long as possible before re-assinging builder, bridges going to the right can be stretched further (with a 1-pixel overlap) than bridges going to the left (with a 2-pixel overlap). Immediately re-assigning builder would make a 4-pixel overlap in both directions.

You already say "the pin depends on direction", so maybe you don't have to alter much, if even anything, to have the paper acceptably accurate. This is just an ugly result of sprite placement, and making the physics look nice with the sprites.

Good luck with the thesis!

-- Simon

[viglietta]

Thanks a lot, Simon!

Yes, I read your essay before writing the paper, and it helped me a whole lot!  I briefly took care of that asymmetry by saying that the pin position depends on direction, and that is kind of sufficient for the scope of the paper.  The main issue here is the space constraint of 12 pages!  I would love to add more details, but I don't know how to fit them all.

By the way, I'm not really doing this for my thesis, it's just for fun!  But thanks anyway.   

[ccexplore]

By the way, I'm not really doing this for my thesis, it's just for fun!  But thanks anyway.   

"just for fun"?  Oh, how I envy you guys with seemingly unlimited free time, something in short supply when one has to work for a living.

Cool paper though, I haven't had a chance to read in detail but it was intriguing just from the abstract.

Regarding glitches, keep in mind that Lemmings is possibly one of the most ported games in existence, with a version available in almost every PC or console system you can think of.  I don't know (as I haven't read through your paper yet) if the scope of your paper is specifically geared towards DOS Lemmings (which is what Lemmix emulates) vs some other version, but given that there's bound to be some obscure behavior unique to each particular version, I don't think it'd be necessary to be absolutely complete in terms of the game mechanics.  I suspect none of the differences would've affected your results anyhow.

[ccexplore]

I just got some reading done and got to page 2.   Okay, maybe not as much reading as I'd like.

The "deadly zone" definition was interesting as an attempt to merge water/lava type objects and triggered-trap objects under the same definition, but as a result it's not quite accurate, or at least somewhat ambiguous the way I read it.  The key difference is that if you have multiple ("N") lemmings moving perfectly in sync with each other (ie. they are all compressed to the exact same position and moving together), and then they reach the object's trigger area, a water/lava type object will kill all of them at once.  A triggered trap will only affect 1 of the N lemmings.  Whereas in your definition, it reads more like all N of the perfectly-sync'ed lemmings will all get killed as they all move into a triggered (ie. k > 0) trap, and then the trap becomes inactive for the next k time units.

I suppose with a more fine-grained definition of time unit that considers the update of each individual lemming to occur at distinct time units, your given definition would be accurate, although I think it would also allow triggered trap objects that don't actually exist in the real game.

Anyhow, I'm sure it doesn't really affect the results of the paper in any meaningful way.   I guess I'll read on and find out.