Spritetris
June 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.
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
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:
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
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
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
*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
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
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
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
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
Ah, so "predetermined" = "self-determined". Sure, that wouldn't be too hard.
posted by DU at 1:42 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
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
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]
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 »
This thread has been archived and is closed to new comments
posted by a snickering nuthatch at 11:35 AM on June 3, 2013 [1 favorite]