Backroute Checker Program

[Colorful Arty]

I've had this idea for a while now. I want to make a program for NeoLemmix that essentially finds all possible solutions in a level. You would run this program, input a level file, and it would essentially brute-force its way to find all possible solutions, running in the background so the user can perform other tasks on their computer. When the program finishes, it would save every working replay it found for the level.

For those more experienced with programming and the NeoLemmix code itself, please tell me: would such a program be possible? If so, how feasible would it be to make?

Also, is anyone interested in helping me make such a program? I have a lot of other projects I'm working on right now, so help would be very useful.

I think if we could create such a program, it would be an immense help to the community. Not only would it eliminate the need to get testers for a pack, but it could also help you find amazing solutions to your levels even you never thought of.

[kieranmillar]

OK, stop and think about this for a second.

Let's take the simplest official Lemmings level, Just Dig.

How many valid replays is this going to generate if you brute forced every possible combination of skill assignment in every possible place at every possible time? Tens of thousands? Who is going to look through tens of thousands of replays to see if there is a backroute or just a gazillion variations on the same thing?

OK so obviously you'd need to do some culling, but try to define some good rules for this that don't cause backroutes to be missed.

This is only the first of very very many very very complicated roadblocks.

[Simon]

program be possible?

Yes, possible.

NL doesn't expose an API to control execution. Either let the robot brute-force replays based on the level file and feed them into the NL replay checker, or fork NL and hack the robot into the game itself.

you'd need to do some culling, but try to define some good rules for this that don't cause backroutes to be missed.

Yeah, brute-force is infeasible. The solution space explodes according to the size of the skillset.

For brute force, the solution space is all replays that assign the finitely-many skills to the finitely-many lems over time. Since time is unlimited, it seems absurd to allow the maximum possible time before a looping sequence of physics repeats, and instead impose artificial restrictions à la maximum of 5 minutes of doing nothing, or 10 minutes of absolute time.

In Lix, we already encourage level authors to let levels be solved within 5 minutes after the final assignment, so a skill every 5 minutes seems reasonable. 5 minutes is 5*60*15 Lix physics updates or 5*60*17 NL physics updates of doing nothing.

Lix replay checker runs single-threaded. On an Intel i5-6600 at 3.30GHz with 4 cores (3 unused), it checks 22 replays/second. Even though this doesn't generate any imagery unlike the interactive mode, some time is still spent constructing the physics matrix in the beginning. For solving single levels, you would construct this phymap once, cache that, and revert.

The problem runs purely on RAM, and two solutions never interact, thus this parallelizes perfectly across CPU cores.

We still cannot conclude that, without rendering the phymap every time, an AI could test replays faster than this per core. Wrong replays can run for a while before they're cut under the 5-minute-idling rule.

Ballpark guess: A typical level may have 20 lix, 10 skills, and guarantees that a solution under 10 minutes = 9000 Phyus exists. To brute-force without reading physics along the way, each skill assignment may go in 9000*20 positions, and you must test all spreads of the 10 different skills across these positions, that is (9000*20)^10 = 3.57 * 10^53 replays. At 20 replays-per-core-per-second * 4 cores = 80 replays-per-second, we need 4.4 * 10^51 seconds = 1.4 * 10^44 years.

essentially finds all possible solutions in a level

You'd have to define "essential". Levels with infinite time can allow infinitely many solutions. The human considers two solutions practically identical based on intuition, this seems hard to capture in rules.

-- Simon

[nin10doadict]

In conclusion, making such a program feasible and effective would be harder than just getting backroute testers to play your levels.

[Ryemanni]

Tens of thousands?

Millions, billions, too many.

[Nepster]

NL doesn't expose an API to control execution. Either let the robot brute-force replays based on the level file and feed them into the NL replay checker, or fork NL and hack the robot into the game itself.

Or just ask me to provide a sensible API. If you are really serious about this, I can implement (almost) whatever API you desire. This will be a (million) pieces of cake compared to the effort of writing a useful backroute checker.

Two more thoughts on this topic:
1) I wouldn't strive to get all solutions, but to find just one. If you write your application in a semi-random way, chances are that it will find alternative solutions each time the application runs (if there are several of them). Or it will always find the same one, but then one can be somewhat sure that this is really the easiest to find (for a computer).
2) As Simon said, a brute-force algorithm certainly won't work. Therefore I would suggest adding some sort of point-based evaluation method for intermediate level positions (perhaps combined with some machine-learning algorithm to optimize it), to filter out the best attempts so far. Then those can be modified again to see whether they can be improved even more.

[Ron_Stard]

What about just finding the most optimal solution, in terms of less skills used?

[Nepster]

What about just finding the most optimal solution, in terms of less skills used?

That doesn't make it any easier... *cough* *cough* Final Frustration *cough* *cough*...

[Crane]

Of course, I could discourage you by pointing out how infeasible it is to try every skill at every frame, because then you get an exponentially-growing tree.  In the example given, just evaluating "Just dig!" is going to take a while because of the size of the upper area, along with giving more than one lemming a digger skill, and then trying to dig through the lower path (which will kill lemmings, but the program doesn't know that, and some may still reach the exit).

You're welcome to try, of course, and also try to prune the generated tree in some way, but I don't think your backroute tester program will have a general solution that can be found in polynomial time... this is NP-hard at best.  Also, I dare ask what will happen if a level is actually impossible with the skills given!

[ccexplore]

To summarize, it is already a difficult problem just to write a program that can reliably and successfully find a solution to a level in practical amount of time, especially for hard levels whose solutions (and backroutes) may rely on timing, precision moves and special tricks that would likely escape more simplified models of levels and solutions.  Pure brute force has been shown by many here as not effective due to the vastness of the problem space (no surprise there, pure brute force in general is ineffective for most games for that reason).  Backroute checking has the additional problem of finding at least one (more) solution that is significantly different (whatever that means exactly) from a given set of accepted reference solutions.

That being said, I think it's still interesting to see a serious attempt at tackling this fascinating and difficult problem (getting a computer to find solutions to lemmings levels) and see how far you can get, and see what interesting things we may learn out of such an effort.

[Pieuw]

Such a program would be very helpful for people like me, too lazy to backroute-test their levels
The amount of work to make something like this must be tremendous though.

[Dullstar]

I was reading this and had a thought: I have no idea how machine learning works, or what it takes to run that sort of thing, but I wonder if it would be possible to get a computer to play the game at all via machine learning?

[mobius]

mmmmmmmmmmmmmmmmmm....

I'm curious how much (if at all) more possible or likely to work this concept would be on L3 (or better yet) a L3 like but improved tile-based Lemmings game...