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.
I'm hence surprised about the hardness of approximation result.
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.)