Automated generation of Manic Miner speedrun/walkthrough

[crem]

15 hours ago, jetsetdanny said:

Then it's a confirmation that one can't go any higher, and it sets a "crossbar" for humans to reach (if they haven't already).

Strictly speaking, the tool's search was not exhaustive, so while I'm sure all "micro-optimizations" are done perfectly, in theory it's possible [although unlikely] that the tool missed some more "strategic" ideas.

It may come from one of three sources:

• The algorithm is a bit "greedy", so if there's a fast way to collect 2-3 items, it may prune more optimal (in long term) route which takes 0-1 items within the same initial time.
• The tool doesn't like doing nothing, so strats that involve waiting could be missed.
• If something (like crumbling platform configuration) had to be set up earlier in the level to be used much later on "way back", it may also be missed (although I think there are no levels like this).

In fact, the tool DID miss best routes for the first attempts, especially for the first half of levels before I tuned scoring:

• Level 2 "The Cold Room" - in the end there's some waiting involved. Initially waiting was penalized too much, so after ~1 second Willy gave up and decided to take another round in the level.
• Level 4 "Abandoned Uranium Workings" - there in one of attempts Willy was too greedy, and after seeing that he can take 2 items quickly, it pruned more optimal route which involved taking the furthest key first.
• Level 5 "Eugene's Lair" - this one was the hardest. If I didn't know that the record is higher that the script got, I would stop. In the optimal route, the first item is collected after the less optimal route already has 2 items, so it was pruned. The optimal route was penalized even more because it involved waiting of the "night-time toilet". The route that the script kept generating is similar to the optimal route, but the first item to take was the one above the "night-time toilet".
• Level 7 "The Vat" was also not done from the first attempt. As it involved some waiting, Willy initially wasted some frames by jumping. Out of all levels, I think this has the largest probability (although still very low) of being suboptimal. Maybe I'll rerun the latest version of the tool on this level.
• In level 12 "Return of the Alien Kong Beast", the item right below the beast was tempting to take in the beginning of the route rather than just before the final jump. While I suspect that at that point the scoring was well tuned to find the right route without needs for nudges, I just programmed it to ignore this item completely in order not to waste search capacity.

Notes about other levels:

• In level 3 "The Menagerie" two routes (bottom key first vs last), time till the first key was comparable, so even with early untuned script it worked well, considering both routes.
• In level 13 "Ore Refinery" it looked like large number of order in which items are collected are possible, so I ran my tool at extreme settings to ensure nothing is missed.
• In level 17 the first item is a bit inconvenient to take, so initially Willy preferred to go to the right right away. While it would likely find the optimal route without my help, I helped it a bit by counting the leftmost key as two so that it preferred to take it a bit more.

[Norman Sword]

I now have a full working version of automatic play.  The time between what is written and my final version. Depends on my own criteria of quality control.

All the room layout data has been part  compressed. This was to allow the addition of movement data.
I added a new room draw routine to take the new compressed data.
I added a routine to switch normal keyboard input or auto keyboard input
I added a room selection input
I added the graphics (with doors that open/close) to the room selection input
! added the room name being displayed at room selection.
I added a display for the mode

Besides the final barrier graphics- I am now going to design some of my own graphics and also perhaps modify the title screen graphics. 

An example of problems: left room and came back to see 16 Willies dancing across the screen- the score was over 200000. that version would only stop when the score overflow was big enough to cause problems. 

 

Addendum ;- with the Data I used the score for all the levels and back to the Central Cavern is a mere 39144. (with no loss of life)  and no aching fingers. Drink a cup of tea and watch.

 

 

Edited March 16, 2021 by Norman Sword
Correction of information.

[crem]

A status update regarding lvl19.

2 days ago I did the first experimental run of my script. It only found the solution with score=1124 (1 point below @jetsetdanny), and it was clear the scoring was poor.

Yesterday I fixed the scoring and did a very quick run which gave score=1133. So I thought all looked good and started a long run overnight, but it didn't find any solutions at all.

While I'm figuring out what's wrong, here is the current lvl19, score=1133. It's likely that it's not the best solution so far.

lvl19_20210317-2027.fixed.rzx

[IRF]

Well done, crem and your algorithm!

There were a couple of significant changes in the route taken this time, compared with the previous recording which can be seen here http://jswmm.co.uk/topic/580-automated-generation-of-manic-miner-speedrunwalkthrough/?do=findComment&comment=12887

Firstly, the fact that Willy collected the items in a different order, this time grabbing the bottom-right item first (which is of course the closest one to Willy's starting position, so that probably saves some walking time).

Secondly, this time Willy avoided using the platform with the blue horizontal guardian on it as a step up to the top platform, preferring instead to climb up there via the centrally placed platform [the one which lies directly above Willy's head at the very start of the cavern].  That is a significant tactic in terms of minimising the number of jumps that pass through the solar beam whilst it is shining straight down from its source (reducing the amount of air sapped by the beam, compared with the route which sticks closer to the right).

[IRF]

The difference in final score between Danny and the algorithm for 'Solar Power Generator' is eight points.  This equates to Danny having spent a single additional timeframe with the beam passing through two cells occupied by Willy (4 extra 'saps' of air per cell occupied by Willy's white INK).

Crem, will you be updating your earlier post to reflect the sequence of movements which led to your improved score in the Solar cavern?:

It occurs to me that the sequence of movements in that cavern could be re-run (perhaps using Norman Sword's idea for an automated MM tool?) in a modified game that has the solar beam switched off (POKE 36230,24 should do the trick), and that would then enable us to quantify precisely how many points were lost as a result of the solar beam's effect.

Edited March 18, 2021 by IRF

[crem]

I've updated the route post.

As far as I remember, in the score=1133 run, 160 points were lost due to the solar beam.

And in my score=1124 run, 220 points were lost.

I can re-confirm that in the evening. I can also upload my 1124 run if that helps.

Edited March 18, 2021 by crem
224 -> 220

[crem]

Here is the score=1124 attempt of the level 19.

Here 220 points were lost due to the solar beam, while in the current record of 1133, only 160 points were lost.

The route is quite different, as you can see.

out.rzx

[IRF]

On 3/14/2021 at 9:42 PM, MtM said:

I wonder though, is there not a superfluous jump in this level [first Kong cavern], after the second lever has been thrown?

Willy was passing time, waiting for the rolling rock beneath to get out of the way.  I don't think it could have been completed any quicker if he hadn't done that jump you refer to. 🤔

[IRF]

1 hour ago, crem said:

I've updated the route post.

Good stuff.

Just to be pedantic, does the cavern 6 entry in that post need updating as well (as you've since completed it without standing still in the first frame)?

Edited March 18, 2021 by IRF

[jetsetdanny]

Well done, crem! 👍

So no surprise there, my score has been improved. The route that the algorithm took is exactly the same as mine. So if the improvement means that it managed to avoid the Solar Beam for one time frame longer than I did, I've nothing to be ashamed of, I would say 🙂.

I'm not sure if I will ever be able to force myself to repeat that result. I should, but recording the Solar Power cavern is a real pain, as you can't know whether the beam touched you or not (when talking about split-second contact). I tried to "control" it by looking at the amount of Air left on the status bar (as compared to my previous best recording). But it's really hard to tell if you just look at the remaining Air on the status bar.