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

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.

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".

C64 BASIC version within a screen of code

[Neo-Rio-101]

It's a 15 liner.
Note that the {CBM-x} represents the graphic on that particular key (press the c= key and the letter to produce it)

1 a$="efijefijefijefijbfjnhijkbfjnhijkijfgaefjijfgaefjefjkiefbefjkiefbbfjidefj"
2 a$=a$+"abeieijkaeijijkgabfjiefgehijebfj@abe@dhe":o=207:dime(o):forx=0to111
3 print," {CBM-M}"," {CBM-G}":p=asc(mid$(a$,x+1)):e(x)=(pand3)+(pand12)*10:next:m=2024
4 print," {CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}{CBM-T}":gosub6:goto7
5 pokei+e(r),c:pokei+e(r+1),c:pokei+e(r+2),c:pokei+e(r+3),c:c=160:r$="d":return
6 i=1152:r=h:c=32:gosub5:j=int(rnd(0)*7)*16:r=j:gosub5:r=h:h=j:i=i+9:return
7 gosub6:w=i:t=i:g=r:k=240:l=1278
8 gosub15:c=32:gosub5:r=-r*b-g*notb:g=r
9 i=w:w=i+40:gosub5:gosub15:ifbthen12
10 getk$:g=randkor((r-4*(k$="s"))and15)
11 t=w:w=w+(k$=l$)-(k$=r$):l=l+40:goto8
12 c=o:gosub5:m=m-(l0:w=-t*b-w*notb:l$="a":return