Automated generation of Manic Miner speedrun/walkthrough

[crem]

Recently I attempted to generate new strats for speedrunners for DOS game Prince of Persia (PoP). The approach was mostly a brute force, yet surprisingly it worked pretty well, although most of the findings were micro-optimizations.

Now I'm trying to do the same for Manic Miner (and if successful, later for other ZX Spectrum games).

Algorithm is pretty dumb breadth-first search:
0. Initially have just 1 state, start-of-the-level.
1. In the beginning of the step, there are N states from the previous step.
2. For every step, for all possible player inputs, generate possible states for the next frame.
3. Deduplicate and score the states (using some heuristic).
4. Keep only N=LIMIT best possible states.
5. Goto 1.

Quite unexpectedly, performance turned out to be a problem. For PoP (actually, I used open source port of it called SDLPoP) my tool could generate whopping 800'000 frames per second, while for Manic Miner it's only 2000, which greatly reduces the scope of what's possible. For MM I guess it's possible to generate a level per night or so, but later JSW plans will need some optimization.

Actually with the z80 emulation library that I initially used it was 200 fps, then I switched to this one and it was much faster. It's pretty hard to find emulator which wouldn't claim that it's "fast" in the description, but it doesn't look like anyone have ever done any comparison.

One optimization that helped a lot (2.5x or so) is not to try to press any keys when Willy is in the air. Turns out that optimization was buggy, so I switched it off for now. Willy can finish jump and start a new one within one game cycle, so checking that in the beginning of the cycle is not enough.

---

Anyway, I've just finished generating the Level 1, here it is attached as .rzx and as .mp4 file.

565 frames total, score is 1724, and I believe that this score cannot be improved.

Will leave level2 calculating overnight.

lvl1.rzx

[JianYang]

That's really cool. While the score matches the record in the high score challenge, the route is quite spectacular. Can't wait to see more.

 

Have you published your PoP solutions somewhere? I'd love to see that too.

 

Edited March 7, 2021 by JianYang
you -> your

[MtM]

 

Welcome to the forum Crem, very good to have another new member!

 

This reminds me of

 

https://en.wikipedia.org/wiki/Deep_Blue_versus_Garry_Kasparov

 

Human players will always make the most beautiful routes 😉

 

It is very interesting to watch and read about though, and I suppose proves that this is brute force AI,

not intuitive AI. Imagine if the baddies could respond using similar means - we would still all be stuck

on the Central Cavern...

[andrewbroad]

There is brute-force search (trying all possibilities), and then there are heuristics (rules of thumb).

[crem]

Level 2 is ready.

Score=1975, no surprises.

lvl2_20210308-0217.rzx

[crem]

9 hours ago, JianYang said:

 

Have you published your PoP solutions somewhere? I'd love to see that too.

 

I only posted them to PoP speedrunning discord, but here are some examples.

[crem]

6 hours ago, andrewbroad said:

There is brute-force search (trying all possibilities), and then there are heuristics (rules of thumb).

There was actually a 20-page long thread exactly on this topic on chess engine developers forum, whether aggressive variants pruning based on hauristics makes the algorithm non-brute-force. It's just a question of terminology, and most of people seem to agree that brute force with pruning is still brute force, as opposed to novel neural network based algorithms.

For Manic Miner, as I've said, I use score-based pruning. Just keep N results with the best score for every frame. The score is pretty simple:

• Every collected item adds 1.0 to the score.
• If Willy is jumping or falling, that subtracts ~0.001 from the score -- not sure this is necessary.
• If the position of Willy (ignoring the rest of the level state) wasn't seen earlier, add 0.9 to the score.
• In the case of duplicate Willy positions within N frames in the batch, penalize the second one with -0.01, third with -0.02 and so on.
  Those two latest rules help with diversity of positions. Otherwise Willy would stuck in lots of copies of the same position with different world state (e.g. all possible combinations of crumbling platforms)
• If the same Willy's position was seen in previous frames, also penalize that with -0.003 per frame.

It works pretty well, although there are issues. For example, when Willy stays on a crumbling platform, he doesn't change his position for 8 frames (he only starts to fall when the platform fully collapsed), so this is penalized and in general Willy doesn't like to use them.

Also as you could see, it doesn't like to wait, instead it will do useless back and forth movements and so on. Speedrunners actually liked similar behaviour in Prince of Persia, it allows them to time the strat correctly instead of just waiting for the right moment.

[crem]

Level 3, score=1903.

lvl3_20210308-0109.rzx

[IRF]

Your scores achieved using this method have so far matched the highest reported scores in this thread:
http://jswmm.co.uk/topic/421-file-manic-miner-highscore-challenge

 

It will be interesting to see what score your automated method manages to acquire when you reach the Solar Power Generator, where Willy's interactions with the solar beam provide for perhaps a less predictable outcome in scoring terms...

[crem]

1 hour ago, IRF said:

Your scores achieved using this method have so far matched the highest reported scores in this thread:
http://jswmm.co.uk/topic/421-file-manic-miner-highscore-challenge

 

It will be interesting to see what score your automated method manages to acquire when you reach the Solar Power Generator, where Willy's interactions with the solar beam provide for perhaps a less predictable outcome in scoring terms...

Actually currently the tool searches for the shortest route in terms of number of frames, not the remaining air. Optimizing air is a bit more complicated, but doable.