Editing Tetris (section)

=== Computer science research ===
In 1992, John Brzustowski at the [[University of British Columbia]] wrote a thesis on the question of whether or not one could theoretically play ''Tetris'' forever.<ref>{{Cite thesis |last=Brzustowski |first=John |title=Can you win at Tetris? |date=March 1992 |degree=Master of Science |publisher=[[University of British Columbia]] |url=https://open.library.ubc.ca/media/stream/pdf/831/1.0079748 |format=PDF |archive-url=https://web.archive.org/web/20220318064558/https://open.library.ubc.ca/media/stream/pdf/831/1.0079748 |archive-date=March 18, 2022 |access-date=October 16, 2013 |url-status=live}} [https://archive.org/details/20220318_20220318_0433 Alt URL]</ref> He reached the conclusion that ''Tetris'' is statistically doomed to end. If a player receives a sufficiently large sequence of alternating S and Z tetrominoes, the naïve gravity used by the standard game eventually forces the player to leave holes on the board. The holes will necessarily stack to the top and end the game. If the pieces are distributed randomly, this sequence will eventually occur. Thus, if a game with, for example, an ideal, uniform, uncorrelated [[Random number generation|random number generator]] is played long enough, any player will [[almost surely]] top out.<ref>{{Cite web |last=Burgiel |first=Heidi |date=January 7, 1996 |title=Discussion of the Tetris Applet |url=http://www.math.uic.edu/~burgiel/Tetris/explanation.html |url-status=dead |archive-url=https://web.archive.org/web/20061209110731/http://www.math.uic.edu/~burgiel/Tetris/explanation.html |archive-date=December 9, 2006 |access-date=February 25, 2007 |website=Tetris Research Page}}</ref><ref>Heidi Burgiel. [http://www.geom.umn.edu/%7Eburgiel/Tetris/tetris.PS How to Lose at Tetris] {{webarchive|url=https://web.archive.org/web/20030513033006/http://www.geom.umn.edu/~burgiel/Tetris/tetris.PS |date=May 13, 2003 }}, Mathematical Gazette, vol. 81, pp. 194–200 1997</ref>

In [[computer science]], it is common to analyze the [[Computational complexity theory|computational complexity]] of problems, including real-life problems and games. In 2001, a group of [[MIT]] researchers proved that for the "offline" version of ''Tetris'' (the player knows the complete sequence of pieces that will be dropped, i.e. there is no hidden information) the following objectives are [[NP-complete]]:
# Maximizing the number of rows cleared while playing the given piece sequence.
# Maximizing the number of pieces placed before a loss occurs.
# Maximizing the number of simultaneous clearing of four rows.
# Minimizing the height of the highest filled grid square over the course of the sequence.

Also, it is [[Hardness of approximation|difficult to even approximately solve]] the first, second, and fourth problem. It is [[NP-hard]], given an initial field and a sequence of ''p'' pieces, to approximate the first two problems to within a factor of {{nowrap|''p''<sup>1 − ''ε''</sup>}} for any constant {{nowrap|''ε'' > 0}}. It is NP-hard to approximate the last problem within a factor of {{nowrap|2 − ''ε''}} for any constant {{nowrap|''ε'' > 0}}. To prove NP-completeness, it was shown that there is a polynomial [[Reduction (complexity)|reduction]] between the [[3-partition problem]], which is also NP-complete, and the ''Tetris'' problem.<ref>{{cite conference|url=http://erikdemaine.org/papers/Tetris_COCOON2003/paper.pdf|title=Tetris is Hard, Even to Approximate|last1=Demaine|first1=Erik D.|last2=Hohenberger|first2=Susan|last3=Liben-Nowell|first3=David|date=July 25–28, 2003|conference=Proceedings of the 9th International Computing and Combinatorics Conference (COCOON 2003)|conference-url=https://web.archive.org/web/20120105042734/http://www.cs.montana.edu/bhz/cocoon03.html|location=Big Sky, Montana|access-date=December 18, 2009|archive-url=https://web.archive.org/web/20100613201613/http://erikdemaine.org/papers/Tetris_COCOON2003/paper.pdf|archive-date=June 13, 2010|url-status=live}}</ref><ref>{{cite book |url=https://archive.org/details/powerupunlocking0000lane/ |last=Lane |first=Matthew |title=Power-up: Unlocking the Hidden Mathematics in Video Games |publisher=[[Princeton University Press]] |date=2017 |pages=165–166 |isbn=9780691161518 |via=[[Internet Archive]] |url-access=registration}}</ref>