6 ms·

Tetris Printer Algorithm

235 points by shill 13y ago

albertzeyer 13y ago
You should watch the video at the end: http://www.youtube.com/watch?v=PJkHwulsac4 http://www.youtube.com/watch?v=PJkHwulsac4 That just demonstrates the algorithm and makes it clear how it works.
ronaldx 13y ago
wow! The video has some nice examples, indeed. I suppose this method cannot be adapted to work for non-random 'bags' of Tetris shapes...?
JoshTriplett 13y ago
The comments point out that the printer algorithm gets to choose the next piece; however, it is possible to manipulate the next piece you get through the timing of dropping the previous piece, so in theory this algorithm could produce emulator inputs for a Tetris cart that would draw similar pictures. (Albeit limited to the "resolution" of that tetris field, unlike the extra-wide field used in the video.)
- Breakthrough 13y ago
  It really depends what version of Tetris you're talking about, but it might be possible if it follows the concepts of Playing Tetris Forever ( http://www.tetrisconcept.net/wiki/Playing_forever http://www.tetrisconcept.net/wiki/Playing_forever ) - specifically, the generator they use ( further discussed in the same Wiki on the http://tetrisconcept.net/wiki/Random_Generator http://tetrisconcept.net/wiki/Random_Generator page). That being said, it would be awesome if someone fit the algorithm onto a little microcontroller and got it to generate the control signals for a particular console (although as you already mentioned, resolution might be a limiting factor here...).
  - JoshTriplett 13y ago
    I was thinking of the original NES version, specifically. You'd need to emulate it yourself so that you could figure out when to supply inputs to manipulate the RNG and give yourself the pieces you need.
    - danielweber 13y ago
      Are the timings that precise? ISTR that there were only 24 or 100 frames per second, so a micro-controller ought to be able to send the proper signals.
      - JoshTriplett 13y ago
        A microcontroller can easily send the proper signals; check out NESBot for an example. Here's a video of NESBot playing the original NES Tetris with a series of inputs that manipulates the RNG: http://tasvideos.org/1502M.html http://tasvideos.org/1502M.html . You just need to emulate the game when planning out the series of moves, to figure out what timing to use to manipulate the RNG and get the pieces you want.
      - Breakthrough 13y ago
        They can be... Rickard Gunée actually generated a raw analog NTSC/PAL signal to be connected to a composite cable using a microcontroller: http://www.rickard.gunee.com/projects/video/sx/howto.php http://www.rickard.gunee.com/projects/video/sx/howto.php It's a pretty good read if you're into that sort of thing, and really helps explain the mechanics of analog video (and also gives you some hints about simulating it in software). He also created his own clones of Tetris and Pong that run on the MCU as well!
danielweber 13y ago
Without the video it was really hard to grasp what was going on, but this is awesome.
benkillin 13y ago
why on earth would you want to do this? this seems insane Don't get me wrong, the idea is non trivial and the writeup is great.
- deathcakes 13y ago
  Insanity is very close indeed to genius. Also, why not?
PetitPrince 13y ago
Nice algorithm ! Kind of related: in the Tetris community, there iss a human player who's specialty in making Tetris pattern (using legit piece generator). He began by making the classic ">" pattern (famous amonst the bored Japanese Sega-styled (TGM) Tetris players) [1]. Then he progressively improved and he can now do some quite impressive "sculpting". Check out his space invader [2], repeated triforce [3], Luigi [4] and the rest of his youtube channel. It's mesmerizing. [1] https://www.youtube.com/watch?v=yBrl2-f5vjI https://www.youtube.com/watch?v=yBrl2-f5vjI [2] https://www.youtube.com/watch?v=wF8KWzDxpqY https://www.youtube.com/watch?v=wF8KWzDxpqY [3] https://www.youtube.com/watch?v=B_buHvlra5A https://www.youtube.com/watch?v=B_buHvlra5A [4] https://www.youtube.com/watch?v=_tipJDjeKuY https://www.youtube.com/watch?v=_tipJDjeKuY [5] https://www.youtube.com/user/Shuey187/videos https://www.youtube.com/user/Shuey187/videos
- mtdewcmu 13y ago
  It would be more impressive seeing a person do it.
foobarbazqux 13y ago
There was a precursor in 2005, a paper called "How to Construct Tetris Configurations". Their output was monochrome, but I'm sure the proof results are transferable. http://scitua.scit.wlv.ac.uk/OJS_IJIGS/index.php/IJIGS/article/view/95 http://scitua.scit.wlv.ac.uk/OJS_IJIGS/index.php/IJIGS/artic... http://www.liacs.nl/~kosters/tetris/ijigstetrisfinal.pdf http://www.liacs.nl/~kosters/tetris/ijigstetrisfinal.pdf
erikb 13y ago
It should have shown the video at first. Even for scrolling it's too much until you find out what all that really is about, that you are not willing to read it any more.

235 points by shill 13y ago

You should watch the video at the end: http://www.youtube.com/watch?v=PJkHwulsac4 http://www.youtube.com/watch?v=PJkHwulsac4 That just demonstrates the algorithm and makes it clear how it works.

ronaldx 13y ago

wow! The video has some nice examples, indeed. I suppose this method cannot be adapted to work for non-random 'bags' of Tetris shapes...?

JoshTriplett 13y ago

The comments point out that the printer algorithm gets to choose the next piece; however, it is possible to manipulate the next piece you get through the timing of dropping the previous piece, so in theory this algorithm could produce emulator inputs for a Tetris cart that would draw similar pictures. (Albeit limited to the "resolution" of that tetris field, unlike the extra-wide field used in the video.)

Breakthrough 13y ago
It really depends what version of Tetris you're talking about, but it might be possible if it follows the concepts of Playing Tetris Forever ( http://www.tetrisconcept.net/wiki/Playing_forever http://www.tetrisconcept.net/wiki/Playing_forever ) - specifically, the generator they use ( further discussed in the same Wiki on the http://tetrisconcept.net/wiki/Random_Generator http://tetrisconcept.net/wiki/Random_Generator page). That being said, it would be awesome if someone fit the algorithm onto a little microcontroller and got it to generate the control signals for a particular console (although as you already mentioned, resolution might be a limiting factor here...).
- JoshTriplett 13y ago
  I was thinking of the original NES version, specifically. You'd need to emulate it yourself so that you could figure out when to supply inputs to manipulate the RNG and give yourself the pieces you need.
  - danielweber 13y ago
    Are the timings that precise? ISTR that there were only 24 or 100 frames per second, so a micro-controller ought to be able to send the proper signals.
    - JoshTriplett 13y ago
      A microcontroller can easily send the proper signals; check out NESBot for an example. Here's a video of NESBot playing the original NES Tetris with a series of inputs that manipulates the RNG: http://tasvideos.org/1502M.html http://tasvideos.org/1502M.html . You just need to emulate the game when planning out the series of moves, to figure out what timing to use to manipulate the RNG and get the pieces you want.
    - Breakthrough 13y ago
      They can be... Rickard Gunée actually generated a raw analog NTSC/PAL signal to be connected to a composite cable using a microcontroller: http://www.rickard.gunee.com/projects/video/sx/howto.php http://www.rickard.gunee.com/projects/video/sx/howto.php It's a pretty good read if you're into that sort of thing, and really helps explain the mechanics of analog video (and also gives you some hints about simulating it in software). He also created his own clones of Tetris and Pong that run on the MCU as well!

danielweber 13y ago

Without the video it was really hard to grasp what was going on, but this is awesome.

benkillin 13y ago

why on earth would you want to do this? this seems insane Don't get me wrong, the idea is non trivial and the writeup is great.

deathcakes 13y ago
Insanity is very close indeed to genius. Also, why not?

PetitPrince 13y ago

Nice algorithm ! Kind of related: in the Tetris community, there iss a human player who's specialty in making Tetris pattern (using legit piece generator). He began by making the classic ">" pattern (famous amonst the bored Japanese Sega-styled (TGM) Tetris players) [1]. Then he progressively improved and he can now do some quite impressive "sculpting". Check out his space invader [2], repeated triforce [3], Luigi [4] and the rest of his youtube channel. It's mesmerizing. [1] https://www.youtube.com/watch?v=yBrl2-f5vjI https://www.youtube.com/watch?v=yBrl2-f5vjI [2] https://www.youtube.com/watch?v=wF8KWzDxpqY https://www.youtube.com/watch?v=wF8KWzDxpqY [3] https://www.youtube.com/watch?v=B_buHvlra5A https://www.youtube.com/watch?v=B_buHvlra5A [4] https://www.youtube.com/watch?v=_tipJDjeKuY https://www.youtube.com/watch?v=_tipJDjeKuY [5] https://www.youtube.com/user/Shuey187/videos https://www.youtube.com/user/Shuey187/videos

mtdewcmu 13y ago
It would be more impressive seeing a person do it.

foobarbazqux 13y ago

There was a precursor in 2005, a paper called "How to Construct Tetris Configurations". Their output was monochrome, but I'm sure the proof results are transferable. http://scitua.scit.wlv.ac.uk/OJS_IJIGS/index.php/IJIGS/article/view/95 http://scitua.scit.wlv.ac.uk/OJS_IJIGS/index.php/IJIGS/artic... http://www.liacs.nl/~kosters/tetris/ijigstetrisfinal.pdf http://www.liacs.nl/~kosters/tetris/ijigstetrisfinal.pdf

erikb 13y ago

It should have shown the video at first. Even for scrolling it's too much until you find out what all that really is about, that you are not willing to read it any more.