4 ms·
Tetris Is Hard, Even to Approximate
- inevitable2 8y agohttps://www.cs.montana.edu/courses/spring2004/513/resources/BH03.pdf https://www.cs.montana.edu/courses/spring2004/513/resources/...
- djtriptych 8y agoWorth 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 https://en.m.wikipedia.org/wiki/Erik_Demaine Also highly recommended basically any filmed class he’s teaching on MIT OpenCourseware
- abhgh 8y agoI 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 http://courses.csail.mit.edu/6.849/fall10/lectures/L01.html
- tomcam 8y agoThis dude is amazing. Did not know about him. Thanks!
- jackpirate 8y agoAlso fun to point out that Erik was given the title "Tetris Master" for this paper: https://erikdemaine.org/images/tetris_award_large.jpg https://erikdemaine.org/images/tetris_award_large.jpg
- maxmcd 8y agoI love his skip-lists lecture: https://www.youtube.com/watch?v=kBwUoWpeH_Q https://www.youtube.com/watch?v=kBwUoWpeH_Q
- amelius 8y agoIs he programming? I wonder if we'd all be doing exciting stuff like this if we didn't fall into the trap of programming.
- padthai 8y agoI was not even programming at 20, let alone working as a Professor.
- stcredzero 8y agoHas someone tried to implement public key cryptography with Tetris?
- gqcwwjtg 8y agoThis 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.
- maxmcd 8y agoThe original NES variant (which is used for professional play) has random pieces.
- Waterluvian 8y agoI think this is also true for GB?
- jamiek88 8y agoThe 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.
- everly 8y agoTotally agree and I've always wondered how much of that has to do with the hardware feel.
- frosted-flakes 8y agoIt's available on the 3DS as a Virtual Console, and it's identical in every way, including the controls.
- QuinnWilton 8y ago> 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 https://en.m.wikipedia.org/wiki/Tetris_effect
- schoen 8y ago(2002)
- MrEldritch 8y agoIt's not like Tetris has gotten any easier to approximate in the last 17 years.
- rhacker 8y agoInteresting. 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.
- cfcosta 8y agoThat’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.
- ComplexSystems 8y agoWell, according to this paper, ML can't do too well, unless you can use ML to solve NP-complete problems.
- hopler 8y agoWhat 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
- bjourne 8y agoThat 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.
- schwurb 8y agoML is all about finding approximate solutions. Categorizing problem as NP-complete only makes sense when talking about exact solutions.
- userbinator 8y agoThis 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#Computational_complexity https://en.wikipedia.org/wiki/Tile-matching_video_game#Compu...
- mmarx 8y agoThe 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).
- temprunberkdk 8y ago> “Job creators, entrepreneurs, these are the people who make America great.” So there are people walking around with substantial wealth who think that they have it because they’re better. I can think of a certain social media entrepreneur that definitely think he is some sort of genius.
- sddfd 8y agoI 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.
- jhanschoo 8y agoYou 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.)