Tetris is Hard, Even to Approximate

posted by @ulaulaman about #tetris #ComputerScience #NeuralNetwork

Before today I thought that tetris was a really simple game...

In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configuration of filled squares; any completely filled row of the gameboard is cleared and all pieces above it drop by one row. We prove that in the offline version of Tetris, it is NP-complete to maximize the number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously filled and cleared), minimize the maximum height of an occupied square, or maximize the number of pieces placed before the game ends. We furthermore show the extreme inapproximability of the first and last of these objectives to within a factor of p^(1-epsilon), when given a sequence of p pieces, and the inapproximability of the third objective to within a factor of (2 - epsilon), for any epsilon>0. Our results hold under several variations on the rules of Tetris, including different models of rotation, limitations on player agility, and restricted piece sets.⁽¹⁾

Tetris is a puzzle video game originally designed and programmed by Alexey Pajitnov and it could be used to learn to a neural network:

The cross-entropy method is an efficient and general optimization algorithm. However, its applicability in reinforcement learning (RL) seems to be limited because it often converges to suboptimal policies. We apply noise for preventing early convergence of the cross-entropy method, using Tetris, a computer game, for demonstration. The resulting policy outperforms previous RL algorithms by almost two orders of magnitude.⁽²⁾

The cross-entropy (CE) method is a general algorithm for (approximately) solving global optimization tasks (...). The main idea of CE is to maintain a distribution of possible solutions and update this distribution at each step.⁽²⁾

It is also possible to solve Tetris using an evolutionary algorithm:

The computer chooses the best move [in Tetris] by rating possible subsequent game boards based on a rating function. This function is primarily a weighted sum of several subratings. The evolutionary algorithm is used to find optimal weights for these.⁽³⁾

---

(1) Demaine E.D., Hohenberger S. & Liben-Nowell D. (2003). Tetris is Hard, Even to Approximate, Computing and Combinatorics Lecture Notes in Computer Science, 2697 351-363. DOI: 10.1007/3-540-45071-8_36 (arXiv - pdf; a short version)
About this paper, read also nature.com
(2) Szita I. & Lörincz A. (2006). Learning Tetris Using the Noisy Cross-Entropy Method, Neural Computation, 18 (12) 2936-2941. DOI: 10.1162/neco.2006.18.12.2936 (pdf)
(3) Niko Bohm, Gabriella Kokai, Stefan Mandl. An Evolutionary Approach to Tetris (pdf). MIC2005: The Sixth Metaheuristics International Conference

---

Cartoon via falcemartello, altrochenuovonuovo