Alyosha
He/Him
Editor, Expert player (3514)
Joined: 11/30/2014
Posts: 2713
Location: US
http://tasvideos.org/userfiles/info/47030679356753062 Here is 3-10 in 422 steps (4 better then Nitrodon's improvement to 426.) That's probably about all the effort I'm going to put into this game. If GBHawk becomes acceptable in the next BizHawk release I'll likely just submit what I have.
Joined: 12/10/2006
Posts: 118
Great work. I'll be exited to watch it.
Player (6)
Joined: 11/26/2007
Posts: 43
Neat, nice to see some work done on the TAS. I was thinking about updating this with the time savings I found a few months ago, but didn't know if anyone would be interested in them. I posted the ILs to speedrun.com, check out my runs there for 2-1 (41), 2-2 (197), 2-3 (98), 2-6 (105), 2-7 (237), and 2-9 (118). Those are all the ones with fewer steps than the currently posted TAS. I stopped checking at 3-4 and on since they were so long. In case you missed these: https://www.speedrun.com/Kwirk/individual_levels Looking forward to the improvements.
Alyosha
He/Him
Editor, Expert player (3514)
Joined: 11/30/2014
Posts: 2713
Location: US
Woah nice work on 2-2 and 2-9, I would never have thought of those! 2-1, 2-3, and 2-6 are in the current WIP. If you are interested 2-4 can be improved 2 steps to 241 and 2-7 can be improved to 236.
Alyosha
He/Him
Editor, Expert player (3514)
Joined: 11/30/2014
Posts: 2713
Location: US
Seeing those improvements in stage 2 gave me some fresh motivation to look for other improvements. I found a pretty significant improvement in 3-4, I haven't optimized it yet but looks like it will be around 12 steps. http://tasvideos.org/userfiles/info/48107498757978657 Here is a new file with ZenicReverie's improvements in 2-2 and 2-9 as well as my new 3-4 in 324 moves (-14 steps) EDIT: 3-4 improved further to 322.
Active player (282)
Joined: 3/4/2006
Posts: 341
This is probably too late, but 3-10 can be improved to 418 steps. The trick is to push the 2x1 block last. EDIT: 416 steps.
Alyosha
He/Him
Editor, Expert player (3514)
Joined: 11/30/2014
Posts: 2713
Location: US
Looks like Kwirk isn't quite done yet. I realized I made a mistake in 2-7 pushing a block unnecessarily, then I noticed that I could also saves 4 steps with a pretty obvious oversight. I don't think there are any other improvements before 2-7, but I'm going over everything again. EDIT: 3-4 improved by one move and one unnecessary push. 3-7 improved by 2 unnecessary moves. 3-9 improved 4 unnecessary moves (my goodness I made a lot of oversights.)
Sand
He/Him
Player (124)
Joined: 6/26/2018
Posts: 154
Exciting news today with #8905: Nitrodon, ZenicReverie, CyberShadow, Sand, Alyosha & Deadcode's GB Kwirk "Going Up?" in 15:15.89 and most of the "Going Up?" levels being bot-optimized. I've been thinking a bit about the "Heading Out?" game mode a bit as well. In that mode, you play a sequence of up to 99 random mini-floors in a row, in one of three skill levels. RTA runners have categories for 10 floors and 99 floors in each of the three skill levels. There's a different number of distinct floors in each skill level: 30 in Easy, 50 in Average, and 40 in Hard. When you play 99 floors, you are guaranteed to get repeats. Internally the game numbers floors thus:
  • 0–29: Going Up?
  • 30–59: Heading Out? Easy
  • 60–109: Heading Out? Average
  • 110–149: Heading Out? Hard
I reverse engineered the Kwirk RNG. The RNG is only used in "Heading Out?" mode. It's seeded from a frame counter mod 60, so there are at most 60 different random floor schedules in each skill level. (The schedules are in fact all distinct, so there are exactly 60 for each skill.) The RNG is used once at the beginning of the run to generate the floor schedule, and then called once when starting each new floor for a 50% chance of flipping the floor layout vertically. There's no way to manipulate the RNG while playing, so which floors get flipped can also be considered an immutable part of the floor schedule. Vertical flips don't change anything really: if you have a solution already, just change all Up moves to Down and vice versa. One idea would be to make a TAS that does 99 "Heading Out?" floors in each of the three skill levels. Pre-solve every floor in the selection pool, and choose an RNG seed that produces the schedule of 99 levels that is fastest to solve. "Heading Out?" floors are smaller (maximum 8×6) than "Going Up?" floors and probably easier to solve. But another idea I had is an "all unique floors" TAS. This would mean playing until you've finished all 30 distinct Easy floors, all 50 distinct Average floors, and all 40 distinct Hard floors (ignoring vertical flips). This would allow you to choose any number of floors, and play the same skill level more than once. For example, you might play a run of 40 floors in Hard to hit 36 distinct floors, then start a new run with a different seed to play 12 more floors and collect the remaining 4 floors. (These numbers are made up.) It adds an additional dimension to the optimization: not only solving each floor as fast as possible, but choosing a good route through seeds in each skill level in order to see all the distinct floors as fast as possible. There's a "magic" seed, 40 42, in the Easy skill level that hits all 30 distinct floors in the first 30 levels. There's no such one-shot seed for Average and Hard. Without restarting, the seed that hits all distinct floors in Average in the least number of floors is seed 20, requiring 88 floors to see 50 distinct. In Hard, the seed that hits all distinct floors without restarting in the least number of floors is seed 34, requiring 60 floors to see 40 distinct. These could likely be done faster with judicious restarts. Caveat: I haven't carefully checked my reverse engineered floor schedule generator for accuracy, so these specific numbers may be inaccurate.
Sand
He/Him
Player (124)
Joined: 6/26/2018
Posts: 154
Sand wrote:
I've been thinking a bit about the "Heading Out?" game mode a bit as well. In that mode, you play a sequence of up to 99 random mini-floors in a row, in one of three skill levels.
These are my Kwirk TAS utilities:
git clone https://www.bamsoftware.com/git/kwirk.git
I reverse engineered how floors are stored in the ROM. The rip-floors script extracts floor layouts and writes them to a file. The floors/ directory has all the floor layouts, including both non-inverted and inverted versions of the "Heading Out?" floors. The solver/ directory contains my optimizer. It can't solve all the "Going Up?" floors, but the "Heading Out?" floors are easier. I posted solutions for all 120 floors (non-inverted and inverted) at Wiki: GameResources/GB/Kwirk#HeadingOut. Caveat: I haven't actually tried these in an emulator. My thought is that we can also try solving them with DDD-Kwirk as a check against error. The total frame count for each floor may be off by a constant, because I just hacked in an exit staircase at the left side of each floor. I was slightly incorrect in Post #527972 when I said that inverting doesn't affect the time to complete a floor. It's true that the central portion of the floor is equivalent, but the entrance/exit passages are carved out after the central part is inverted, and therefore may change length when the floor is inverted. For example, these are the non-inverted and inverted versions of floor 31. (# = wall, 1 = player, . = empty, a = block, ~ = hole.) Note how there is an extra bend in the entrance/exit passages in the inverted version:
31
####################
####################
####################
####################
####################
####################
######........######
######........######
......~.####......1#
######..####..######
######.a......######
######.#......######
####################
####################
####################
####################
####################
####################
31i
####################
####################
####################
####################
####################
####################
######.#......######
######.a......######
....##..####..##..1#
###...~.####.....###
######........######
######........######
####################
####################
####################
####################
####################
####################
The solutions are therefore of different lengths.
31   429 frames  44 steps  WWWWWNWWWWWWSSWSEEEEESENNNENWWWWWWNWSSWWWWWW
31i  447 frames  46 steps  WWSWWWWSWWWWWNNWNEEEEENESSSESWWWWWWSWNNWWWNWWW
Post subject: Heading Out? routing
Sand
He/Him
Player (124)
Joined: 6/26/2018
Posts: 154
Sand wrote:
But another idea I had is an "all unique floors" TAS. This would mean playing until you've finished all 30 distinct Easy floors, all 50 distinct Average floors, and all 40 distinct Hard floors (ignoring vertical flips). This would allow you to choose any number of floors, and play the same skill level more than once. For example, you might play a run of 40 floors in Hard to hit 36 distinct floors, then start a new run with a different seed to play 12 more floors and collect the remaining 4 floors. (These numbers are made up.) It adds an additional dimension to the optimization: not only solving each floor as fast as possible, but choosing a good route through seeds in each skill level in order to see all the distinct floors as fast as possible.
A route in Heading Out? mode is a set of RNG seeds, paired with a number of floors to play in each seed before bailing out and starting the next seed. Optimizing a route is equivalent to solving an instance of the weighted set cover problem, except for a few minor details like menuing. The decision version of set cover is NP-complete, but there are few enough seeds and floors involved that solving it for Kwirk is tractable. Below I'll show routes I computed, based on optimized frame counts per floor and some quick measurements I did of the time between levels and seeds. Let's take Hard for an example. The universe U is the set of 40 distinct floors we need to cover: {110, 111, 112, …, 149}. We have 60×99 = 5,940 sets to work with, where each set represents a seed (0–60) and a number of floors to play in that seed (1–99). For example, S0,5 = {121, 122, 124, 130, 148}, because those are the distinct floors you cover if you play the first 5 floors of seed 0. (Refer to the floor schedules.) We need to find a collection of Sseed,n sets whose union is U. The optimization part is that each Sseed,n has an associated weight Wseed,n, which represents the number of frames needed to restart a run and play the specified number of floors into the seed, taking into account the time needed to actually solve the floors, as well as the animated transitions between them. The collection of sets must not only cover U but also have minimum combined weight. To solve it, we can represent the instance of weighted set cover as an integer program. (I got the idea from these lecture notes.) A is a 5940×40 matrix, where 5,940 is the number of Sseed,n sets and 40 is the size of U (the number of distinct floors in Hard). Each column of A is a 0–1 vector that indicates what floors are covered by the corresponding set. For example, the fifth column of A, corresponding to S0,5, has a 1 in the positions for 121, 122, 124, 130, and 148, and a 0 in all other positions. c is a 5,940-vector of weights for each set. The integer program is: minimize: cTx subject to: Ax1, x integer, 0x1 What this means is: all the elements of the solution vector x have to be either 1 or 0 (we either include a set or we don't). The matrix product Ax tells us how many times each floor gets played for a given solution vector x; all elements of this product must be at least 1 (we have to cover every floor). And finally, the x we find that satisfies these constraints should minimize the total weight cTx. I thought I might have to settle for approximation, but I threw the matrices and vectors into scipy.optimize.milp and it found exact solutions without any problem. The program to do this is headingoutroute in my repository. In order to know the weight of each seed+n combination, we need to know not only how long it takes to play each floor, but also how long it takes to transition between floors on the same seed, and how long it takes to end a run, navigate the menus, and start a new seed. I timed two floor transitions at 222 and 224 frames, so I estimated 223 as an average cost. I timed a run restart at about 646 frames total: 209 frames to play the victory jingle, 109 frames to navigate menus and change the number of floors, and 328 frames to play the entrance jingle. These estimates don't include time waiting for the next seed, but that's at most 59 frames each time we have to do it, and we have some flexibility because we can play the seeds in any order. The estimates also don't account for varying menuing times to change the number of floors between runs, but I am treating those differences as negligible. Here are the optimized routes. Unsurprisingly, the optimizer found the "magic" seed 42 in Easy that covers all floors with no restarts. In Average and Hard, it manages to cover all the floors with just one repeated floor (underlined) in each case. Easy: total frames 17,085, total floors 30
Seed# FloorsFloors
423032i, 35i, 55i, 46, 59, 45i, 49i, 58, 56, 33, 30i, 57, 48i, 31i, 47i, 51i, 37, 41, 38, 44i, 50i, 34i, 42i, 53, 43, 54i, 40i, 36, 52i, 39i
Average: total frames 38,210, total floors 51
Seed# FloorsFloors
114109i, 100i, 62, 83
125105i, 94, 104, 77i, 99i
172567i, 78, 84i, 69, 75, 61, 79, 88, 72, 85, 81, 70i, 66, 92, 86, 98, 73i, 71i, 108i, 106, 65, 63i, 107i, 64i, 80i
321102
36260, 101i
45490, 103, 87, 76i
52474i, 89, 93i, 68i
54682, 91, 97, 78, 96, 95i
Hard: total frames 39,113, total floors 41
Seed# FloorsFloors
214125, 134, 114i, 145i
263137i, 140i, 130i
3428120, 133i, 138i, 110i, 118i, 123, 139, 119i, 113i, 146, 148i, 111i, 144, 143i, 140, 131i, 142i, 136i, 149, 116, 112, 147i, 121i, 129i, 127i, 141, 135, 115i
352124i, 117
584128i, 132, 122i, 126
If the frame count estimates are accurate, a full "Heading Out?, all unique floors" run will take about 26m13s.
Post subject: Heading Out? WIP (Easy floors)
Sand
He/Him
Player (124)
Joined: 6/26/2018
Posts: 154
Here's a WIP draft of Heading Out? mode, the 30 floors of Easy only. It navigates the opening menus, waits for RNG seed 42, then plays each floor using precomputed solutions. Link to video BizHawk file With this TAS I'm trying something new (at least for me). All the inputs for the movie are generated by a Lua script. The main code block looks like this:
Language: lua

savestate = run_until_exec(savestate, nil, TITLE_SCREEN_ADDR) console.log("title screen") savestate = earliest_effective_frame(savestate, function (s) return savestate_joypad_set(s, {Start = true}) end, function (s) return run_until_exec(s, 32, MENU_ADDR) end) console.log("select game") savestate = select_menu_item(savestate, 1) -- Heading Out? console.log("select skill") savestate = select_menu_item(savestate, 0) -- Easy console.log("select course") savestate = select_num_floors(savestate, 30) console.log("select display") savestate = select_menu_item(savestate, 1) -- Bird's-eye View console.log("heading out confirm") savestate = earliest_effective_frame(savestate, function (s) return savestate_joypad_set(s, {[menu_confirm_button(s)] = true}) -- Start end, function (s) return run_until_u8_is(s, 100, RNG_SEED_ADDR, 42) end, true) console.log(string.format("rng seed %d", savestate_read_u8(savestate, RNG_SEED_ADDR))) assert(savestate_read_u8(savestate, RNG_SEED_ADDR) == 42) for _, floor in ipairs{"32i", "35i", "55i", "46", "59", "45i", "49i", "58", "56", "33", "30i", "57", "48i", "31i", "47i", "51i", "37", "41", "38", "44i", "50i", "34i", "42i", "53", "43", "54i", "40i", "36", "52i", "39i"} do console.log("floor", floor) local solution = SOLUTIONS[floor] savestate = play_floor(savestate, solution.moves) end
The core feature of the script is a function that finds the earliest frame at which an input has an effect. You give it a function to execute that enters the input, and another function to test whether the input had an effect. The function tries the input at the current frame, then runs the emulator ahead for a few frames to see if anything changed. If not, it rewinds to before it tried the input, advances one frame, and tries again. The first stanza of code is an example. function (s) return savestate_joypad_set(s, {Start = true}) end tells the function to try pressing the Start button. function (s) return run_until_exec(s, 32, MENU_ADDR) end means to try running up to 32 frames ahead, checking to see if the emulator executes the main menu subroutine. Other functions, like select_menu_item and play_floor, are implemented similarly, finding the earliest frames for menu inputs and player movements respectively. Here's a video of the Lua script running in BizHawk at 400% speed. It's super jittery because of the repeated advancing and rewinding to find the earliest frame for every input. Link to video
Post subject: 27 frames to push a block into a hole, not 28
Sand
He/Him
Player (124)
Joined: 6/26/2018
Posts: 154
EDIT: This was incorrect, see Post #528398. The execution Lua script doesn't have move costs hardcoded. After making a move, it tries the next move at multiple offsets to find the earliest frame where an input has effect. It finds the move costs that are already known, e.g. 9 frames for a move into an empty square, 10 to push a block, 12 to push a turnstile, with one exception. Pushing a block into a hole consistently takes 27 frames total, not the 28 frames reported at Post #527986. For example, applying this patch to the Lua script to log move costs:
Language: diff

diff --git a/tas.lua b/tas.lua index 1886e26..19aa575 100644 --- a/tas.lua +++ b/tas.lua @@ -717,6 +717,7 @@ end local function play_floor(savestate, schedule) console.log("executing schedule", schedule) savestate = run_until_exec(savestate, nil, SWITCH_PLAYERS_ADDR) + local prev_frames for i = 1, string.len(schedule) do local code = string.sub(schedule, i, i) local button = ({ @@ -732,6 +733,11 @@ local function play_floor(savestate, schedule) end, function (s) return run_until_player1_moves(s, 16) end, true) + local frames = savestate_frame_count(savestate) + if prev_frames ~= nil then + console.log("exec", code, frames - prev_frames) + end + prev_frames = frames end return savestate end
results in this log for floor 56:
floor	56
executing schedule	WWWWWWWNWENEESWWWWSNWWWSWWWWWW
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	N	9
exec	W	12
exec	E	9
exec	N	9
exec	E	9
exec	E	9
exec	S	9
exec	W	10
exec	W	10
exec	W	10
exec	W	27
exec	S	12
exec	N	9
exec	W	12
exec	W	9
exec	W	9
exec	S	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
exec	W	9
Despite the thread for #8905: Nitrodon, ZenicReverie, CyberShadow, Sand, Alyosha & Deadcode's GB Kwirk "Going Up?" in 15:15.89 saying 28 frames, I checked the input file and it actually uses 27 frames. I didn't see anything to improve there. I re-ran both the per-floor and route optimizers. The frame count for a few floors decreases slightly, but the solutions don't change in any significant ways. The RNG seed segments remain the same.
Post subject: Re: 27 frames to push a block into a hole, not 28
Sand
He/Him
Player (124)
Joined: 6/26/2018
Posts: 154
Sand wrote:
Pushing a block into a hole consistently takes 27 frames total, not the 28 frames reported at Post #527986.
Never mind, I was mistaken. The inputs are still spaced 28 frames apart in the movie file. It was an artifact of the way the script counts frames and how the script decides when an input has taken effect. In floor 56, for example, the 4 W moves in the middle have 2× block push, 1× hole fill, 1× step, the costs of which we think of as
exec	W	10
exec	W	10
exec	W	28
exec	W	9
But the script considers a move accomplished (and starts looking for the first possible frame for the next move) when Kwirk's position in memory changes, not when the hole is completely filled. So it ends up being the same total number of frames, just subdivided differently:
exec	W	10
exec	W	10
exec	W	10
exec	W	27
The script was just attributing the 18 frames to fill the hole to the next move, rather than the current move. The 27 comes from 18+9 (fill hole and take a step), not 10+17 (push block and fill hole).
Post subject: Left + Select cheat code
Sand
He/Him
Player (124)
Joined: 6/26/2018
Posts: 154
I just learned there's a cheat code in Heading Out? mode. If you hold the Left and Select buttons while confirming the "Select Display" menu, then the floor schedule will be overwritten to play all the floors in the chosen skill level, exactly once and in order. Each floor may still be inverted or not, but the cheat code skips seeding the RNG, so the inversion schedule is always the same as well. (Unless you've played an earlier round to set the seed.) This cheat code would obviously be the fastest way to play all floors in Heading Out? mode, but I'm not planning to use it in the TAS, because it would take away the fun of RNG seed routing. Also, while reverse engineering, I discovered a feature that I couldn't find documented. If you hold the B Button while playing, it disables movement auto-repeat. You have to release and press the D-Pad for each step. It's probably not useful for a speedrun.

1711718966