I think your disagreement comes from a problem of definition. This paper (linked in the mathoverflow thread) appears to demonstrate playing Tetris optimally is

I 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.