Not random; there's no notion of randomness here. It's worst case analysis in a Tetris board that is provided in the input to the algorithm (i.e. with input len

Not random; there's no notion of randomness here. It's worst case analysis in a Tetris board that is provided in the input to the algorithm (i.e. with input length proportional to its size, as opposed to specifying integers corresponding to its dimensions, which will give a not-easier computational result), alongside a sequence of tetrominos; the question is to devise a strategy of player moves achieves a standard objective; e.g. the maximum number of rows cleared, or achieves the objective to within an approximation. That it is NP-complete says that verification that a sequence indeed attains this maximum is easy (even if we don't know the maximum beforehand), but that it is unlikely we will find an efficient algorithm for the problem. The authors note that there is a "relatively simple dynamic program solves the case of a constant-size gameboard in time polynomial in the number of pieces." So what you seem to be thinking of is solvable quite efficiently.