crem

I regenerated the Level 4 from the keypresses information, and it worked fine. However, the result turned out to be 1 frame longer than the current record from another topic in this forum. Not sure if it worth sharing before it's polished. 😛
Level 6 and Level 9 have also finished, but they turned out to be even worse (2 and 5 frames slower respectively, if I remember right).
I tweaked scoring a bit (the duplicate Willy position penalization function is sigmoid now rather than linear function) I think it should help.
I've also made the source code of the tool public at https://bitbucket.org/mooskagh/zx-stratfinder/src/master/ if anyone is curious how it's written, wants to adapt it to other games or wants to help.

Thanks for sharing this, crem, it's fascinating! 👍
I meant to make exactly the same comments as Ian made above (great minds...! 🙂), drawing your attention to the highscore challenge scores and the Solar Power Generator, where you will have to optimise the method for the remaining air, as the solar beam is a huge factor there.
I am also wondering about JSW games, as the possible routes will multiply the possible options the algorithm will have to analyse. The original "JSW" may be "relatively" simple in this respect, but if you ever wanted to carry out a similar analysis for other JSW games that have been released so far (a complete list is here), you will find some real behemoths among them. Take sendy (Alex Cornhill)'s "where's woody?" for example. 256 edited rooms (although the player does not have to visit all of them to complete the game - that's another challenge for the algorithm, to determine which rooms can be skipped safely), non-linear, hundreds of possible room exits altogether, so I would think thousands and thousands of possible routes to take (or even more - it will grow exponentially, won't it?). I don't know if you have enough processing power to analyse that one 🤪. But it would certainly be interesting to know how much my best in-game completion time (achieved using the Rollback feature and what I decided, after a careful analysis, was the most efficient route) of 2:10 pm can be improved...
Meanwhile, I am looking forward to your scores in the next MM caverns - it's very interesting, thanks again! 🙂

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.

Level 2 is ready.
Score=1975, no surprises.
lvl2.mp4 lvl2_20210308-0217.rzx

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.

Level 3, score=1903.
lvl3.mp4 lvl3_20210308-0109.rzx

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.
Peek 2021-03-07 19-00.mp4 lvl1.rzx

Some updates on further levels (tl;dr no success yet):
For level 4 ("Uranium"), the computation was completed, but for some reason Fuse fails to open the resulting .rzx file. Will look why is it so when I have time (hopefully today in the evening). I also have keypress information per frame, so if it's the problem with rzx writing and the rest worked fine, there will be no need to redo the calculation.
Level 5 ("Eugene") has the same problem with opening .rzx, but also it didn't find the win. When I woke up today and checked the results, all 35000 states had Eugene already sitting on the top of the portal, making win impossible. I'll restart this level with adjusted scoring (will make it a loss if Eugene sits on the portal).
In the morning I started Level 6 ("Pacman Processing Plant"), Level 7 ("VAT"), Level 8 ("Kong v1") and Level 9 ("Amoebatrons v1"). For levels 2-5, the search with "width" of 35000 states took 6 hours to complete, so I started Levels 6-9 with 50000 to finish by the end of the day.
Level 7 ("The Vat") finished after 7 frames with "no solution found" status. Clearly some bug on my side, will take a look later. Meanwhile, started Level 11 ("Telephones") instead (and later realized that I missed Level 10 "Endorean Forest").

That's indeed true, the main motivation for this is to find something useful for speedrunners, not to have the highest score.
Unlike in solar power generator level, Kong levels are pretty easy to fix. Just consider end of level a loss rather than a win, if Kong is still in its initial position.

That's indeed true, the main motivation for this is to find something useful for speedrunners, not to have the highest score.
Unlike in solar power generator level, Kong levels are pretty easy to fix. Just consider end of level a loss rather than a win, if Kong is still in its initial position.

Level 3, score=1903.
lvl3.mp4 lvl3_20210308-0109.rzx

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.

Level 2 is ready.
Score=1975, no surprises.
lvl2.mp4 lvl2_20210308-0217.rzx

I only posted them to PoP speedrunning discord, but here are some examples.
pop-lvl1-2-3.mp4 pop-lvl4.mp4 pop-lvl7-noending.mp4

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.

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.
Peek 2021-03-07 19-00.mp4 lvl1.rzx

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.
Peek 2021-03-07 19-00.mp4 lvl1.rzx

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.
Peek 2021-03-07 19-00.mp4 lvl1.rzx

The game frame rate and video frame rate have no relation to each other (for games that rely on CPU interrupt frequency there may be differences, but JSW disables interrupts).
The actual game framerate would be somewhere between 9 or 13 fps depending on number of moving objects in a screen, number of lives left, whether the music is on, etc. There's also a difference between ZX Spectrum 48 and later variants as they have slightly different CPU clock speed (3.5MHz for Spectrum 48, almost 3.55MHz for Spectrum 128).
If you record video of the JSW and watch it frame by frame, you'll notice when you go from a frame to the next one, most of the time the image doesn't change. (E.g. if you record at 30fps, and game is ~10fps, only every 3rd frame would show the change).

The game frame rate and video frame rate have no relation to each other (for games that rely on CPU interrupt frequency there may be differences, but JSW disables interrupts).
The actual game framerate would be somewhere between 9 or 13 fps depending on number of moving objects in a screen, number of lives left, whether the music is on, etc. There's also a difference between ZX Spectrum 48 and later variants as they have slightly different CPU clock speed (3.5MHz for Spectrum 48, almost 3.55MHz for Spectrum 128).
If you record video of the JSW and watch it frame by frame, you'll notice when you go from a frame to the next one, most of the time the image doesn't change. (E.g. if you record at 30fps, and game is ~10fps, only every 3rd frame would show the change).

The game frame rate and video frame rate have no relation to each other (for games that rely on CPU interrupt frequency there may be differences, but JSW disables interrupts).
The actual game framerate would be somewhere between 9 or 13 fps depending on number of moving objects in a screen, number of lives left, whether the music is on, etc. There's also a difference between ZX Spectrum 48 and later variants as they have slightly different CPU clock speed (3.5MHz for Spectrum 48, almost 3.55MHz for Spectrum 128).
If you record video of the JSW and watch it frame by frame, you'll notice when you go from a frame to the next one, most of the time the image doesn't change. (E.g. if you record at 30fps, and game is ~10fps, only every 3rd frame would show the change).

The game frame rate and video frame rate have no relation to each other (for games that rely on CPU interrupt frequency there may be differences, but JSW disables interrupts).
The actual game framerate would be somewhere between 9 or 13 fps depending on number of moving objects in a screen, number of lives left, whether the music is on, etc. There's also a difference between ZX Spectrum 48 and later variants as they have slightly different CPU clock speed (3.5MHz for Spectrum 48, almost 3.55MHz for Spectrum 128).
If you record video of the JSW and watch it frame by frame, you'll notice when you go from a frame to the next one, most of the time the image doesn't change. (E.g. if you record at 30fps, and game is ~10fps, only every 3rd frame would show the change).