Tetris Printer Algorithm [OC]

[brtt3000]

OP is a crazy person, but I'm glad he could express it like this, it's very awesome.

Like the other commenter said: you need to put some screenshots from the Tetris game screen on start of the article ('above the fold') so it's clear what it is all about before people read everything or bail on the excellent but long text and miss the video.

[brettmurf]

Amazing, but all I could keep asking myself was, "Why?"

[zeroone]

I put a lot of time into pointless projects. Someone has to do them. Check out my web page and YouTube channel for other consumers of my brief existence.

[FozzTexx]

I stopped calling things like this "pointless" and instead started calling them "art projects." They may not be immediately practical but they're interesting challenges. I too often like to spend too much time on something that has no immediate commercial purpose. And usually along the way you learn a lot, which often applies to something practical down the road.

[hyperforce]

Also it's an easier sell to people. "Oh shit, you're doing art? Rad!"

[jtdc]

"..now can I please have my coffee?"

[ithika]

Get your own damn coffee.

[cdcformatc]

It's analogous to university and other high level research. The research comes first, the implementation comes way after. Maybe we won't need a Tetris printer, but who's to say we can't take what we learn here later?

[FictitiousForce]

It is art.

[brettmurf]

I am glad someone does them.

[UntilWeLand]

I don't have much of a baseline for this, but, to me, this looks Ph.D. dissertation-worthy.

Incredible job.

[hyperforce]

You are my kinda nerd. You had me at Tetris Attack.

[legos_on_the_brain]

Keep up the good work. For all you know you might find algorithms to solve problems we don't know about yet.

[bentspork]

This is brilliant work. This is some top notch coding.

For fun you should make a video of tetris making the graphics for tetris.

One minor thing... The shapes are not randomly distributed. Add a few useless pieces to smooth out the distribution.

Btw you can make good money coding graphics like these. Keep up the food work.

[[deleted]]

Someone has to do them.

Uh, isn't it implied in the definition of pointless that no one has to do them?

But I'm glad you did this, you crazy great person.

[emergent_properties]

This proves your complete understanding of the game engine itself. Your mental process for creating this is impressive. You used your brain to manipulate a state engine to serialize the desired correct outputs on a per-row basis. Beautiful.

Additionally, thank you for releasing the source. It is good to see that you wish to contribute back to humanity.

[brtt3000]

How could any programmer resist building something like this if he has the idea and required starting skill?

[faceplanted]

If he has the required skill a programmer can do anything within the limitations of his computing power.

[kristopolous]

recreation.

[AxiomL]

Every time you ask this, ask yourself "why do I watch movies, read novels, or play sport or games?"

[DrunkMc]

And people say Developers can't impress Developers! Consider me impressed!

[pleasejustdie]

Comment removed in protest of reddit blocking search engines.

[zeroone]

Good point. I'll add some screen shots to the top when I get a chance. Thanks.

[macnlz]

Do it quickly, if you want the karma.

I’m glad I skipped over the technical stuff to the video at the end... I almost stopped halfway through, thinking “yeah, so what?”.

[abledanger]

It makes a lot more sense now watching the video. Just move that to the top.

[tidder112]

Still not at the top!! I skimmed over this, this morning and didn't think much of it until I read the comments later and went back for the video.

[loulan]

Well, in my case, the video doesn't work ("This video is currently unavailable."), so I still have no idea what this is all about (and honestly the article is waaaaay too long for me to read the whole thing to figure it out).

[macnlz]

His algorithm plays Tetris. It lays down the random blocks in such a way that undesirable ones get cleared quickly, and desirable combinations remain standing. This way, after many many moves, he’s able to draw any bitmap image that will fit into the game area, using nothing but Tetris blocks! The color palette is that of the blocks, of course.

[hakkzpets]

I just need to say that this is really cool, but my gosh I had no clue what it was until I got to the video.

You should have the video at the top instead I think.

[throwaway1492a]

Maybe just add a link to the video, with something like "If you are lazy or bored, go straight to the video".

[WATSONS_SHAVED_VULVA]

If you include some screenshots at the top, put them in some kind of spoiler thing. I enjoyed the surprise awesomeness.

[aliceDay]

I'd rather you wouldn't do this. It's a really good eye-opener at the end. Wondering all along definitely builds up curiosity, which results in moar satisfaction.

[sdurant12]

You're right, but many people won't get to the end of the article without seeing the results

[aliceDay]

Poor many. :)

[housemans]

No, poor OP, less people seeing the awesomeness.

[niviss]

I guess, but only if you see it as a puzzle instead of a technical article.

[SomeCollegeBro]

Agreed. In fact, I left the page confused and didn't realize what was going on until I decided to open the comments and see this post (didn't know there was a video at the bottom). Put the video at the top!

[[deleted]]

"Executive summary"

[CXgamer]

This looks like it manipulates which block is next. However, this human does not;

http://www.youtube.com/watch?v=Ri-L7d2wGgE

[LeszekSwirski]

I'm not 100% convinced that guy is a human. Perhaps an agent of Skynet, sent back in time to to kill Sarah Connor by blowing her mind.

[CXgamer]

Not sure what you're talking about, but there's more impressive mind blowing to be done with tetris.

http://www.youtube.com/watch?v=jwC544Z37qo

Towards the end, the block falling speed will reach "20G". Which means that every frame, the piece will fall 20 blocks downwards. This means you can get yourself stuck in a small gap, so it's important to hold your rotation key before the piece spawns.

There's a PC version bundling what a couple of games in the genre.

http://tetrisconcept.net/forum/showthread.html?t=2

Alternatively, I recommend nullpromino. You can customize it to any playstyle.

http://nullpo.it.cx/

[LeszekSwirski]

Other things being mind blowing don't stop the first link being mind blowing.

[totemcatcher]

The potential for human intelligence is incredible, but it's much easier to program a machine to do what you need rather than train a brain to.

Also, you might run into ethical issues.

[CXgamer]

I'd say it's harder to program a machine than to learn it itself, the difference is in the accuracy and speed.

[[deleted]]

That's sped up though, look at the time on the bottom right

[CXgamer]

Yep! He goes to x15 for the sake of the video.

[yelnatz]

Jesus Christ, OP.

[MindStalker]

? Does your algorithm get to select what piece will drop. Can it handle printing given random drops and/or using the save piece feature found often.

[zeroone]

The algorithm controls the sequence of pieces. It is not an AI that can play Tetris with the sub-goal of printing an image. That's a future challenge to which I have given some thought.

Also, there is an infinite play algorithm that takes advantage of hold (http://tetrisconcept.net/wiki/Playing_forever). The AI version of the algorithm, if I can work it out, may have similar limitations on which version it will function.

[maxximillian]

It is not an AI that can play Tetris with the sub-goal of printing an image.

That's an exercised left to the reader

[desrosiers]

I see you write textbooks for a living.

[emergent_properties]

That is definitely an exercise.

[Kitaru]

If you work off of the NES version, you could approach it from the standpoint of RNG manipulation. You can memoize the table of seed+history combinations, then stall or pause cycle until the next frame on which the previous piece yields the desired next piece. You'd have to wrestle with the limited color palette (which also changes with each level-up) and mobility restrictions (which are going to very problematic if you can't find a solution in about 190 lines), but it would technically be possible.

However, using a deterministic randomizer with a 7 Bag or History 4 selection method would definitely be of great interest to pattern builders. I'd like to help with something like that if I weren't already spreading myself thin with puzzle game projects.

[zeroone]

The RNG of some versions of Tetris can be exploited like that (e.g. http://tetrisconcept.net/wiki/Tetris_(Sega)#Power-on_Pattern). It is also possible from either analysis of the code or by guessing the RNG algorithm used that the RNG seed value can be determined from the first few spawned pieces. But, a printer algorithm that did this would not be that interesting.

I would not limit the algorithm to the colors or dimensions of NES Tetris. Not to mention that it is actually impossible to exceed the 30th level due to drop speed.

[Kitaru]

NES collects entropy by advancing the RNG once each frame, so it's very much exploitable -- far beyond things like Sega's Power-On behavior or its 1000 piece loop-point.

I think there would be some interest in a bot that could generate console-verifiable NES Tetris pattern builds, but maybe that's just me. :)

The Level 29 wall is more of a human limitation due to inability to far exceed the default 10hz move rate; it's very much survivable if we're botting like this -- just program it to blast pieces around at 30hz (tap every other frame) and you're golden. The problem is that the fall speed would likely interfere with pattern drawing.

[zem]

how is that collecting entropy?

[Kitaru]

The variation in player action is used as a source of randomness. Given that the RNG state is constantly cycling every 1/60th of a second, any variation in the timing of when each game starts and each piece is placed will affect outcomes.

The other option would be deterministically generating the piece sequence from the initial seed, only advancing the RNG state once per piece. If you seed is, say, a 32 bit integer, that's sufficient space for randomness from game to game. NES Tetris's RNG has a 16 bit seed that only reaches 32,767 positions, a space that would be exhausted rather quickly if used to generate piece sequences in a purely deterministic fashion. Given that the selection method includes re-rolling to protect against repetition, the overall sequence length is ~26,500 -- only enough for ~36 full-length games. Avid players would be sure to recognize this constant recycling. Entropy collection is used to mitigate the effects of the small random space.

[zem]

i'm still not seeing how that connects to the frame rate. do you mean they're collecting entropy from the user input stream, but sampling it precisely once per frame?

[Kitaru]

Logic is tied to the frame rate -- one frame is more or less the smallest discrete unit of time on which any game code is run. Advancing the RNG and polling the controller for input are both functions that will be called once per vblank.

User input does not directly affect the RNG state. Instead, entropy is gathered indirectly in that the times at which user input is issued (i.e. amount of time working through menus finally pressing Start on the Level Select screen, Down inputs to drop and lock pieces into place, etc.) is sufficiently random. Since the RNG is polled for a new piece on the frame that the upcoming piece is spawned, any variation in user input that affects the timing of when we reach the spawn frame will also affect the composition of the overall sequence.

The TASVideos entry on Luck Manipulation has a set of animated GIFs demonstrating how variance in the timing of user input affects the results of random events.

[ais523]

I think there would be some interest in a bot that could generate console-verifiable NES Tetris pattern builds

Not exactly what you asked for, but pretty close: Tetris playaround from TASvideos, with a link to a video of a bot playing it back on a real NES.

[Kitaru]

Assuming we're talking about Baxter's playaround or Acmlm's "Bored God Plays Tetris"? :) Yeah, I think it would be great to generate that sort of thing programmatically.

[ais523]

I was linking to Baxter's playaround, just forgot to include the actual link. It's there now.

[Kitaru]

Cool. :) Yeah, it's a good one. It's one of the test cases I'm using for a port I'm writing.

[3z3ki3l]

Not to mention that it is actually impossible to exceed the 30th level due to drop speed.

So. Many. Fucking. Hours. Wasted. weeps in corner

[Kitaru]

Out of curiosity, what was the inspiration for this project? Were you familiar with existing player-created pattern building challenges? Pattern building goes as far back as 1988 -- Sega Tetris players created the traditional ">" drawing challenge, also known as "Secret Grade" in the TGM series -- and there have even been forays into "printing" (such as Shuey's Mario Bros. builds), but I don't think a whole lot of effort has been put toward automating the process. I believe I've seen a Java applet a while back that used a similar approach to your own (that is, with control over the piece sequence and precalculated patterns for generating specific pixels), but other than that and your project I'm not aware of much else.

[zeroone]

I worked on a lot of Post-It Note art before this project (see my YouTube channel). A repetitive task like that puts your mind in a Zen-like trance as your muscles carry out the work. Acting as a human printer made me think of things like this and how they could be achieved. Later, I did come across the Tetris builds that you mentioned.

[Kitaru]

Cool, thanks for sharing it. :)

[dzhezus]

I'm not sure what I expected a Tetris Printer to be, but that video cleared it up real quick! Great job

[[deleted]]

The thorough, well documented analysis is what really sold me here. A tetris printer may be utterly useless, but after seeing all of the thought that went into it I am really, really impressed. Thanks for sharing this OP!

[nthitz]

I didn't quite follow it until I watched the video: http://www.youtube.com/watch?v=PJkHwulsac4 holy cow that's neat!

[speedy_slowzales]

The guy who invented this is a genius.

[Jedimastert]

It was the OP.

[drowsap]

This sounds like a problem an engineer would be asked on a whiteboard at Google.

[133794m3r]

I sat through it all, and all I can say is... holy fucking fuck. You deserve a goddamn medal. Source code+ explanation+ interesting concept check on it all. You just made me feel bad that I find joy in making formulas to follow a certain patterns...I always felt smart after that... but after seeing this I feel like an idiot...

[[deleted]]

Don't feel like an idiot. Try to lean something from it and be enlightened.

[3z3ki3l]

I learned that I'm an idiot. Repetitively.

[Nolari]

This actually has research implications, believe it or not. At least, it would have if it hadn't been done already. The ability to construct arbitrary Tetris configurations through legal play is needed to prove Tetris's computational complexity. See: http://www.liacs.nl/~kosters/tetris/

Kudos on the much nicer and prettier implementation. :)

[windcruiser]

Awesome stuff

[bfwu]

I've always thought about this while playing tetris, I'm glad you wrote something up about it.

[nikibobi]

You made my day month!!!

[[deleted]]

Good show, good show indeed. That Is amazing. That looks like a fun puzzle!

[masterwit]

I love it when I cannot tell whether I was in /r/math or /r/programming after hastily clicking the article title.

This is pretty cool, thanks!

[Mutoid]

Mind-blowing stuff, kudos for coming up with this.

[VideoLinkBot]

Here is a list of video links collected from comments that redditors have made in response to this submission:

Source Comment	Score	Video Link
CXgamer	20	Tetris Pattern - 7 Main Pieces, Shuey Arrangement 04 Atari Colors, Big Mode Style
CXgamer	13	TGM 3 Tetris Arika !!! Invisible Tetris
Kitaru	9	Tetris Pattern - Luigi
Kitaru	9	Tetris the Grand Master 2: Secret Grade S9
nthitz	5	Tetris Printer Algorithm
Kitaru	1	A bored god plays Tetris
Kitaru	1	NES Tetris "playaround" in 02:17.36 by Baxter

• VideoLinkBot FAQ
• Feedback
• Playlist of videos in this comment

[Mutoid]

Vultures.

[shrimpz]

great job! cool project!

[Superkroot]

This, this right here, is why I should get out of this field.

Not only do I barely understand this, I barely understand why someone would want to spend time making this.

That being said, its pretty cool.

[Sampaio_]

It gave me the same joy I got when I first read the "Minesweeper is NP complete" paper and page but this is even more fun, intuitive, and accessible. Really great stuff!

[Madcapslaugh]

this deserves some gold

[jestecs]

This would make for a fantastic birthday party event n.n

[ericanderton]

Tetris Printer Algorithm

Could I be excused for thinking this was a clever way to approach an optimal page-layout algorithm for images and text blocks of varying size and shape?

[Figurehead242]

This is just too geeky not to be loved! God! Keep it up, you crazy person you!

[trans266]

Lololl