3 ms·
Tetris is NP Hard. Also Hatris: https://www.youtube.com/watch?v=EIBqEUvvDi0 https://www.youtube.com/watch?v=EIBqEUvvDi0 Not sure if your comment was to say "I
by __s 9y ago
Tetris is NP Hard. Also Hatris: https://www.youtube.com/watch?v=EIBqEUvvDi0 https://www.youtube.com/watch?v=EIBqEUvvDi0
Not sure if your comment was to say "I thought tetris was easy in a turn based environment, turns out I was wrong" or if you were contradicting the linked thread without basis
- nrook 9y agoI think your disagreement comes from a problem of definition. This paper (linked in the mathoverflow thread) appears to demonstrate playing Tetris optimally is NP-hard, even in a turn-based environment; that's because playing Tetris optimally involves getting lots of Tetrises, not just surviving indefinitely. http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-865.pdf http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-86... In contrast, it's not clear to me that playing Tetris indefinitely with the piece randomizers used in current Tetris games is NP-hard.