Lemmings Boards > Tech & Research

Artificial Intelligence

(1/3) > >>

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:
:lem-mindblown: 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:

--- Quote from: Lueuebee on April 10, 2020, 04:32:29 PM ---:lem-mindblown: 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!

--- End quote ---

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:

--- Quote from: IchoTolot on April 10, 2020, 05:09:24 PM ---Yes, these are learning algorithms that improve with every match they played until they could compete.

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


--- Quote from: IchoTolot on April 10, 2020, 05:09:24 PM ---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....

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


--- Quote from: IchoTolot on April 10, 2020, 05:09:24 PM ---There is no clear optimal way in lemmings compared to these games where you can make out certain variables (there is a clear matagame)

--- End quote ---
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! :8:()[:
:lemming::lemming::lemming::lemming::lemming::lemming::lemming::lemming::lemming::lemming:

Navigation

[0] Message Index

[#] Next page