TASVideos

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

Submission #6806: Jigwally's SGB Mario's Picross in 59:35.26

Console: Super Game Boy
Game name: Mario's Picross
Game version: USA/Europe
ROM filename: Mario's Picross (USA, Europe) (SGB Enhanced).gb
Branch:
Emulator: BizHawk 2.4.2
Movie length: 59:35.26
FrameCount: 214869
Re-record count: 13963
Author's real name: Basil Gruber
Author's nickname: Jigwally
Submitter: Jigwally
Submitted at: 2020-07-14 01:40:52
Text last edited at: 2020-07-25 20:14:18
Text last edited by: Jigwally
Download: Download (90127 bytes)
Status: decision: cancelled
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:
The process of making this TAS was probably more interesting than the movie itself. I've been interested in using optimization algorithms for the purpose of helping to route TASes. This is probably the most mundane example possible of that but it's got me thinking about using a similar approach for more complex gameplay.

You can move up/down/left/right or diagonally every other frame & the optimal solution is the one that visits the fewest unnecessary tiles (tiles you've already chiseled or tiles that aren't part of the solution). If all of the tiles in the puzzle are connected in a way that you can solve the puzzle just by visiting each of them once & no other tiles that is clearly an optimal solution (aka a Hamiltonian path).

To verify that all solutions are optimal I converted all the puzzles to a distance matrix which allows the puzzles to be treated as instances of the Traveling Salesman Problem. The Concorde solver ( http://www.math.uwaterloo.ca/tsp/concorde.html ) is a highly efficient TSP solver that quickly verified the fewest number of steps for all puzzles. I also wrote some extra code to convert solutions directly to controller input so they could simply be pasted into TAStudio to speed up the process.

Some notes:

Possible improvements:

Edit: Will resubmit fixed version


feos: Judging...

Similar submissions (by title and categories where applicable):