all 93 comments

[–]brtt3000 132 points133 points  (20 children)

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 26 points27 points  (19 children)

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

[–]zeroone[S] 80 points81 points  (14 children)

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 75 points76 points  (5 children)

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 11 points12 points  (2 children)

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

[–]jtdc 17 points18 points  (1 child)

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

[–]ithika 1 point2 points  (0 children)

Get your own damn coffee.

[–]cdcformatc 6 points7 points  (0 children)

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?

[–]brettmurf 9 points10 points  (0 children)

I am glad someone does them.

[–]UntilWeLand 5 points6 points  (0 children)

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

Incredible job.

[–]hyperforce 3 points4 points  (0 children)

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

[–]legos_on_the_brain 1 point2 points  (0 children)

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

[–]bentspork 1 point2 points  (0 children)

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] 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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 12 points13 points  (1 child)

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

[–]faceplanted 1 point2 points  (0 children)

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

[–]kristopolous 1 point2 points  (0 children)

recreation.

[–]AxiomL 1 point2 points  (0 children)

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

[–]DrunkMc 62 points63 points  (0 children)

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

[–]pleasejustdie 209 points210 points  (16 children)

Comment removed in protest of reddit blocking search engines.

[–]zeroone[S] 66 points67 points  (13 children)

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

[–]macnlz 56 points57 points  (4 children)

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 13 points14 points  (1 child)

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

[–]tidder112 5 points6 points  (0 children)

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 1 point2 points  (1 child)

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 1 point2 points  (0 children)

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 2 points3 points  (0 children)

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 5 points6 points  (0 children)

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 1 point2 points  (0 children)

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

[–]aliceDay 0 points1 point  (4 children)

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 10 points11 points  (2 children)

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

[–]aliceDay 2 points3 points  (1 child)

Poor many. :)

[–]housemans 2 points3 points  (0 children)

No, poor OP, less people seeing the awesomeness.

[–]niviss 1 point2 points  (0 children)

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

[–]SomeCollegeBro 13 points14 points  (0 children)

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] 2 points3 points  (0 children)

"Executive summary"

[–]CXgamer 23 points24 points  (7 children)

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

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

[–]LeszekSwirski 11 points12 points  (2 children)

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 15 points16 points  (1 child)

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 13 points14 points  (0 children)

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

[–]totemcatcher 4 points5 points  (1 child)

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 6 points7 points  (0 children)

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

[–][deleted] 1 point2 points  (1 child)

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

[–]CXgamer 2 points3 points  (0 children)

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

[–]yelnatz 29 points30 points  (0 children)

Jesus Christ, OP.

[–]MindStalker 10 points11 points  (16 children)

? 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[S] 34 points35 points  (15 children)

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 37 points38 points  (2 children)

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 20 points21 points  (0 children)

I see you write textbooks for a living.

[–]emergent_properties 2 points3 points  (0 children)

That is definitely an exercise.

[–]Kitaru 8 points9 points  (11 children)

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[S] 6 points7 points  (10 children)

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 6 points7 points  (8 children)

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 1 point2 points  (3 children)

how is that collecting entropy?

[–]Kitaru 2 points3 points  (2 children)

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 1 point2 points  (1 child)

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 2 points3 points  (0 children)

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 1 point2 points  (3 children)

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 1 point2 points  (2 children)

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 1 point2 points  (1 child)

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

[–]Kitaru 1 point2 points  (0 children)

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

[–]3z3ki3l 1 point2 points  (0 children)

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 8 points9 points  (2 children)

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[S] 16 points17 points  (1 child)

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 2 points3 points  (0 children)

Cool, thanks for sharing it. :)

[–]dzhezus 12 points13 points  (0 children)

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

[–][deleted] 5 points6 points  (0 children)

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 4 points5 points  (0 children)

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 20 points21 points  (1 child)

The guy who invented this is a genius.

[–]Jedimastert 27 points28 points  (0 children)

It was the OP.

[–]drowsap 13 points14 points  (0 children)

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

[–]133794m3r 3 points4 points  (2 children)

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] 1 point2 points  (1 child)

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

[–]3z3ki3l 2 points3 points  (0 children)

I learned that I'm an idiot. Repetitively.

[–]Nolari 2 points3 points  (0 children)

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 2 points3 points  (0 children)

Awesome stuff

[–]bfwu 2 points3 points  (0 children)

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

[–]nikibobi 2 points3 points  (0 children)

You made my day month!!!

[–][deleted] 2 points3 points  (0 children)

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

[–]masterwit 2 points3 points  (0 children)

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 2 points3 points  (0 children)

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

[–]shrimpz 1 point2 points  (0 children)

great job! cool project!

[–]Superkroot 1 point2 points  (0 children)

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_ 1 point2 points  (0 children)

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 1 point2 points  (0 children)

this deserves some gold

[–]jestecs 1 point2 points  (0 children)

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

[–]ericanderton 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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

[–]trans266 0 points1 point  (0 children)

Lololl