Tetris Is Hard To Test

New submitter JackDW writes: Tetris is one of the best-known computer games ever made. It's easy to play but hard to master, and it's based on a NP-hard problem. But that's not all that's difficult about it. Though it's simple enough to be implemented in one line of BBC BASIC, it's complex enough to be really hard to thoroughly test.

It may seem like you can test everything in Tetris just by playing it for a few minutes, but this is very unlikely! As I explain in this article, the game is filled with special cases that rarely occur in normal play, and these can only be easily found with the help of a coverage tool.

Comments

One line?

[GrahamCox]

If anybody wrote code like that for me, they'd be made to sit on the naughty step and think very, very hard about what they'd done.

Re:One line?

[lgw]

Except that is not "one line". It is six lines. Any program can be a "one-liner" if there is no limit on the line length. Well, unless you writing it in Python.

The line length limit is 256 bytes, of course. And these hacks are the basic-equivalent of the C obfuscation contest.

As the authors say: "I'd like to think it is self documenting. The code speaks for itself; even if what it has to say is not very nice."

Re:One line?

[BlackHawk-666]

In ASCII, but many BASICs will reduce keywords down to a single byte.

in Soviet Russia

[Trepidity]

It may seem like you can test everything in Tetris just by playing it for a few minutes, but this is very unlikely! As I explain in this article, the game is filled with special cases that rarely occur in normal play, and these can only be easily found with the help of a coverage tool.

Tetris doesn't need coverage tool to test you. Everything about you.

Code-coverage tool is crutch for weak capitalist engineer. Tetris is Soviet technology, forged by people's will.

Nice advertisement

[Anonymous Coward]

From a company promoting automated WCET analysis. Hah!

Re:Nice advertisement

[phantomfive]

Normal users don't test all cases of a game.

Maybe not, but as soon as you tell yourself, "I don't need to test this code, a normal user will never get to it;" you can be certain that after saying that, a user will find a way to break it. The Gods of Eternity will laugh at you.

replacing line feeds with terminators is not a 1-l

[raymorris]

In BBC BASIC, a colon is a statement terminator, much like a semicolon in languages with C-style syntax. The linked code is therefore not a one-liner by any meaningful definition of the term. One could replace all of the linefeeds in Linux kernel source with semicolons and other appropriate terminators. That wouldn't make the kernel a one-liner.

perhaps. I wonder if it NP-hard

[raymorris]

The fact that probability is involved doesn't mean there's not an optimal strategy, of course, where optimal is defined as "highest expected score" (score X probability). So figuring out an optimal strategy is a hard problem - how hard is it?

If the probability of a certain series of shapes coming next were 100%, we'd have an NP-hard problem, agreed? Does another probability make it easier or harder? Harder, if anything. That's provable because the probability version can be solved by solving each of the potential series as if each were known. What's harder than NP-hard? It may well still be NP-hard. It can't be of any more solvable complexity class.

Re:perhaps. I wonder if it NP-hard

[phantomfive]

What's harder than NP-hard?

Intractable.

Infomercial for a code coverage tool?

[140Mandak262Jamuna]

Code coverage tool seems like a good idea from some theoretical stand point. But in practice number of code paths multiply rapidly and getting all the paths executed would involve unreasonably long time. Further rarely called procedures or rarely executed is just one class of problems. There are functions that will execute million times correctly and misbehave once in a million or once in a billion calls. For example I came across a bug in something so simple like calculating the centroid of a triangle. Absurdly simply code that adds the x, y, z coordinates of the vertices and divides by 3. That is all. In dealing with output of some CAD software, when the smallest angle of the triangle fell below 1.0e-08 radians, it returned a wrong value of the centroid. Typical sanity checks based on mathematical facts, like centroid of a triangle can never be outside the triangle will not work. The code that checks inside-or-outside of triangle is far more complex than the centroid code. The floating point truncation errors make this kind of sanity check useless. You can't even plot it on the screen and look at the centroid. OpenGL is implemented in single precision.

So at some point you reach a point of diminishing returns. It might not be worth making sure every line got tested when there are procedures that have a bug that happens in one in a billion calls. My philosophy is, "Perfection is the goal. Doing better than the last release is the shipping criterion".

Nonsense -- make your own test suite

[rs1n]

Why would you only test your code via normal use? Why wouldn't you just create a test suite that actually tests all the scenarios? In the case of tetris, you can simply force a sequence of pieces that will enable you to reach the scenarios described in the article. Or you can even start the game with a pre-made board.

Has slashdot really become a means for tech companies to inject free advertisement by a simple blog post made to look like real journalism?