Submission #4910: qqwref, AdituV's GBA Denki Blocks! "100%" in 1:24:07.67

On Puzzle Island, the greatest accolade is the title of Puzzle Master. To earn it, you have to defeat the best seven Denki Blocks! players on the island, and then solve the current Puzzle Master's puzzles. This movie finishes every puzzle in Tournament mode, earns every bonus star, and then uses the stars to unlock and finish all 30 Club puzzles.

Denki Blocks! is a puzzle game released for the Game Boy Color, Game Boy Advance, and several other platforms. The main Tournament mode has 8 stages, each of which have 25 puzzles. The puzzles in each stage can be done in any order, and there are many possible optimal orders, so for entertainment we chose orders that are related to the puzzles in each stage.

This run completes all 265 puzzles in the game, as well as collects all 125 bonus stars. That means (a) completing the 25 puzzles in each stage, (b) finishing the 5 extra puzzles in the first 7 stages, (c) doing every possible 3 of a Kind and Bonus Shape bonus in the Tournament stage, and (d) beating the 30 Club levels unlocked using the bonus stars. This also unlocks every trophy in the Trophy Room; while it is possible to do that while finishing only 255 of 265 puzzles and getting only 100 of 125 stars, we felt that this 100% definition was more satisfying.

Each puzzle has a bunch of colored blocks of various shapes and sizes, as well as some walls. A move brings all of the blocks in the same direction by one space, except for the ones that are blocked from moving (by walls, or by the edge of the playing field). Whenever two blocks of the same color touch, they stick together, making a bigger block that is then harder to move around. Puzzles specify one or more colors, and when you stick together all the blocks of those colors, you finish the puzzle.

The bonus stars and Club puzzles add some extra complexity to the puzzles. For a 3 of a Kind bonus, each of the three colors must end up paired in the same shape and the same orientation. For a Bonus Shape bonus, a selected color must end up paired in a certain shape. The Club puzzles also add several extra game mechanics, such as the Switch (which must be covered to beat the level) or the Key (which must be pushed to the Lock to beat the level).

In July 2014, I (qqwref) started working on a C++ program to optimally solve the puzzles. That turned out to be too difficult, so the program became a suboptimal solver, which could finish most of the puzzles efficiently. Eventually, I had good solutions for almost all of the puzzles and was thinking about putting them together into a TAS. Then AdituV joined on, writing a Lua script to save time. Together, we timed things, optimized solutions for real time instead of moves, organized them, and made the input file.

Every move takes 7 frames, except for the first move which takes 10.

Finishing pairing one of the required colors starts a 79-frame cutscene. If there are multiple colors, pairing two or three of them in the same move starts those cutscenes at the same time, which is faster. At the end of a puzzle, the game will play a 180-frame "Nice Pair" cutscene if two shapes are identical, a 421-frame "3 of a Kind" cutscene if three shapes are identical, or a 360-frame "Bonus Shape" cutscene if a shape matches the goal shape (in applicable levels). This is why many levels use solutions that are not the shortest known solution: the extra moves cost less time than the avoided cutscenes.

Some Club puzzles contain pieces that change the color of other pieces. The Painters (blocks with a dot in the center) cost 10 frames for every move where at least one block changes color. The Jokers (color-changing blocks), on the other hand, cost 10 frames per wave of color change. In levels with these elements, that extra time also had to be taken into account.

Outside of puzzles, the conversation cutscenes can be skipped by hard resetting the console at the proper time. This is almost always worth it, even though it means having to navigate through the game menus again.

Instead of running through an emulator, my program saves a lot of time by simulating the puzzles internally. When looking for a solution, we check positions 1 move deep, 2 moves, and so on, storing the sets of positions so we can ignore any positions we have already seen. A minimum-distance function gives a lower bound for the number of moves it could take to solve, so if we are trying to beat a given move count, we can discard any positions that the function says can't be solved in fewer moves than the goal.

When looking for an optimal solution, we simply keep track of every position, which means we either find a solution or run out of memory. Even with optimizations, though, many levels are very far from being optimally solvable. To look for a suboptimal solution, we keep track of the best 100000 or so solutions for each number of moves, with "best" being determined by a slight variant of the minimum-distance function. Even that wasn't enough for some of the hardest levels, though, so we created an initial move sequence by hand or computer and then let the program continue from there.

Searching for 3 of a Kind and Bonus Shape solutions was trickier, especially nearing the end of Tournament mode. For Bonus Shapes, where a color has to pair up into a given shape, we checked every position to make sure all current shapes could fit inside the goal shape, and discarded any with an unacceptable shape. For 3 of a Kind, when we saw a potential solution, we discarded the position if the shapes were not identical. In some harder 3 of a Kind puzzles, we also used the shape technique: define a goal shape, and make sure every shape of any color can fit inside it. The choice of goal shape for 3 of a Kind can matter a lot, so when we used this technique we tried a few different ones per puzzle.

When optimizing for time instead of move count, the biggest concern was to pair up as many colors as possible. This was done by checking the number of solved colors at each position; if we want to pair up every color at once, for instance, we can discard any position that has one color paired and another color un-paired. This technique made it possible to find a lot of clever solutions that saved cutscenes at the cost of only a few extra moves.

For many Club puzzles it was necessary to keep track of the exact number of frames used during the solution, as well as the move count. Instead of a goal movecount, there was a goal frame count, and any positions that used more frames than the goal were discarded.

In total, I would estimate several billion moves have been simulated with the search program.

The rerecord count is inaccurate - the real number is probably a few thousand.

There are no currently known improvements, and the solutions shown here beat or tie the time of all published solutions. With more time and RAM, the solver could search further and try more possibilities, but a lot of time has been spent already, and the search space is too large to find optimal solutions for everything.

ars4326: Judging!

ars4326: Hello qqwref & AdituV. Like your any% submission, very impressive how you guys put together tightly optimized solutions with a lua/search program (several billion simulated moves!). As for this 100% category, the solutions were even more interesting to see unfold, with the additional conditions of bonus shapes and '3 of a kind' thrown in (especially toward the end of the game). Outstanding work on these categories, overall :)

Accepting for publication to Vault!

Spikestuff: Publishing.