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