Artificial Intelligence

[EricLang]

Now I created a side-project: a lemmings engine, stripped down to a kind of state-machine with the same mechanics as my player.
I still have to optimize a few things, but the framerate is now between 3,5 to 5 million frames per second, which is around 800 entire games "Just Dig" per second.
All game features are available as commands and I was wondering if it is possible to write a A.I. that can solve a level.
Brute force or some kind of AlphaBeta search algorithm are probably not sufficient at all: after a few frames the amount of possibilities is already insane.

So: if there are any ideas...

[IchoTolot]

This came up before and after doing a bit more research here are my findings:

The complexity is just way too high. The following article shows this: https://arxiv.org/abs/1202.6581

Lemmings is NP-hard even under very restricted game rules with only 1 lemmings and one of the corollary in the article stated the following:

"Computing approximate solutions to Lemmings with a relative error lower than 1/8 is NP-hard, even for levels with only one type of skill(whatever the skill is)." This holds even if only one skill  type is available, what-ever the skill is.

They even restricted the level to have no deadly-zones, as these are a mjor point for complexity.

In the section "6 Conclusions and Open Problems"  they even stated the following:

"..if exponentially many Builders and Bashers are available, Lemmings is PSPACE-complete, even restricted tolevels with only one lemming."

So the ability to remove created terrain amplifies the complexity even more and in most cases the game is even PSPACE-complete.

As most levels do contain more than 1 lemming, more than 1 skilltype and have deadly zones you can see the big problems here.

One type of the level is an exception though: "levels with only Climbers and  Floaters are solvable in P,  provided  that  they  contain  no deadly zones."

Anyway, I think the article is a good find and sadly an A.I. that solves regular levels is most lekely not possible.

[Lueuebee]

A very interesting concept!!!

I have not much experience with A.I. terminology at all, but I've heard there exists A.I. (for example OpenAI?) that win complex games like DOTA2, GO and Starcraft against pro players... These seem like very very very complex games to me, many times more complex than a lemmix game, so I'm curious to see a solution!

[IchoTolot]

A very interesting concept!!!

I have not much experience with A.I. terminology at all, but I've heard there exists A.I. (for example OpenAI?) that win complex games like DOTA2, GO and Starcraft against pro players... These seem like very very very complex games to me, many times more complex than a lemmix game, so I'm curious to see a solution!

Yes, these are learning algorithms that improve with every match they played until they could compete.

The difference here is there is no statistic that shows how good an attempt is in lemmings. In DOTA you got the objectives, kills, positioning, items....

In lemmings even a solution that is just 1 lemming short (or gets close to the exit) could still be totally wrong. There is no clear optimal way in lemmings compared to these games where you can make out certain variables (there is a clear matagame)

That's a possibility why the algorithm complexity of lemmings is higher.

[Lueuebee]

Yes, these are learning algorithms that improve with every match they played until they could compete.

Couldn't we just use those algorithms here, too?

The difference here is there is no statistic that shows how good an attempt is in lemmings. In DOTA you got the objectives, kills, positioning, items....

What about time spent in game, amount of lemmings saved, amount of skills used?

There is no clear optimal way in lemmings compared to these games where you can make out certain variables (there is a clear matagame)

I'm not sure whether I understand what you mean by this, but I think every level in lemmings has a theoretical optimal solution and I think A.I. is able to find that solution one day in the very near future.

Let's keep our hopes high!

[IchoTolot]

Couldn't we just use those algorithms here, too?

No, as these are highly specific and we don't have comparable statistics. 

What about time spent in game, amount of lemmings saved, amount of skills used?

These are all no certain clues on how close you are to a solution. Even if you saved nearly enough lemmings, your solution could still be totally wrong. You can also just spam all your skills away and let the game run for a long time.

I'm not sure whether I understand what you mean by this, but I think every level in lemmings has a theoretical optimal solution and I think A.I. is able to find that solution one day in the very near future.

Let's keep our hopes high!

Yes, but learning that solution using diffrrent skills while having multiple lemmings is even worse than NP, in fact PSPACE. With that I have no hopes that there will be a good solving algorithm anytime soon. Again https://arxiv.org/abs/1202.6581 is worth a read.

[ccexplore]

There is a nuance when it comes to computational complexity.  It is true that you can construct Lemmings levels that are in effect encodings of computer science problems having specific classes of complexity.  So any algorithm for solving Lemmings levels, no matter how good, will inevitably run into trouble with some levels--if an algorithm can correctly and efficiently solve any level there is, they would in effect also be able to correctly and efficiently solve those equivalent computer science problems that have eluded researchers for decades (and are generally believed to be not possible to solve efficiently, even if there is no proof of impossibility at present).  It's worth pointing out that humans will not fare much better on those kinds of levels either.

But that's a bit different from creating an algorithm that, sure, might not successfully solve literally every solvable level there is, possibly not even every 120 level in the original game, but perhaps can solve, say, Fun or Tricky levels with reasonably high probability of success.

The metric for solution-closeness doesn't have to be perfect.  Yes, sometimes it may lead you down a path where you get very close, but can never actually solve the level.  This is no different from a human hitting a dead end when solving a level; at some point they'll need to backtrack and explore a different branch of solution to make progress.

All that being said, this will still certainly be challenging even with a lowered goal of say just the Fun levels.  I'd suggest doing some research first on what the state of art is for solvers of other puzzle games, for example Sokoban.  Maybe looking at the state of art for other kinds of games can also be interesting, though I suspect less applicable to puzzle games like Lemmings.  I suspect to make good progress for Lemmings, it will also be necessary for an algorithm to derive a higher-level abstraction or model of the level that is perhaps more based on distinct level areas separated by obstacles (ie. a lot more like how we mentally process levels as we plan out solutions), as opposed to just a raw arrangement of pixels.

[ccexplore]

I should add that as far as I know, all current approaches to AI game solvers still throw large amounts of computation power at the problem.  It may be hard to do anything even mildly interesting if you don't have some kind of compute cluster or supercomputer to run your AI on; it'll probably take way too long in most cases if you can only run things on your own computer.

That being said, I'm far from an expert in this area, maybe there are also research into other approaches that are not so computationally expensive.

[EricLang]

Same here, I am no expert at all in artificial intelligence at all. I created a chessprogram once, which comes closest to A.I.
Interesting to see were the first randomized tries, which solved some easy levels after a few runs. But mainly these were in the Fun 1-5 category.
Now I am reading a bit about genetic algorithms and thinking about giving that a try in combination with some very specific built-in lemmings-knowledge and adding some heuristics.

[PapaPetro]

Yes it is possible.
Someone should do it.

Doesn't have to be perfect; just make progress at first.
Solve the first level, say Steel Works in Mayhem, and then train off perfecting that level; then train it on the next levels as such and so forth.
Iterative/Generative AI.

[namida]

AI has come a long way in the last few years. Whereas before people were likely thinking of brute force or algorithmic solvers, it'd be interesting to see what neural network-based AI or similar can achieve. Unfortunately, I don't know nearly enough about it to consider giving it a go.

[mobius]

I've been looking into if it's possible to get Chat GPT or something of similar caliber to play a game like Lemmings. As of yet, I've not gotten very far but saw this article recently so its seems at least remotely possible;

https://www.wired.com/story/fast-forward-gpt-4-minecraft-chatgpt/