Tetris Is Hard, Even to Approximate | Hacker News Reader

Tetris Is Hard, Even to Approximate

arxiv.org

126 pointsColinWright39 comments

Worth linking to the most famous of these authors, Erik Dermaine. More or less a prototypical child genius in math / CS. MIT Professor at 20.

https://en.m.wikipedia.org/wiki/Erik_Demaine

Also highly recommended basically any filmed class he’s teaching on MIT OpenCourseware

I quite like his presentation format for his online lectures (example - [1]); 3 panels - (1) video of him explaining/board work (2) notes (3) slides, all sync-ed. When he changes topic the slide and notes panel also move forward. And I think this has been around for ~ 10 yr now.

[1] http://courses.csail.mit.edu/6.849/fall10/lectures/L01.html

This dude is amazing. Did not know about him. Thanks!

Also fun to point out that Erik was given the title "Tetris Master" for this paper: https://erikdemaine.org/images/tetris_award_large.jpg

I love his skip-lists lecture: https://www.youtube.com/watch?v=kBwUoWpeH_Q

Is he programming? I wonder if we'd all be doing exciting stuff like this if we didn't fall into the trap of programming.

I was not even programming at 20, let alone working as a Professor.

This is a version of Tetris in which random pieces appear, not the classic version where all 7 of the pieces appear in a shuffled order over and over.

The original NES variant (which is used for professional play) has random pieces.

I think this is also true for GB?

The GB version is the definitive version for me, I’ve never been able to find a modern version on any device that feels the same.

It was the only game I had for my GB, I played the crap out of that game to the point I’d dream about it or see the tiles when I closed my eyes.

Totally agree and I've always wondered how much of that has to do with the hardware feel.

It's available on the 3DS as a Virtual Console, and it's identical in every way, including the controls.

> I played the crap out of that game to the point I’d dream about it or see the tiles when I closed my eyes.

I'm sure you already know this, but for anyone who doesn't, this phenomenon is actually common enough to have a name: https://en.m.wikipedia.org/wiki/Tetris_effect

You're probably thinking of the "Random Generator" which is used by the Tetris Company for new Tetris games around 2001 or so. Previous Tetris games did not necessarily use this system (I know the NES and Gameboy versions certainly did not) and the other popular variant, Tetris Grand Master, has its own system. Sources below:

https://tetris.wiki/Tetris_Guideline#See_also

https://tetris.wiki/Random_Generator

https://tetris.wiki/TGM_randomizer

Yes, that is in accordance with section 5.1 of the Tetris specification. https://www.colinfahey.com/tetris/tetris.html

The definition of "Standard Tetris" is an idealized model of the most important characteristics and behaviors of the first IBM-PC implementation of the Tetris game (circa 1986-1988). The idealized model is based upon inferring the apparent intentions of the developers of the first IBM-PC implementation of the Tetris game. For example, it seems reasonable to infer that the developers of the first IBM-PC implementation of the Tetris game intended to select the shape of each new falling piece "randomly", and that the use of the Borland C implementation of the rand() function was merely a practical approximation of the intention. The definition of "Standard Tetris" specifies that the shape of each new falling piece is to be selected "randomly". This ideal behavior cannot be achieved by any implementation, but implementations can approximate the ideal behavior.

Yes, so much research in Computer Science has been based on Tetris that someone found it worthwhile to create a specification for the game.

Bag randomizers are a modern thing, imposed by the Tetris company on all Tetris games released for the last couple decades. Classic Tetris almost universally used a standard rng, sometimes with some memory mechanism to attempt to prevent runs (ie. Remember the last piece and attempt a reroll N times to get a non duplicate piece. I believe nestris used a 1 piece memory).

You were definitely not guaranteed to get an I piece in any particular number of drops in any Tetris released in the 80s afaik. I think bag randomizers came about in Tetris worlds

Not random; there's no notion of randomness here. It's worst case analysis in a Tetris board that is provided in the input to the algorithm (i.e. with input length proportional to its size, as opposed to specifying integers corresponding to its dimensions, which will give a not-easier computational result), alongside a sequence of tetrominos; the question is to devise a strategy of player moves achieves a standard objective; e.g. the maximum number of rows cleared, or achieves the objective to within an approximation.

That it is NP-complete says that verification that a sequence indeed attains this maximum is easy (even if we don't know the maximum beforehand), but that it is unlikely we will find an efficient algorithm for the problem.

The authors note that there is a "relatively simple dynamic program solves the case of a constant-size gameboard in time polynomial in the number of pieces." So what you seem to be thinking of is solvable quite efficiently.

Interesting. I would think ML would do well to copy players. When I play it's a rather boring game, I'm almost always just setting up for the |. I can imagine trying to approximate a player using a complex branch if/else structure being complicated code. But I have to wonder if deep ML would be a rather impressive implementation (even without seeing the next block). The only thing that kills my game is the ever increasing speed, which wouldn't matter to ML.

That’s the high level, however t has thousands of micro decisions each time, such as some situations where you might choose to create a hole to maximize a clear later, or when it is better to try to Tetris at higher levels as compared to clear the lower ones to avoid getting too high and therefore harder or impossible to manipulates the pieces properly.

Well, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.

What does "too well” mean?

The paper proves that Tetris is NP hard, but that is only because Tetris is infinitely long game. It's still easy for a computer to play as well as a human and faster

That is the "even to approximate" part. It means that Tetris is NP-hard AND no polynomial time algorithm can be shown to be within a constant factor of the optimal solution. Eg no matter how good your Tetris bot is, there may be one that is a thousand times better waiting to be discovered.

ML is all about finding approximate solutions. Categorizing problem as NP-complete only makes sense when talking about exact solutions.

that's not true at all https://en.m.wikipedia.org/wiki/Approximation_algorithm#Hard...

Please point out where I am (completely!) wrong.

I have formally dealt with approximation algorithms before and I skimmed the wikipedia article, yet I did not find anything that contradicts me. Note the in the section on hardness, P and NP (obviously) appear as bounds of solutions. Where is the contradiction?

Further, all this (approximation algos and P/NP algos) are discrete, complete algorithms. ML is a completely different story, as one is never certain whether some optimum is global or local. Hence, ML is a heuristic, while Djikstras shortest path algorithm is a series of steps with a success guarantee (with provable worst runtime behavior).

Eventually, the speed kills everyone’s game. It literally becomes impossible to get pieces to the edge. (This is in NES Tetris.)

Imo NES Tetris gets a bit too much attention, there's plenty of better Tetris games if you want to talk about speed (SEGA Tetris, TGM, clones like DTet or Cultris, and so forth.)

Ironically, tgm gets much faster (nestris tops out at 1 row dropped per frame, tgm at 20) but the faster speeds in tgm are much much easier (and more fun imo) to control because of various other variables in how dropping and locking work.

Agreed. TGM is probably my favorite Tetris game; once you get used to the rotation it feels very natural without needing to go through the wall kick gymnastics of modern guideline Tetris. Sadly it seems Arika is either not able or not willing to produce more TGM games using their own ruleset. The guideline Tetris ruleset feels ass backwards in comparison, but I guess it really doesn't matter too much.

I never quite hit GM in any TGM game anyways; as fun as it was, I definitely had trouble keeping a clean stack at high speeds.

I got my first GM a couple months ago. Definitely felt like an achievement.

Afaik Arika is not allowed to make non-guideline Tetris games, but the fact that they made Tetris 99 for the switch has got some rumors going that they reached some kind of agreement and maybe a tgm4 could actually happen again.

TGM4 didn't fail due to TTC licensing issues. They had a hard time getting arcade vendors to co-operate and distribute cabinets. TGM1 and 2 (plus TAP+) were made before TTC started to enforce their rotation guidelines for games and that's why TGM3 and TGM Ace had the "World" and "classic" modes. Former being the TTC required rotation system and Classic being the (superior imo) Arika rotation system.

TGM4 is essentially finished and just in hold until Arika figures out how they're going to distribute it. I think you're right though that T99 is kinda Arika testing the waters with a console version and I think they might release it on Switch at least.

Has someone tried to implement public key cryptography with Tetris?

I thought Tetris was pretty easy for a computer to play: to decide where to put the next piece, just maximize flatness of the surface while penalizing holes.

I'm hence surprised about the hardness of approximation result.

You are right: the authors observe that when the size of the playing field is fixed and the only variable is the sequence of tetrominoes (which may vary arbitrarily in length), Tetris can be solved in polynomial time with a dynamic programming approach.

The authors' contribution is that the problem of choosing the optimal strategy is NP-complete when the playing field is itself variable, and provided as an input to the algorithm (as a matrix of 1s and 0s indicating whether or not the cell is filled, or equivalently, as the number of cells in the grid provided in unary base.)

This is a very thorough analysis. It's not that surprising to me, given the existing knowledge about the complexity of this type of game:

https://en.wikipedia.org/wiki/Tile-matching_video_game#Compu...

The paper is from 2002, all of the references in that Wikipedia article are younger (and indeed, reference [16] even cites the Tetris is Hard paper).

(2002)

It's not like Tetris has gotten any easier to approximate in the last 17 years.

Reply on news.ycombinator.com