frieze
@frieze

I made this short TAS a while back to tease something I've been kind of working on

After pages of notes I think I have finally convinced myself that finding an optimal TAS for solving Mario's Super Picross puzzles (not finding the solution but rather finding the inputs to carve out that solution on the screen) is NP-hard by a series of reductions to the classic Traveling Salesman Problem.

I don't want to spoil too much of it because I want to make a video about it, but essentially I can translate a Picross puzzle's solution into a graph that corresponds to button inputs that move the cursor across the board, and can find an optimal series of inputs by finding a path on this graph that is sort of a TSP variant: given a graph G and any number of disjoint subsets of G, find a path of minimal weight that visits at least one node of every subset.

I can reduce that to another TSP variant: given a graph G and a subset of G, find a path of minimal weight that visits every vertex in that subset. This is actually a pretty common problem that reduces to a non-returning TSP variant, where you don't have to start and stop at the same vertex. In this case I define the starting point (top left corner), but the end location is arbitrary.

Then to handle two players, I add a node P connecting the two starting positions of the two players (top left and bottom right), and then a node S that connects to every vertex so that it reduces to the classic TSP (finding a cycle). Then, instead of using a heuristic to find the minimal weighted cycle, I instead find the sum of the weights of edges between P and S (for player one), and between S and P (for player two). The heuristic would try to minimize the maximum of these two numbers, which corresponds to trying to get both players to pull equal weight, therefore ending the level quicker.

Yeah sure the biggest puzzles in the game might come down to solving TSP with >2000 nodes and over 2 million edges, but a reduction is a reduction!


Stevoisiak
@Stevoisiak

I discovered Picross speedruns and thoughy I might want to try TASing it. I found this while searching to see how the traveling salesman problem would apply to Picross.



glassbottommeg
@glassbottommeg

I feel like a lot of us currently run our devblog via Patreon because I mean, it's something we basically already want to write, but can barely find an excuse/audience for. So we put it behind a $1 bucko entry fee that friends were already kicking us, and then hey, free encouragement to actually write the thing. Works great.

Buuuuut Patreon just lost, what, 70% of its value? I think? So that seems. Bad. Guessing they're going to be a casualty of dotcom 2.0.

Which then leaves a whooooole lot of us in devblog land off in who knows where, and then hey. Look at this. neo-Tumblr! And it fits like a cozy, worn-in tshirt!

So yeah. Still not sure how I'll use this site or for what exactly, but hoooo boy. Patreon dying would definitely send a wave of people this way, I expect. And that seems like a given now.