Submission #9257: Sand's GB Kwirk "Heading Out?, all floors" in 25:15.19

Kwirk is a block-pushing puzzle game for Game Boy. This is a speedrun of the game's "Heading Out?" mode, which is a time attack of small puzzles, drawn randomly. The goal of this run is to clear all 120 unique floors of this mode as fast as possible. Besides solving each individual floor quickly, this requires manipulating RNG to access unplayed floors.

(Link to video)

Suggested screenshot: frame 21507

Kwirk has two game modes. Going Up? mode is the "adventure mode": you play 30 full-size floors in a fixed order across three difficulty levels, Easy, Average, and Hard. Heading Out? mode is the "time attack mode": you choose a difficulty level and a number of floors, and the game gives you that many mini-floors to play, with time-based scoring. The floors in Heading Out? mode are drawn randomly from a pool of 120, distributed over the three difficulty levels: 30 in Easy, 50 in Average, and 40 in Hard.

I started writing a Kwirk solver with the idea of applying it to Going Up? mode. This turned out to be harder than expected, as some of the floors are combinatorially complex. Luckily, #8905: Nitrodon, ZenicReverie, CyberShadow, Sand, Alyosha & Deadcode's GB Kwirk "Going Up?" in 15:15.89 appeared and did Going Up? better than I would have, using a tuned solver and large amounts of computation and storage.

That still leaves Heading Out? mode, which does not have a published TAS. The puzzles in Heading Out? are smaller, enough that my relatively simple solver could find optimal solutions for all of them. While the floors are smaller, there are more of them: 120 compared to 30 in Going Up? mode. And while you can choose the difficulty and number of floors (from 1 to 99), the actual floors you get are randomly selected by the game.

RTA runners play Heading Out? in a single segment of 10 or 99 floors, taking whatever floors the RNG gives them. (Which entails playing some floors more than once, in the 99-floor case.) For the TAS I decided to do something different: clear all 120 floors at least once, over multiple segments (allowing to re-seed the RNG between segments, at the cost of time). This is a new, invented category, but one I think is well-suited to a TAS. It adds another dimension to the optimization, because in addition to playing each floor optimally, you have to coax the RNG into giving you floors you haven't seen yet.

The video encode attached to this submission has a tracker that shows which floors have been cleared so far.

The solver for individual floors is nothing very special. It is the typical breadth-first, uniform cost search kind of thing, with a reimplementation of the game rules and knowledge of the cost in frames of each action, such as: 9 frames to step into an empty tile, 28 frames to push a block into a hole, 12 frames to rotate a turnstile. As there is no randomness within floors, all solutions can be pre-computed as fixed move sequences. I am confident the per-floor solutions are optimal.

The game counts "steps" as well as frames. This run tries to minimize real time (frames), not steps or in-game time.

The floors in Heading Out? are internally numbered 30–59 for Easy, 60–109 for Average, and 110–149 for Hard. Floor numbers 0–29 are used for Going Up? mode.

The RNG is seeded, at the start of each segment, with a frame counter mod 60. This means the only possible seeds are 0–59, and you can get any seed you want by waiting at the confirmation menu for up to 1 second. A complete schedule of floors is generated as soon as you hit Start. There is no way to affect the RNG while playing a segment, only between segments. In the video encode attached to this submission, you can see the constantly updating frame counter that is used to set the RNG seed (in gray), and the seed used for the current segment (in white).

Each floor has a 50% random chance of being inverted (flipped vertically). This does not have much of an effect on gameplay or routing. The inverted version of a floor has essentially the same solution as the normal version, but it may be slightly faster or slower to solve, because inversion affects the shape of the passages into and out of the central puzzle area.

It might seem that there are only 60 possible floor schedules per difficulty level, which is what I thought at first. But there's an important complication. The game keeps track of the 20 most recently played floors, and will never repeat a floor that is in that set. This filter remains in effect across segments and even across difficulty levels, because the set of recently played floors is indexed relative to the start of the difficulty level. This means, for example, that if you have just cleared floor 35 (which is index 5 in Easy) and started a new segment, none of the next 20 floors can be 35 (index 5 in Easy), 65 (index 5 in Average), or 115 (index 5 in Hard). Massaging the random floor generation algorithm with this cross-segment carryover is critical for getting long sequences of not-yet-played floors.

But it's not simple to optimize. (If you think of it as a graph search problem, the branching factor is about 181, because after clearing a floor you have the option of continuing in the current segment, or starting a new segment in one of 3 difficulty levels and one of 60 random seeds.) The route used in this run is the result of a computer search. In the end I turned to a genetic algorithm to find the segment route shown below, which has 8 segments and 1 repeated floor. I am pretty happy with this route, but it has no proof of optimality. It may be possible to improve on this route, whether by using fewer segments, repeating no floors, repeating a shorter floor, getting more favorable inverted floors, or spending less time waiting for RNG seeds to roll around.

Seed 42 in the Easy difficulty level is extremely lucky. On a freshly started game, seed 42 hits all 30 floors exactly once with no repeats. The route starts there, because it's hard to beat for efficiency. It only works when it's the first segment, and the history of recently played floors is empty. If you've already played a segment, the recently played floors filter will cause you to get a different sequence of floors that no longer covers all 30 possibilities cleanly.

The route consists of 8 segments. Only 1 floor is repeated, floor 90 in the Average difficulty level. An "i" suffix means the inverted version of a floor.

There are routes with no repeats, but they are slower overall, because they require more segments. The scrolling animation between floors in a segment takes about 3.5 seconds, while starting a new segment (with the associated fanfares, menuing, etc.) costs around 11.5 seconds. For perspective, this route with 1 repeat is 171 frames (2.9 seconds) faster than the fastest route I found with no repeats. It's a small fraction of the overall time, but once you've optimized every individual floor, the only improvements can come from better routing.

The sum of in-game times per segment is 23:39.

I won't comment on every floor, just some of the more noteworthy ones.

Floor 30i is the shortest floor in Easy, with 26 steps and 240 frames.

Perhaps surprisingly, it is not the shortest floor overall, which is rather floor 76 in Average.

Floor 52i is the longest floor in Easy, with 56 steps and 528 frames.

Floor 148i is the longest floor in Hard, and the longest of the run overall, with 132 steps and 1239 frames.

Floor 131 is the shortest floor in Hard, with 34 steps and 318 frames.

Floor 141 is the only floor that is not sight-readable, by which I mean it violates a convention that is observed everywhere else in the game. In the initial configuration, the west spoke of the "T" turnstile covers a hole tile, which never happens in any other floor, whether in Going Up? or Heading Out? mode. Although you cannot see it at first, without that hole the floor is unsolvable.

I know this because my map extraction script did not handle this case correctly at first :)

Floor 86 is the longest floor in Average, with 128 steps and 1218 frames.

There are two consecutive segments that both have a difficulty level of Average and a floor count of 15; only the RNG seed is different. Because the difficulty level and number of floors is the same, we do not even have to enter the menus between these two segments, just wait for the next RNG seed. This is not something the route optimizer was trained to look for, just a lucky coincidence.

Floor 76 is the shortest floor in Average, and the shortest of the run overall, with 26 steps and 238 frames.

Here we repeat floor 90, which is the only repeated floor of the run. It is a pretty short floor, 41 steps and 388 frames. It was played for the first time at 16:56.

My posts documenting the development of this run start at Forum/Posts/527972.

My source code and notes are in a Git repository:

git clone https://www.bamsoftware.com/git/kwirk.git

nymx: Claiming for judging.

nymx: Re-uploading to correct any possible cycle count issues.

nymx: I'm a big fan of solving tools that optimize game-play. This TAS is no exception. You caught my attention, when you confirmed my [6148] C64 Match Blox by nymx in 00:55.66 solutions with math...instead of my brute forcing scripts. So naturally, I find your tools and efforts to have great strength, and I have complete confidence in this run. A lot times, I can't see the end coming, until the last moment. In my opinion, that is the sign of a true solution...where human effort can often be foreseen. On top of all this, finding that RNG seed is also important. I've observed a small group of members that really focus on finding that perfect seed. So, with all that said...I'm always cautious about saying that nothing else can be found, but it sure does look like you have clinched this game. Congratulations on excellent work! I look forward to your future submissions!

Happily Accepting!

fsvgm777: Processing. Dimon12321 is handling the encodes for this one.