Submission Text Full Submission Page
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.

Game objectives

  • Emulator used: BizHawk 1.11.1
  • Completes all 265 puzzles
  • Collects all 125 stars
  • Aims for fastest time
  • Does not abuse programming errors

Comments

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.

Timing

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.

Finding Solutions

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.

Other comments

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.

TASVideoAgent
They/Them
Experienced Forum User, Moderator
Joined: 8/3/2004
Posts: 12516
Location: 127.0.0.1
This topic is for the purpose of discussing #4910: qqwref, AdituV's GBA Denki Blocks! "100%" in 1:24:07.67
Editor, Experienced Forum User, Publisher, Skilled player (1324)
Joined: 10/12/2011
Posts: 6057
Location: The land down under.
PSX TASer of 2016
Temp Encode: Link to video Gonna publish this one when/if it gets accepted.
WebNations/Sabih wrote:
+fsvgm777 never censoring anything.
Disables Comments and Ratings for the YouTube account. These colours are pretty neato, and also these.
hellagels
He/Him
Experienced Forum User, Experienced player (666)
Joined: 2/1/2011
Posts: 79
Location: Guangdong, China
GBA TAS of 2017GBA TASer of 2015
Yes vote. In many level it takes much lower moves than I think. How you complete 3 of 1 Kind looks very beautiful.
Current projects: Castlevania - Order of Ecclesia (NDS)
Experienced Forum User
Joined: 12/10/2006
Posts: 118
really nice work with that sovler. also really good execution with using resets for example.
Twisted Eye
He/Him
Experienced Forum User, Player (249)
Joined: 10/17/2005
Posts: 611
Location: Seattle, WA
Lots of really nice solutions here. Once I caught on just how long the "Nice pair!" and such cutscenes were, I suddenly appreciated the extra effort to match all of the colors on the same move whenever possible. Incredible amount of forethought went into this one, and it shows in the end.
Experienced Forum User, Player (126)
Joined: 9/18/2007
Posts: 389
Is this game purely deterministic, even the Joker tiles? In that case, it should be possible to use a SAT solver to find the optimal solutions, like I did it for Polarium. That would be a difficult but doable task, as it requires you to describe the game and the solution as a set of non-changeable boolean variables (whenever a variable would possibly change its value in the usual context, you need to invent a new variable at that moment). The good thing is that you wouldn't have to worry that much about optimizations and memory usage, as these are all done by the highly optimized SAT solver in that case. I haven't seen your solver. Most of the solutions look very good, and I'm sure you put a lot of effort into making these movies. Definitely good enough for Vault, maybe good enough for Moons.
Experienced Forum User
Joined: 3/9/2009
Posts: 530
Maybe I'm missing something. At ~33:05 in, you have this situation. Can't you solve that with L-U-L? The solution used is U-U-L-L-U. Edit: Ah, this is one of those "not optimal solutions due to cut scene" things, isn't it? It really... irks me.
Experienced Forum User, Player (108)
Joined: 8/27/2004
Posts: 162
partyboy1a wrote:
Is this game purely deterministic, even the Joker tiles? In that case, it should be possible to use a SAT solver to find the optimal solutions, like I did it for Polarium. That would be a difficult but doable task, as it requires you to describe the game and the solution as a set of non-changeable boolean variables (whenever a variable would possibly change its value in the usual context, you need to invent a new variable at that moment). The good thing is that you wouldn't have to worry that much about optimizations and memory usage, as these are all done by the highly optimized SAT solver in that case. I haven't seen your solver. Most of the solutions look very good, and I'm sure you put a lot of effort into making these movies. Definitely good enough for Vault, maybe good enough for Moons.
Yeah, the game's deterministic; it even has a rule that if a tile is going to change to two different colors at once, it doesn't change at all. The idea of SAT solving is very interesting, and I'd love to hear more. I'm not sure how this kind of game could be turned into boolean variables, though; you'd have to turn both the moves and the whole piece joining rule somehow. Would it involve something like describing every possible shape/location and then writing out how every move can affect those? And thanks to you and everyone else for the interest in this run! :)
Tangent wrote:
Maybe I'm missing something. [snip] Edit: Ah, this is one of those "not optimal solutions due to cut scene" things, isn't it? It really... irks me.
Yeah, that gives a 43-move solution (tying the best one I know of), but it is 58 frames slower because of the pairing cutscenes. I could also make a movie with the fewest-moves solutions I know about, if people are interested. I assumed that this game would end up in the Vault, so only going for fastest real time made sense.
Experienced Forum User, Player (126)
Joined: 9/18/2007
Posts: 389
qqwref wrote:
The idea of SAT solving is very interesting, and I'd love to hear more.
I don't want to go off-topic here too much, so here are a few links: To know what the boolean satisfiability problem is all about, read this part from Wikipedia: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem My solver uses the conjunctive normal form, which is described here. I posted the solver in the following thread: Thread #8509 I also created a framework, which allows you to use a more natural language, in Lua, which can be found in this thread. You may probably need to know a way to encode an at-most-k-constraint, which is described either here, or you may have a look at my source code, where i use a way to encode at-most-k to count the "touched" tiles. And the biggest problem of all: You need to model every single (even totally obvious) rule in the language of a boolean satisfiability problem, and the model must be optimized in a "nice" way. "nice" is what makes the solver fast, and is very hard to predict....
Post subject: Movie published
TASVideoAgent
They/Them
Experienced Forum User, Moderator
Joined: 8/3/2004
Posts: 12516
Location: 127.0.0.1
This movie has been published. The posts before this message apply to the submission, and posts after this message apply to the published movie. ---- [3008] GBA Denki Blocks! "100%" by qqwref, AdituV in 1:24:07.67
Active player, Experienced Forum User (339)
Joined: 10/4/2015
Posts: 86
I didn't see the script linked in the description, but to me it sounds like this used a breadth first search strategy. While RAM has certainly gotten cheaper over the years, my bet is you could also use a more efficient algorithm. 3-SAT, sounds honestly more complicated than necessary. I'd suggest something like A-star rather than BFS.