Post by Sand

Posted: 5/11/2018 12:33 AM
(Edited: 2/9/2020 1:06 PM)

Quote

Alyosha

He/Him

Editor, Emulator Coder, Expert player (3808)

Joined: 11/30/2014
Posts: 2828
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.

Posted: 5/11/2018 5:52 AM

Quote

thommy3

Joined: 12/10/2006
Posts: 118

Great work. I'll be exited to watch it.

Posted: 6/26/2018 9:04 PM

Quote

ZenicReverie

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.

Posted: 6/26/2018 11:24 PM

Quote

Alyosha

He/Him

Editor, Emulator Coder, Expert player (3808)

Joined: 11/30/2014
Posts: 2828
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.

Posted: 6/28/2018 1:52 AM
(Edited: 2/9/2020 1:06 PM)

Quote

Alyosha

He/Him

Editor, Emulator Coder, Expert player (3808)

Joined: 11/30/2014
Posts: 2828
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.

Posted: 7/1/2018 6:28 AM

Quote

Nitrodon

Active player (286)

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.

Posted: 10/5/2019 12:26 AM

Quote

Alyosha

He/Him

Editor, Emulator Coder, Expert player (3808)

Joined: 11/30/2014
Posts: 2828
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.)

Posted: 2/23/2024 4:05 AM
(Edited: 5/7/2024 4:33 PM)

Post subject: Heading Out?

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

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.

Posted: 2/25/2024 3:19 AM

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

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

Posted: 2/27/2024 6:43 AM

Post subject: Heading Out? routing

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

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, S_0,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 S_seed,n sets whose union is U. The optimization part is that each S_seed,n has an associated weight W_seed,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 S_seed,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 S_0,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: c^Tx subject to: Ax ≥ 1, x integer, 0 ≤ x ≤ 1 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 c^Tx. 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	# Floors	Floors
42	30	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

Average: total frames 38,210, total floors 51

Seed	# Floors	Floors
11	4	109i, 100i, 62, 83
12	5	105i, 94, 104, 77i, 99i
17	25	67i, 78, 84i, 69, 75, 61, 79, 88, 72, 85, 81, 70i, 66, 92, 86, 98, 73i, 71i, 108i, 106, 65, 63i, 107i, 64i, 80i
32	1	102
36	2	60, 101i
45	4	90, 103, 87, 76i
52	4	74i, 89, 93i, 68i
54	6	82, 91, 97, 78, 96, 95i

Hard: total frames 39,113, total floors 41

Seed	# Floors	Floors
21	4	125, 134, 114i, 145i
26	3	137i, 140i, 130i
34	28	120, 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
35	2	124i, 117
58	4	128i, 132, 122i, 126

If the frame count estimates are accurate, a full "Heading Out?, all unique floors" run will take about 26m13s.

Posted: 3/19/2024 9:46 AM

Post subject: Heading Out? WIP (Easy floors)

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

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

Posted: 3/20/2024 12:55 AM
(Edited: 3/20/2024 1:40 AM)

Post subject: 27 frames to push a block into a hole, not 28

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

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.

Posted: 3/20/2024 1:38 AM

Post subject: Re: 27 frames to push a block into a hole, not 28

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

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).

Posted: 3/22/2024 7:08 PM

Post subject: Left + Select cheat code

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

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.

Posted: 5/7/2024 7:55 PM

Post subject: Timing transitions between segments

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

Now that we have a list of 14 segments that together cover all unique floors, we have to decide what order to play them in. The order matters for two reasons. First, menuing. Settings carry over between segments, so transitioning from one Average segment to another Average segment, for example, is faster than transitioning from an Average to a Hard, because you don't have to go as deep into the menus. Second: RNG. Recall that the RNG seed is a frame counter mod 60. Depending on where we are in the RNG seed cycle after finishing a segment, we have to wait longer for some seeds that others. (At the same time, forced RNG waiting may make some extra menuing "free", as long as it doesn't come at the expense of something even faster.) I wrote a script to automatically measure the time to transition between each pair of segments. For each segment, it gets into the segment from the title screen (to find the transition cost if that segment happens to be chosen as the first segment), plays through the segment and records the time at the end, then (starting from a savestate immediately after solving the segment), measures how long it takes to get into every other segment. There are two ways to go through the menus and change settings between segments, and the script tries both. It also does every segment in both Diagonal and Bird's-eye views. It also measures the time to complete each floor and transition between floors within a segment. After running for about 9 hours, it outputs a table of 29×28×2 segment transition costs and 122 floor transition costs (there are 120 unique floors, 2 of which get played twice). These are segments.csv and floors.csv in the repository. Here's a sample of segments.csv. It says: from boot, it takes 524 frames to get into the (easy, birdseye, 30, 42) segment (earliest frame that gives the desired RNG seed). At the end of that segment, 17030 total frames have elapsed. To complete the (easy, birdseye, 30, 43) segment and transition into the (average, birdseye, 4, 11) segment takes 17417 frames if you use the B Button to traverse menus, or 17416 if you use the END menu. To complete the (easy, birdseye, 30, 43) segment and transition into the (hard, birdseye, 28, 34) segment takes 17440 and 17379 frames respectively for the B Button and END menu respectively.

from_skill	from_display	from_num_floors	from_seed	to_skill	to_display	to_num_floors	to_seed	reconfigure	frames
				easy	birdseye	30	42		524
easy	birdseye	30	42						17030
easy	birdseye	30	42	average	birdseye	4	11	b	17417
easy	birdseye	30	42	average	birdseye	4	11	menu	17416
easy	birdseye	30	42	hard	birdseye	28	34	b	17440
easy	birdseye	30	42	hard	birdseye	28	34	menu	17379

Why test every segment in both Diagonal and Bird's-eye views? We know from #8905: Nitrodon, ZenicReverie, CyberShadow, Sand, Alyosha & Deadcode's GB Kwirk "Going Up?" in 15:15.89 that Bird's-eye view is preferable during gameplay, because pushing a block into a hole is 8 frames faster. In addition, Bird's-eye saves around 16 frames before the first floor, and between each pair of floors in a segment, as you can see in this excerpt from floors.csv (compare corresponding transition_frames between display=diagonal and display=birdseye):

prev_floor	floor	display	seed	num_floors	floor_seq	transition_frames	floor_frames
	109i	diagonal	11	4	1	336	1101
109i	100i	diagonal	11	4	2	230	523
100i	62	diagonal	11	4	3	229	585
62	83	diagonal	11	4	4	229	259
	109i	birdseye	11	4	1	321	1101
109i	100i	birdseye	11	4	2	214	499
100i	62	birdseye	11	4	3	213	585
62	83	birdseye	11	4	4	213	259

The only advantage of Diagonal is that it is 1 frame faster to choose at the SELECT DISPLAY menu—which might be enough to save an RNG cycle and therefore 60 frames. Of course, 16 frames of that gets immediately erased on entering the first floor in a segment, and the segment cannot be too long, or else the rest of the gain will be eaten up by longer floor transitions. (And of course, the segment cannot involve many instances of pushing a block into a hole.) It's unlikely, but possible, that using Diagonal display in some of the shortest segments could save time. In between segments, you have to go through the menus to change the settings for the next segment. The settings you may have to change are the skill level (Easy, Average, or Hard), number of floors, and view (Diagonal or Bird's-eye). How much time you spend in the menus depends on how many settings you have to change. In the special case where the skill level, number of floors, and view are the same in two consecutive segments, you don't have to enter the menus at all, you only have to wait for the right RNG seed. But there are two ways to navigate the menu. You can back up screen by screen using the B Button, or you can directly choose a screen to go to using the END menu. In either case, you then can only advance linearly through the rest of the screens. This is what the possible menu transitions look like graphically:

The difference in time between the END menu and the B Button depends on how far back you have to go in the menu sequence:

If you need to change the skill level (SELECT SKILL menu),	the END menu is 1 or 61 frames faster than the B Button
If you need to change the number of floors (SELECT COURSE menu),	the END menu is 0 or 60 frames faster than the B Button
If you need to change the view (SELECT DISPLAY menu),	the END menu is 2 or 62 frames slower than the B Button

I was surprised at seeing the numbers 1, 2, 61, and 62. It seems like every difference should always be a multiple of 60, because of the RNG seed cycle. Either the difference between the END menu and the B Button is small enough to hit the same cycle, or else one is one cycle slower. That is true, but as it turns out, the RNG seed variable is not an exact frame counter. It can fail to count vblanks in some situations, and moving between menus is one of them. This is why the END menu is usually faster than the B Button, because there are fewer total menu transitions. Only in the special case of having to visit only the final menu (SELECT DISPLAY) can it be faster to use the B Button. The next step is to load the segment transition costs into a traveling salesman solver to optimize the order of segments, in each case using whichever of the B Button or END menu gives the fastest transition between consecutive segments, and keeping the option of doing each segment in either Diagonal or Bird's-eye view.

Posted: 5/14/2024 5:13 AM

Post subject: Optimized segment order – and a plot twist

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

I found approximately optimal orderings of the 14 segments. But I had overlooked something initially in the way random floor schedules are generated. The schedules are not independent, but are affected by schedules that have already been executed. In light of this new knowledge, optimizing the route through RNG seeds is going to require different techniques. I put the segment transition costs from Post #529194 into traveling salesman solvers, with the simplifying assumption of using Bird's-eye view only. This would forego potential minor time savings of using Diagonal view for some segments. I tried the LK solver and GenericGraph.traveling_salesman_problem from Sage. (I also tried algorithms.approximation.traveling_salesman.traveling_salesman_problem from NetworkX, but even with a reduced graph of 7 segments, it was still running after 2 hours, while the other two solvers took only a few seconds. There must be a bug, because 7! is only 5,040, small enough to solve quickly even by brute force.) LK and Sage gave me different routes with equal cost:

Frames	Skill	Seed	# Floors	Floors
17379	Easy	42	30	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
42681	Hard	34	28	120, 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
46056	Hard	26	3	137i, 140i, 130i
49567	Hard	58	4	128i, 132, 122i, 126
54155	Hard	21	4	125, 134, 114i, 145i
57988	Average	12	5	105i, 94, 104, 77i, 99i
60217	Average	36	2	60, 101i
64304	Average	54	6	82, 91, 97, 78, 96, 95i
67084	Average	52	4	74i, 89, 93i, 68i
70738	Average	11	4	109i, 100i, 62, 83
73845	Average	45	4	90, 103, 87, 76i
75257	Average	32	1	102
91869	Average	17	25	67i, 78, 84i, 69, 75, 61, 79, 88, 72, 85, 81, 70i, 66, 92, 86, 98, 73i, 71i, 108i, 106, 65, 63i, 107i, 64i, 80i
93520	Hard	35	2	124i, 117

Frames	Skill	Seed	# Floors	Floors
17379	Easy	42	30	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
42681	Hard	34	28	120, 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
46076	Hard	26	3	137i, 140i, 130i
62664	Average	17	25	67i, 78, 84i, 69, 75, 61, 79, 88, 72, 85, 81, 70i, 66, 92, 86, 98, 73i, 71i, 108i, 106, 65, 63i, 107i, 64i, 80i
66497	Average	12	5	105i, 94, 104, 77i, 99i
68726	Average	36	2	60, 101i
72813	Average	54	6	82, 91, 97, 78, 96, 95i
75593	Average	52	4	74i, 89, 93i, 68i
79247	Average	11	4	109i, 100i, 62, 83
82354	Average	45	4	90, 103, 87, 76i
83771	Average	32	1	102
88276	Hard	21	4	125, 134, 114i, 145i
91869	Hard	58	4	128i, 132, 122i, 126
93520	Hard	35	2	124i, 117

But when I entered one of the schedules into the Lua script to have it executed, it desynced after the first segment. There was an error in my understanding of how the random floor schedule generation algorithm works. I understood that the algorithm does not allow repeating a floor if that same floor was already played within the most recent 20 floors of a schedule. What I did not understand is that this 20-floor history carries over across schedules, too. The first floor in a schedule cannot be the same as any of the most recent 20 floors played in previous runs, then the window shifts by 1 for the second floor, and so on. (The equality that matters for this purpose is the relative floor number; that is, the floor's index number minus the index of the first floor in the skill level. So floor 35 (index 5 in Easy) will block not only 35, but also 65 (index 5 in Average) and 115 (index 5 in Hard). This is the code that I initially misinterpreted:

generate_random_floor_schedule:
        31e7    1111c3  ld      de, heading_out_floor_schedule
                        ; Seed the RNG.
        31ea    fa77c3  ld      a, [frame_counter_copy]
        31ed    ea28cf  ld      [rng_state_a], a
        31f0    ea29cf  ld      [rng_state_b], a
        31f3    ea2acf  ld      [rng_state_c], a
        31f6    ea2bcf  ld      [rng_state_d], a
        31f9    0e63    ld      c, 99           ; Always generate a full schedule of 99 rooms.
next_random:
        31fb    cd5432  call    rng_next        ; Get a random 8-bit integer.
        31fe    6f      ld      l, a
        31ff    2600    ld      h, 0
        3201    cdc93e  call    heading_out_num_floors_for_skill_level
        3204    78      ld      a, b
        3205    cd2b1f  call    remainder_16b   ; Reduce the random number mod the number of floors in the skill level.
        3208    c61e    add     30              ; Add 30 to skip over Going Up? floors.
        320a    cd3c32  call    check_for_recent_duplicate_floors
        320d    feab    cp      0xab            ; 0xab is a sentinel that means a duplicate was found.
        320f    28ea    jr      Z, next_random
        3211    12      ld      [de], a         ; Assign next slot in heading_out_num_floors.
        3212    13      inc     de
        3213    0d      dec     c               ; Are we done with all 99 floors yet?
        3214    20e5    jr      nZ, next_random
        3216    fab9c2  ld      a, [heading_out_num_floors]
        3219    47      ld      b, a
        321a    fab8c2  ld      a, [game_mode]
        321d    fe01    cp      0x01
        321f    2808    jr      Z, copy_last_20_into_history
        3221    fabac2  ld      a, [heading_out_num_floors_remaining]
        3224    4f      ld      c, a
        3225    90      sub     b
        3226    3801    jr      C, copy_last_20_into_history
        3228    41      ld      b, c
copy_last_20_into_history:
        3229    78      ld      a, b
        322a    21fdc2  ld      hl, heading_out_floor_schedule - 20
        322d    cd6b24  call    add_16b         ; Add the selected number of floors to hl.
        3230    0614    ld      b, 20
        3232    11fdc2  ld      de, heading_out_floor_schedule - 20
                        ; Copy 20 bytes from heading_out_floor_schedule - 20 + num_floors
                        ; into the history buffer at heading_out_floor_schedule - 20.
copy_loop:
        3235    2a      ldi     a, [hl]
        3236    12      ld      [de], a
        3237    13      inc     de
        3238    05      dec     b
        3239    20fa    jr      nZ, copy_loop
        323b    c9      ret

check_for_recent_duplicate_floors:
        323c    d5      push    de
        323d    c5      push    bc
        323e    0614    ld      b, 20
        3240    4f      ld      c, a
        3241    1b      dec     de
check_loop:
        3242    1a      ld      a, [de]
        3243    b9      cp      c
        3244    2806    jr      Z, dup_found    ; Duplicate found, bail out.
        3246    1b      dec     de
        3247    05      dec     b               ; Done with all 20 yet?
        3248    20f8    jr      nZ, check_loop
        324a    1804    jr      no_dups         ; Finished all 20, no duplicates.
dup_found:
        324c    3eab    ld      a, 0xab         ; 0xab is a sentinel indicating a duplicate.
        324e    1801    jr      done
no_dups:
        3250    79      ld      a, c            ; Restore the caller's a register.
done:
        3251    c1      pop     bc
        3252    d1      pop     de
        3253    c9      ret

The important part is the copy_last_20_into_history label at the end of generate_random_floor_schedule. There is an array of 99 bytes at 0xc311 that I call heading_out_floor_schedule, which holds the randomly generated floor schedule. There is also a buffer that starts 20 bytes before heading_out_floor_schedule, which I'll call the "history" buffer. Initially, the history buffer is filled with 0xee, which is unequal to any floor number. I thought the purpose of this buffer was just to simplify the code of check_for_recent_duplicate_floors, allowing it to unconditionally look 20 bytes back, even when that goes before the beginning of heading_out_floor_schedule. But the loop at copy_last_20_into_history copies the 20 floors at the end of the schedule into the history buffer. (It's the 20 floors at the end of the schedule only up to the player's chosen number of floors, which may be less than 99.) So on the second and subsequent runs, the history buffer is no longer filled with 0xee, but contains floor numbers from the previous schedule, which affects the subsequent generation of floors, because of the no-repeat rule. It is not the case that there are only 60 possible schedules in each skill level, one for each seed, as was claimed in Post #527972. That's true for the first run, but after that each of the 60 seeds in each skill level will yield a slightly different random sequence of floors than it would have the first time. This is both good and bad. It will likely be possible to visit all unique floors in fewer than the 13 restarts that I had previously computed, because there are more opportunities to affect the RNG sequence. But the search space is greatly increased – we're no longer looking at just 180 basically static schedules – so it may not be possible to find a route that is definitely minimal.

Posted: 6/2/2024 6:34 AM

Post subject: A complete route for Heading Out?, all floors

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

I've been working on the all-floors route since correcting my understanding of how RNG is affected by previously completed floors. As I suspected, it is a harder overall than the set cover / traveling salesman I had envisioned before. But while the larger search space makes solutions harder to find, solutions also have the potential to be faster, with fewer segments and fewer repeated floors. I found a working route for "Heading Out? all unique floors" that hits all 120 floors in 10 segments with no repeats. It's 90741 frames in length. You can find it in User movie #638529018325843149, and I'll say more about it below. I'm planning to try running a few more variations through the route optimizer to see if I can find a faster route. The route optimizer I wrote is the usual uniform cost search kind of thing. It treats the game states (skill, floor schedule, number of unique floors completed) as vertices in a graph. Being at a certain vertex means you have just completed a floor, and you now have the option of playing the next floor in the schedule, or starting a new segment with a new skill and RNG seed. We're trying to find a shortest path from the origin vertex to a vertex that has all floors completed. To make the problem more tractable, I've imposed some simplifying restrictions:

Optimize only one skill level at a time (Easy, Average, or Hard). This means when we follow a "restart" edge, we only have to consider up to 60 seeds in the current skill, not up to 180 seeds across all skills. This restriction could cause the optimizer to ignore some possibilities; for example, suppose there is a route where you play a few segments in Hard, which lines up the RNG just right to solve Average, which then lines up the RNG to finish the rest of Hard.
Don't follow edges ("next floor" or "restart") that would have us repeat a floor that has already been done. This one is actually not much of a restriction, because we expect an optimum route not to have any repeats anyway.
Only consider "restart" edges when "next floor" is impossible because it would cause a repeat. This means that every segment is as long as possible without a repeat. The optimizer will ignore opportunities to restart a segment earlier. Since every "restart" choice means adding up to 60 new vertices to the candidate list (which in turn can add 60 of its own, and so on), this restriction is important for keeping the size of the candidate vertex set manageable.

The Easy and Hard skill levels are not too hard to deal with. Easy has only 30 floors, and we already know that seed 42 works from boot to cover all 30 perfectly. The optimizer finds that single-segment route for Easy instantly. Hard has 40 floors, which makes the optimizer work more, but is still not too bad. Hard can be done after Easy in just 3 segments. The difficult part is Average skill, with its 50 floors. The most progress I have been able to make in Average, so far, is 48 floors. That's with giving it several hours of computation and about 150 GB of space to work with. I tried optimizing the skill levels in the order Easy, Hard, Average. It got to 118 floors before running out of space. The unfinished floors were 76 and 105. I tried restarting the optimizer with just those two floors, and it found a way to cover them with one additional segment each. This is probably suboptimal (even with the restrictions listed above) because it's not a global optimization: we optimized the problem in two parts and glued them together. But it is at least a functional route that can serve as a basis of comparison. Here is the route. The movie file for it is User movie #638529018325843149. The tas.lua script that executes the route is available at commit 32c435cca14ae486f42be4b261a3fa5a061e0c82 in my repo.

Skill	Seed	# Floors	Floors
Easy	42	30	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
Hard	34	23	138i, 110i, 139, 113i, 146, 148i, 111i, 144i, 143, 140, 131, 142i, 136i, 149i, 112i, 147, 121, 129i, 127i, 141, 135i, 115i, 118
Hard	22	10	128, 123i, 145i, 117i, 114, 125i, 119, 120, 133, 137
Hard	58	7	132, 122, 126i, 124i, 134i, 130, 116
Average	2	29	89i, 98, 90, 108, 71i, 94, 102, 86i, 106, 92i, 103i, 60, 104, 63, 91i, 97i, 64i, 62, 68, 88i, 93, 65i, 74i, 107, 73, 109, 72, 84, 78
Average	17	9	67, 69, 75i, 61, 79, 85, 81, 70i, 66i
Average	26	5	87, 80i, 77, 82i, 95i
Average	13	5	83, 100i, 101i, 99i, 96
Average	10	1	105i
Average	5	1	76

I'm planning to try a few more experiments with route optimization, but not take it too far. Finding routes with fewer restarts, or more favorable floor inversions, can be left as an opportunity for future improvements.

Posted: 7/10/2024 7:27 AM
(Edited: 8/30/2024 3:53 PM)

Post subject: A route in 90570 frames

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

It was surprisingly difficult to find a route faster than the 90741-frame one I posted as a point of comparison in Post #529667. Long story short, the best route I've found is 90570 frames long, about 2.8 seconds faster. Link to video BizHawk file This route has 8 segments, compared to Post #529667's 10 segments. It has one repeated floor, floor 90 in Average skill, but repeating the floor is faster than restarting with additional segments.

Skill	Seed	# Floors	Floors
Easy	42	30	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
Hard	34	22	138i, 110i, 139, 113i, 146, 148i, 111i, 144i, 143, 140, 131, 142i, 136i, 149i, 112i, 147, 121, 129i, 127i, 141, 135i, 115i
Hard	22	10	128i, 123i, 145i, 117, 114i, 125, 119, 120, 133, 137
Hard	58	8	132, 122i, 126, 124i, 134i, 130, 118, 116
Average	37	12	109i, 100, 106, 104i, 98i, 65i, 63i, 93, 90, 73i, 95i, 96
Average	2	15	89i, 108, 71, 94, 87i, 102, 86, 92i, 80, 103i, 60i, 91, 97, 64, 62i
Average	4	15	68, 82i, 83i, 74i, 99, 70i, 76, 84i, 101, 77, 67, 90, 69, 107, 105i
Average	17	9	78, 75, 61i, 79, 88, 72, 85, 81i, 66i

I started using an abbreviated notation to describe routes. The above route is E42x30-H34x22-H22x10-H58x8-A37x12-A02x15-A04x15-A17x9. Here are other routes I discovered and tested over the past month:

Route	Segments	Repeats	Frames	Comment
`E42x30-H34x23-H22x10-H58x7-A26x2-A21x16-A45x17-A04x8-A17x9`	9	2	91644
`E42x30-H34x22-H22x10-H58x8-A21x3-A21x12-A45x16-A03x3-A04x8-A17x9`	10	1	91528
`E42x30-H34x22-H22x10-H58x8-A21x5-A37x13-A45x7-A04x14-A17x10-A53x1`	10	0	90930
`E42x30-H34x23-H22x10-H58x7-A21x6-A37x11-A45x13-A04x12-A48x2-A17x6`	10	0	90904
`E42x30-H34x23-H22x10-H58x7-A21x6-A37x12-A45x13-A04x11-A53x1-A17x7`	10	0	90902
`E42x30-H34x23-H22x10-H58x7-A26x2-A21x22-A17x10-A19x5-A04x8-A45x3`	10	0	90896
`E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A10x1-A14x3-A13x3`	10	0	90873	Best with UCS
`E42x30-H44x8-H41x15-H22x5-H07x4-H58x8-A45x3-A25x1-A23x2-A48x44`	10	0	90786
`E42x30-H44x8-H41x17-H22x4-H07x4-H58x7-A22x1-A45x3-A25x4-A48x42`	10	0	90743
`E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A13x5-A10x1-A05x1`	10	0	90741	Post #529667
`E42x30-H34x22-H22x10-H58x8-A37x12-A02x14-A04x16-A17x9`	8	1	90578
`E42x30-H34x22-H22x10-H58x8-A37x12-A02x13-A04x17-A17x9`	8	1	90577
`E42x30-H34x22-H22x10-H58x8-A37x12-A02x15-A04x15-A17x9`	8	1	90570	This post

I let the uniform cost search optimizer from Post #529667 keep running for a week or so. It did eventually find an exact solution, E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A10x1-A14x3-A13x3. The optimizer doesn't take into account the fact that the time to restart a new segment is variable (mainly because of the time to wait for the next RNG seed), because that it too hard to simulate. So the idea was to get some fast route candidates, then get precise frame counts for them by executing the routes in the emulator. (Because the TAS is automated using a Lua script, testing candidate routes doesn't require manual TASing.) The optimizer estimates that E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A10x1-A14x3-A13x3 is 18 frames faster than the E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A13x5-A10x1-A05x1 of Post #529667, but when actually played out, it's actually 183 frames slower. If allowed to continue, the optimizer would eventually have gotten to E42x30-H34x23-H22x10-H58x7-A02x29-A17x9-A26x5-A13x5-A10x1-A05x1 and competitive routes, but here I decided to try something different, a genetic algorithm. The genetic algorithm has the advantage that is is not bound by the simplifying restrictions introduced to make the problem more tractable. In particular, it's allowed to repeat floors, and start a new segment even when the current segment is not just about to hit a repeat. The tradeoff, of course, is that there's no guarantee of optimality. The first breakthrough was when the genetic algorithm found the solution H34x22-H22x10-H58x8 for the Hard floors. This is very similar to how Hard was solved in Post #529667, H34x23-H22x10-H58x7, just moving one floor from the seed 58 segment to the seed 34 segment, but its slightly different history buffer of recently played levels clears the way for a faster clear of Average. I ran the genetic optimizer several thousand times and tested the best routes it found. Ultimately the best one is the one you see in the video above. The tas.lua script to execute it is in commit 78a676ebcde7f6885d99b751ac27d3f1683df17f in my repo.

Posted: 9/1/2024 4:57 AM
(Edited: 9/1/2024 5:02 AM)

Post subject: Video using cheat code

Quote

Sand

He/Him

Player (143)

Joined: 6/26/2018
Posts: 174

Sand wrote:

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.

Out of curiosity, and because I wanted to make a speedrunning guide, I hacked the tas.lua script to use the cheat code and play all the floors in order, in 3 segments. The total time is 87537 frames and 24:25.128. That's 3033 frames and 50.071 seconds faster than the 90570 frames and 25:15.195 of Post #530388, with its 10 segments. That tracks with the estimate of each restart costing about 8 seconds. Using the cheat code, it might be possible to get a slightly lower time by playing the difficulty levels in a different order. The floors would be the same, but they would be inverted differently.

Skill	Seed	# Floors	Floors
Easy	N/A	30	30, 31i, 32, 33, 34, 35, 36i, 37i, 38i, 39, 40, 41, 42i, 43, 44, 45, 46, 47, 48, 49, 50, 51i, 52, 53i, 54, 55, 56, 57i, 58, 59i
Average	N/A	50	60i, 61i, 62, 63, 64i, 65, 66, 67i, 68, 69i, 70i, 71, 72, 73, 74i, 75i, 76i, 77, 78, 79i, 80i, 81, 82, 83, 84, 85, 86, 87i, 88, 89i, 90i, 91, 92i, 93i, 94i, 95, 96, 97, 98i, 99, 100, 101, 102, 103, 104, 105, 106, 107i, 108, 109i
Hard	N/A	40	110i, 111, 112, 113, 114, 115, 116i, 117i, 118, 119, 120i, 121, 122, 123i, 124, 125i, 126i, 127, 128, 129i, 130i, 131, 132, 133, 134i, 135, 136i, 137, 138, 139, 140, 141, 142, 143i, 144, 145i, 146i, 147, 148, 149

Link to video

Forum Game Boy Games Kwirk! Game: Kwirk

Forum

Game Boy Games

Kwirk! Game: Kwirk