CATEGORIES TV RADIO COMMUNICATE WHERE I LIVE INDEX SEARCH
You are in: Technology
 News Front Page World UK England N Ireland Scotland Wales Politics Business Entertainment Science/Nature Technology Health Education ------------- Talking Point ------------- Country Profiles In Depth ------------- Programmes -------------
 SERVICES Daily E-mail News Ticker Mobile/PDAs -------------
 Feedback Help
 EDITIONS Change to World
Saturday, 26 October, 2002, 08:46 GMT 09:46 UK
The trouble with Tetris
 Tetris: very tricky
Everyone knows that Tetris is compulsively playable, but now scientists have proved that it is harder than you think to complete.

The game was invented in 1985 by Russian Alexey Pajitnov and has since become one of the most widely played games of all time.

Now US computer scientists have analysed it and found it has a lot in common with the hardest problems in mathematics.

These problems are immune to simple solutions and instead demand exhaustive analysis to work out the best way to complete them.

Knotty blocks

Anyone who has played computer games over the last 15 years is likely to have encountered Tetris in one form or another. Many people first played it on the Nintendo Gameboy handheld console.

The game gives the player the task of creating complete lines with the regularly-shaped series of blocks that advance steadily down a narrow grid.

The blocks can be spun to make them fit together better and complete lines. The game gets faster as levels are completed making it harder to spin and fit blocks together fast enough to form lines.

Now Erik Demaine, Susan Hohenberger and David Liben-Nowell from the Laboratory of Computer Science at the Massachusetts Institute of Technology have analysed the game to determine its computational complexity.

The trio discovered that, subject to certain conditions, Tetris has much in common with some of the knottiest mathematical conundrums such as the Travelling Salesman Problem.

No quick fix

This problem involves working out the most efficient route for a salesman or delivery man who has to visit lots of different locations.

These types of problems, known as NP-Hard problems, are difficult because there is no shortcut or smart algorithm that will solve them swiftly.

Instead, all possible solutions have to be tried to find out which produces the best result.

The researchers found that Tetris was an NP-Hard problem, i.e. there was no easy way to maximise a score at the game, even when the sequence of blocks was known in advance.

19 Apr 00 | Science/Nature
16 Oct 00 | Health
25 Dec 01 | Science/Nature
11 Jul 00 | Science/Nature
13 Jun 02 | Science/Nature
09 Sep 02 | dot life
20 May 02 | Science/Nature