Tetris

Tetris is a video game designed to waste time. Invented by Alexey Pajitnov whilst he was working for the Academy of Sciences in Moscow; inspired by a pentominoes game he had purchased earlier.

The Game

Tetrominoes, shapes composed of 4 blocks each, are falling down the screen, and one has to direct them so they will fit to the wall on the bottom. When a line of blocks has no gaps, it is complete and disappears.

The maximum number of lines that can be completed simultaneously is 4, since at least one block is required per line. This can only be achieved with the "I" tetromino: doing this is known as a "tetris".

In order to master the game, the technique of sliding a piece just before it sets is invaluable, as well as using both rotation buttons, when available.

Gravity

When a row of blocks is cleared and removed, the stacks of blocks above it fall. Many versions of Tetris implement a naive approximate gravity algorithm that always moves blocks down by a distance equal to exactly the height of the cleared rows below it. This can leave blocks floating in mid-air. Newer games may implement an improved algorithm that uses a flood fill to segment the playfield into connected regions and then makes each region fall individually, in parallel, until it touches the region at the bottom of the playfield. This opens up additional "chain-reaction" tactics involving blocks falling to fill additional lines, which those games tend to reward with a higher score.

Two falling algorithms on a 6-block-wide playfield.
Top row: naive algorithm; bottom row: improved algorithm that allows chain reactions.

Impact

A massively popular game, Tetris or a clone thereof has appeared on nearly every games machine available, it has even appeared as part of an art exhibition on the side of a building [1] (http://bastilleweb.techhouse.org/). Its most popular port has been to the Game Boy, considered by some the one true form of the game.

History and Legal Issues

The game called Tetris™ has been embroiled in a strangely large amount of legal battles since its inception. In June 1985, Alexey Pajitnov created Tetris on an Electronica 60 while working for the Academy of Sciences in Moscow. He created it at their Computer Center, and Vadim Gerasimov ported it to the IBM PC. From there, the game exploded into popularity, and began spreading all around Moscow. (This version is available on Vadim Gerasimov's web site at http://vadim.www.media.mit.edu/Tetris.htm .)

The IBM PC version eventually made its way to Budapest, Hungary, where it was ported to various platforms and was "discovered" by a British software house named Andromeda. They attempted to contact Pajitnov to secure the rights for the PC version, but before the deal was firmly settled, they had already sold the rights to Spectrum Holobyte. After failing to settle the deal with Pajitnov, Andromeda attempted to license it from the Hungarian programmers instead. Meanwhile, before any legal rights were settled, the Spectrum Holobyte IBM PC version of Tetris was released in the United States in 1986. The game's popularity was tremendous, and many were instantly hooked--it was a software blockbuster.

The details of the licensing issues were uncertain by this point, but in 1987 Andromeda managed to obtain copyright licensing for the IBM PC version and any other home computer system. By 1988, Pajitnov had created his own company for licensing purposes called Elektronorgtechnica, or simply "Elorg". By this time Elorg and Pajitnov had still seen no money from Andromeda, and yet Andromeda was licensing and sub-licensing rights that they themselves didn't even have.

By 1989, half a dozen different companies claimed rights to create and distribute the Tetris software, for the various arcade systems (such as Nintendo's Famicom, and the Game Boy hand-held system). Elorg, meanwhile, held that none of the companies were legally entitled to produce an arcade version, and promptly signed those rights over to Nintendo.

Tengen (part of Atari), regardless, applied for copyright for their Famicom version of Tetris and proceeded to market and distribute it under the name TETЯIS, blatantly disrespecting both Nintendo's and Elorg's rights to the name. After only a few (very popular) months on the shelf, the courts ruled that Nintendo had the rights to Tetris on arcade systems, and Tengen's TETЯIS game was recalled, having sold only about 50,000 copies. Nintendo released their version of Tetris for both the Famicom and the Game Boy and sold more than three million copies; most players considered Nintendo's Famicom/NES version inferior because it lacked the side-by-side simultaneous play of Tengen's version, but Nintendo's Game Boy Tetris became arguably the most well-known version of Tetris. The lawsuits between Tengen and Nintendo over the Famicom/NES version carried on until 1993.

Alexey Pajitnov himself made very little money from the deal, however, even though Nintendo was able to profit from the game handsomely.
In 1996, he and Henk Rogers[?] formed The Tetris Company LLC and Blue Planet Software in an effort to get royalties from the game, with good success on game consoles but very little on the PC front.
In 2001 (at time of writing) Tetris is a registered trademark of The Tetris Company LLC (hereinafter "TTC"). As of this writing, TTC has licensed the Tetris mark to only the following: Bullet-Proof Software, Inc.; Capcom Co., Ltd.; Ericsson Mobile Communication AB; Hasbro Interactive, Inc.; Jaleco Ltd.; Microsoft Corporation; Nintendo Co., Ltd.; Semi-Tech (Turku) Oy; Seta Corporation; Shockwave.com, Inc.; Pocket Express; Radica Games. Any other versions are unauthorized, but as of 2002, the legality of unauthorized clones has not been decided in court. TTC lists further licensing information on their web site's legal page at http://www.tetris.com/corporate/legal .

However, according to circulars available from the United States Library of Congress (available at http://www.loc.gov/copyright/circs/circ61.pdf and http://www.loc.gov/copyright/fls/fl108.pdf ), a game cannot be copyrighted (only patented), which refutes much of TTC's copyright claims on the game, leaving the trademark on "Tetris" as TTC's most significant claim on any government-granted monopoly. TTC no longer seems to pursue "clones" of the game under such names as Bedter[?] ( http://www.geocities.com/Hollywood/2430/bedter ), Quadra[?] ( http://quadra.sourceforge.net/ ), KSirtet[?] ( http://ksirtet.sourceforge.net/ ) and BinaryBlocks game[?] ( http://www.evilpigeon.net/pcsoftware/ ), that do not appear confusingly similar to "Tetris".

Wikipedia does not provide legal advice; only your attorney can provide that.

Is it possible to play forever?

Normally, the player loses because

• she can no longer keep up with the increasing speed, or
• a specific implementation of the game with not very responsive control fails to keep up with itself when the pieces' downward velocity exceeds the maximum sideways velocity the player can apply to a piece. (Avid players consider this situation a design flaw.)

But what if the speed didn't increase? Would it be possible to play forever? An article has been published that addresses this issue, and it turns out that in theory, you are doomed to lose eventually.
The problem is the S- and Z-shaped pieces. Suppose you got a large sequence of S-shaped pieces of the same orientation. Eventually, many implementations' approximation of gravity (see above) forces the player to leave a hole in a corner. Suppose you then get a large sequence of identical Z-shaped pieces. Eventually, you'll be forced to leave a hole in the opposite corner, without clearing your previous hole. Now, things go back to the original orientation for a while and so on until the pieces stack up to the top. Since the pieces are distributed randomly, this sequence will, eventually, occur. So, if you play long enough, and your random number source is theoretically perfect, you will lose the game.
(See also a more detailed discussion of this issue at http://www.geom.umn.edu/java/tetris/explanation , along with an implementation written in the Java programming language that has been modified to deal only S and Z pieces.)

Practically, this does not occur because the linear congruential pseudorandom number generator in most implementations does not deal such a sequence.

Even on an implementation with a theoretically perfect RNG (for example, based on hashing Brownian motion) and with naive gravity, a good player can survive over 150 consecutive pieces selected from the set {S, Z}; the probability at any given time of the next 150 pieces being only S and Z pieces equals one in (7/2)¹⁵⁰ (approximately one in 4 * 10⁸¹). This number has the same order of magnitude as the number of atoms in the known universe (source: http://pages.prodigy.net/jhonig/bignum/qauniver )

Several of the subproblems of Tetris have been stated to be NP-complete.

Tetris Variants

If you liked tetris, you might also like other puzzle games.

External links

• Tetris is Hard, Even to Approximate (http://arxiv.org/abs/cs.CC/0210020)