Submission #4909: qqwref, AdituV's GBA Denki Blocks! in 29:47.18

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 the minimum of 15 puzzles from each of the 8 players.

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, which can be done in any order. To beat each stage you need to finish any 15 puzzles. This run completes the shortest 15 puzzles in each group in an optimal order.

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.

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.

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.

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.

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. Very impressive how you guys put together a lua/search program to tightly optimize the puzzle solutions! This game is definitely strategically deeper than it looks. Overall, this run was certainly an enjoyable watch. Nice work!

Accepting for publication to the Vault!

fsvgm777: Processing.