Automated generation of Jet Set Willy speedrun/walkthrough

[jetsetdanny]

Thanks for the update, crem! 🙂

[IRF]

EDIT: I've shifted this post over onto RuffledBrick's Speedrunning topic, as it seemed to be more pertinent there (and less of a potential distraction from the details of crem's algorithm).

Edited May 13, 2021 by IRF

[crem]

As I was afraid, the first attempt with the dynamic programming didn't work that well. At every moment I kepts 100'000'000 states with the furthest progress, but given how many variants to collect objects are, that was not so simple. The resulting route turns out to be too greedy (first collect whatever is easy and then travel across entire map again to collect the rest).

While I'm working on the improvements, here is the video of the walkthrough for MaxLives+Warpless category (at 25fps). I'm not attaching it here as the file is 50MB in size, not sure whether that's a good use of forum's space.

Link to the video: http://crem.xyz/jsw_warpless_maxlives.html

It's not a proper walkthrough, it's actually sequence of in-room routes spliced together. That's why timer number of lives and collected items restore between rooms, and Willy jumping state during the room transition is sometimes incorrect.

[MtM]

Video didn't work at all for me Crem - I am on Firefox latest version.

[crem]

3 minutes ago, MtM said:

Video didn't work at all for me Crem - I am on Firefox latest version.

It seems that firefox doesn't support mkv files https://bugzilla.mozilla.org/show_bug.cgi?id=1422891, and that's what OBS took the recording in. You can right click on it to download and open with some other player though.

I'll try to record it in other format in future (hopefully just .rzx 🙂)

[MtM]

5 hours ago, crem said:

It seems that firefox doesn't support mkv files https://bugzilla.mozilla.org/show_bug.cgi?id=1422891, and that's what OBS took the recording in. You can right click on it to download and open with some other player though.

I'll try to record it in other format in future (hopefully just .rzx 🙂)

Ah good suggestion, I did just that and watched it thanks.

[Spider]

Watched it, excellent. Did do a quick mp4 conversion of it (36mb vs 55 with a bit of a resoultion reduction) but not much point me uploading that now. 🙂

[crem]

A message of assorted topics about how everything is failing but there's hope. 🙂

(1) It is clear now, that the attempted brute force solution to build the route doesn't work.
It may find good enough walkthroughs and maybe even better than the currently best known routes, but it surely won't find the optimum.

My nightly attempt to re-run the same Warpless+Maxlives lives turned out to give even longer (by 23 frames), despite having much wider search (7'571'762'474 states instead of 2'439'193'796) and entire evening to fighting algorithm's memory hunger.

The route is slightly different, here it is: https://www.twitch.tv/videos/1023369202 (I found that the easiest way to record and share the video is to stream on twitch).

I won't try any complex improvements to this algorithm. Instead I'll do one small tweak (point 3 below), run the algorithm for all the categories (4), and then probably will try a different approach (6).

 

(2) Combining the spliced walkthrough to the proper one didn't work for some of room transitions.

(technical stuff hidden in spoiler)

Spoiler

As I described, when room entrypoints are close enough and transition happens at the same frame of the route, I combined that into sets that I called entryways (or portals). All the routes are then generated "from any entrypoint to all exitpoints". I assumed that by going from the end of the walkthrough to the beginning, it would always be possible to build the route of the same characteristics, but it turned out to be not true.

Anyway, that's an easy thing to fix. I split such problematic entryways into several and recalculate affected routes. This is what's happening now, should take 1 day.

 

(3) The current algorithm is too greedy, I'll try to come up with better game progress metric, which should help but not by much.
The algorithm prefers to grab lots of easy items right away, and then struggles with the remaining ones.

Currently, only "number of collected items" is used as a metric to track progress. Replacing it with a better one can improve things. I'll try to do the following:

• Make items valued differently (e.g. Ballroom West items are cheapest as they are easily accessible and plentiful).
• Penalize some sets of remaining items (e.g. if two remaining items are in different corners of the map).

That will require some manual judgment though.

 

(4) I'm still planning to generate all the speedrun categories using the current algorithm.
But first I'll have to fix issues (2), (3), and for the realtime runs, do the (5).

 

(5) For In-game-time optimization, I use number of frames. For Real-time runs, I'll need number of CPU cycles.

My plan is to measure number of CPU cycles for every of ~250000 routes that were generated (including time to draw the next room) and use it as the edge cost in the algorithm. I expect this process to take ~3 hours.

Some notes regarding that:

• I'm not sure how precise is the emulator library that I use. I surely don't emulate any input or memory delays, but otherwise it should be fine.
• What to do with variable number of lives affecting speed? I can either test a few routes and come up with a formula how number of lives affects frame time, or I can run all routes for all number of lives. Then it will take ~24 hours, still probably that's the easiest. 🙂

 

(6) Second attempt will be an AlphaZero-style neural network (if there will be a second attempt).
If the results of the current algorithm won't be satisfiable, the next thing I'll try (given enough time and enthusiasm) is to try a AlphaZero-style reinforcement learning.

For approach I'm very confident that it will work when implemented, but it's not very fast to write. Probably 1-2 months worth of winter evenings, which translates to 3-4 months of summer evenings.. But depends on weather. 🙂

[MtM]

Don't take this the wrong way Crem - but is it worth the effort? Sounds like a lot of time and work. If you are doing it for a specific purpose, some kind of thesis submission / research etc. then fair enough. Likewise if it is just for your own enjoyment, and ours too in a secondary fashion.

[IRF]

I think it's worth it.  The exercise has revealed some very neat and nifty manoeuvres which I've managed to replicate myself - first in Manic Miner, and now in JSW. 😀