# SpritetrisJune 3, 2013 11:34 AM   Subscribe

By rotating, positioning and dropping a predetermined sequence of pieces, the Tetris Printer Algorithm (video) exploits the mechanics of Tetris to generate arbitrary bitmap images.
posted by a snickering nuthatch (15 comments total) 11 users marked this as a favorite

The writeup jumps into a lot of details with basically zero context, but if you watch the video first, you'll get it right away.
posted by a snickering nuthatch at 11:35 AM on June 3, 2013 [1 favorite]

I'm not understanding the word "predetermined". It knows what pieces are coming? Why can't you print with unknown pieces come? It might take longer, but that's why we have computer players.
posted by DU at 11:44 AM on June 3, 2013

Why can't you print with unknown pieces come? It might take longer, but that's why we have computer players.

Because Tetris is Hard, Even to Approximate. Specifically:
it is NP-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p^(1-epsilon), when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of (2 - epsilon), for any epsilon>0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.
posted by jedicus at 11:49 AM on June 3, 2013 [3 favorites]

The point is that I strongly suspect that if you don't know the sequence of pieces in advance then achieving an arbitrary board state is similarly hard.
posted by jedicus at 11:50 AM on June 3, 2013

This does not simulate a player and a game separately, or use a simulated player to automate a pre-existing implementation of tetris (which, I think, would've been even cooler). The algorithm gets to pick the pieces it wants to do its image thing.
posted by a snickering nuthatch at 11:51 AM on June 3, 2013

Jedicus- I believe that, even if it had to follow conventional tetris rules and was handed random pieces* by a separate routine, what this program seeks to do is easier than any of the optimization problems in that paper.

*Incidentally, the pieces you get aren't selected uniformly at random in many Tetris implementations. Instead, it's very much like drawing from a deck of cards with, say, 2 copies of each piece in the deck, reshuffling the deck after all the cards have been drawn. This puts a hard limit on the number of times you can get any given piece in a row.
posted by a snickering nuthatch at 11:57 AM on June 3, 2013

I don't get it. How come, for example, Mario's leading foot doesn't fall to the floor? At about 0:37 into the video.
posted by Flunkie at 11:57 AM on June 3, 2013

Never mind. Just been too long since I've played Tetris.
posted by Flunkie at 11:59 AM on June 3, 2013

I believe that, even if it had to follow conventional tetris rules and was handed random pieces* by a separate routine, what this program seeks to do is easier than any of the optimization problems in that paper.

Ah, I responded after watching the video but before I read the page. Yeah, it's working out the sequence of pieces it needs ahead of time and using only those pieces. Using a random sequence and trying to clear lines of unwanted pieces while waiting for a wanted piece would be an extremely hard if not impossible problem (in the general case).
posted by jedicus at 12:08 PM on June 3, 2013

The point is that I strongly suspect that if you don't know the sequence of pieces in advance then achieving an arbitrary board state is similarly hard.

But Tetris isn't hard because you don't know what's coming. It's hard because Knapsack Problem. Isn't it?
posted by DU at 1:41 PM on June 3, 2013

...it's working out the sequence of pieces it needs ahead of time and using only those pieces.

Ah, so "predetermined" = "self-determined". Sure, that wouldn't be too hard.
posted by DU at 1:42 PM on June 3, 2013

This is one of the things you don't ask "why?" to, right?
posted by spinn at 1:48 PM on June 3, 2013

But Tetris isn't hard because you don't know what's coming. It's hard because Knapsack Problem. Isn't it?

Hmm..it had been several years since I read the Demaine et al. paper. Their result was for the offline version of Tetris in which the player has perfect knowledge of the sequence of pieces, though the sequence is random. In my memory I had confused randomness and foreknowledge.

Anyway, if achieving one board state (maintaining an empty field or at least minimizing the maximum height of an occupied square) is NP-complete, then I suspect it is similarly difficult to achieve an arbitrary board state, whether you know the sequence of pieces or not.

Demaine et al. actually used 3-Partition for the reduction, not the knapsack problem.
posted by jedicus at 1:49 PM on June 3, 2013

Incidentally, drawing patterns in tetris is something humans occasionally do.
posted by a snickering nuthatch at 2:53 PM on June 3, 2013

What, no Lenna?
posted by dhartung at 5:16 PM on June 3, 2013 [3 favorites]

« Older All Powerful Bike Lobby   |   What It's Really Like To Be A Google Intern Newer »