Current Issue  Past Issues  Order Issues  Subscribe  Renew  Give a gift  Change Address  Customer Care  About Us Magazine Content   Feature Articles   Insights   Innovations   Technicalities   Reviews   Staking Claims   Skeptic   Anti Gravity   Sustainable    Developments   Forum   SA Perspectives   Letters   50, 100 & 150    Years Ago   News Scan   By the Numbers   Working Knowledge
October 20, 2007
SCIENCE NEWS
October 29, 2002

# Mathematicians Prove Tetris Is Tough

By Sarah Graham

 Image: NINTENDO OF AMERICA
The video game Tetris is one of the most popular computer games ever created, perhaps in part because its difficulty makes it addictive. The objective of the game is to move and rotate falling geometric shapes to form complete rows at the bottom of the game board. Now scientists have shown mathematically that the problem posed by Tetris's descending tetrominoes is one of the most difficult to solve, even if you know which pieces are coming next.

Erik D. Demaine, Susan Hohenberger and David Liben-Nowell of the Massachusetts Institute of Technology determined that Tetris qualifies as an NP-complete problem. That is, although it's relatively easy to check whether a solution to the problem is valid, there is no efficient way to optimize any of the game's objectives. These include maximizing the number of rows cleared, maximizing the number of pieces placed successfully before losing, maximizing the number of "tetrises" (clearing four rows simultaneously) and keeping the height of the grid as low as possible over the course of a game. And in the simulated games the team studied, the player knew all of the upcoming pieces ahead of time--a situation that should have been more straightforward than the real thing, in which randomly selected pieces fall quickly from the top of the screen.

The researchers further found that Tetris is an NP-hard problem, which means it is as least as difficult to solve as any other NP problem. "While you're playing Tetris, you're really solving hard problems," Demaine says. Interestingly, another seemingly simple but highly addictive game, Minesweeper, is also an NP-hard problem. So the next time you lose at either, take comfort in the fact that a computer may not have been able to do much better.

 MORE SCIENCE NEWS: News Bytes of the Week—Watson in Disgrace Chimpanzees are manipulative liars, Blood test for Alzheimer's and more…: Coal-Friendly Climate Changes in Kansas Cave Speak: Did Neandertals Talk? Wikipedia "Good Samaritans'' Are on the Money Election fix? Switzerland Tests Quantum Cryptography