Tool-assisted game movies
When human skills are just not enough

Submission #4066: partyboy1a's DS Polarium "puzzle mode" in 06:57.68

Console: Nintendo DS
Game name: Polarium
Game version: USA
ROM filename: 0006 Polarium (US).nds
Branch: puzzle mode
Emulator: DeSmuME 0.9.9
Movie length: 06:57.68
FrameCount: 24988
Re-record count: 305
Author's real name:
Author's nickname: partyboy1a
Submitter: partyboy1a
Submitted at: 2013-08-29 22:26:05
Text last edited at: 2013-09-05 10:25:01
Text last edited by: Spikestuff
Download: Download (10786 bytes)
Status: published
Click to view the actual publication
Submission instructions
Discuss this submission (also rating / voting)
List all submissions by this submitter
List pages on this site that refer to this submission
View submission text history
Back to the submission list
Author's comments and explanations:
DS Polarium finished very fast. It's a pity it's just vault material.

About the game: You do see a field with black and white tiles, surrounded by gray tiles. Your task is to draw a path (the yellow thing). If your path hits a black or white tile, this tile is flipped. If this causes all tiles in the row to become black, or all tiles become white, then this row is deleted. The gray tiles always stay gray, they don't matter for that. Sometimes, it's necessary to use those gray tiles too. Your task is to draw a path so that all lines get deleted at once.

There were two difficult problems to solve: How the input for the puzzles can be done in the fastest way, and which solution takes the lowest amount of frames.

At first we thought: You need to touch every tile where a turn appears for 3 frames, and afterwards one frame pause. I've got a Lua script working which just tried every single possible path. It was too slow, so it got tweaked more and more. ais523 made another solver with a different model, and it worked a lot faster. Some puzzles with a lot of possible paths could still not be computed in a reasonable amount of time, for example stage 21. As I heard about solvers for SAT problems, I converted the "problem" into a set of thousands of boolean variables, and let a SAT solver (minisat) solve the problem. But: A SAT solver only tries to find ONE solution, it doesn't search for the best one. Therefore, the solver has to run multiple times, each time with another "score" limit.

Then there was a "glitch", at least we thought that: Sometimes, the frame with no input could be left out. As I played around a bit, I found out that you can move a lot faster: Up to two tiles per frame. Luckily it was not that hard to adjust the solver for that. A bit later, I found out that the movement can be done with 40 pixels per frame, which equals 2.5 tiles per frame in a straight line. It was somewhat tricky to think about a method which allows the 3-2-3-2-... input, but it worked out to be quite easy. Finally, this piece of software was used to find the solutions. More precisely: It creates a description of the "problem" in the so-called conjunctive normal form, and then minisat generates one solution if there is any, and then the solution (which is just a set of thousands of boolean variables) is converted back to a human-readable format.

I recommend you to read through all pages of the Polarium thread to see how the solvers evolved.

Aims for fastest real time to the credits screen.

Does not aim on shortest input: The last few frames of the movie can be cut out, and you would still see the credits. However, it would look realĺy inconsistent to cut them out. If you want to beat this movie just aiming at shortest input, make sure to be faster than this movie which doesn't double-draw the path for stage 100

The rerecord count only covers the rerecords done before the first puzzle. The rest was botted, more precisely: this script was used to generate the final movie. The solver itself is massively complex.


feos: Accepting for Vault. Movie length to game completion ratio is up to the author.

partyboy1a: As both versions are good, I'd go with the submitted version.

Spikestuff: On it...

Similar submissions (by title and categories where applicable):