Tetris
Colin Fahey
1. Software
StandardTetris_2007June4.zip
Tetris source code (C# and C++ versions) and program ("exe");
4068277 bytes
MD5: 4e957e0ead66064183e9f7e04e618ec0
2. Introduction
This article describes how a computer can play the classic video game Tetris by getting information about the board, determining good actions, and performing those actions.
This article includes software capable of playing Tetris in real time.
The software includes the best real-time Tetris-playing algorithm in the public domain.
This article defines rules for "Standard Tetris", a specification based on the original 1986 pre-commercial version of Tetris for the Personal Computer (PC).
In 2003, the software included in this article was used to enable a computer to play Tetris running on a separate computer.
An ordinary USB video camera was used to enable the computer to "see" the screen of the other computer.
A relay board was controlled via an RS-232 interface to enable the computer to "press keys" on the keyboard of the other computer.
Thus, the first computer has a relationship to the second computer that is similar to a typical human player's relationship to a computer when playing Tetris; the game state is only known by looking at the screen, and player actions can only be initiated through a keyboard.
The configuration in this demonstration established that a computer can play Tetris better than a human, under normal real-time Tetris playing conditions.
3. History of Tetris
In 1985, Alexey Pajitnov and Dmitry Pavlovsky were computer engineers at the Computing Center of the Russian Academy of Sciences.
Dorodnicyn Computing Centre of the Russian Academy of Sciences
Alexey and Dmitry were interested in developing and selling addictive computer games.
They tested out several different games.
Alexey was inspired by the ancient Greek puzzle game, Pentaminos, which involved arranging puzzle pieces made of five squares.
Alexey thought of the idea of arranging Pentamino pieces as they fell in to a rectangular cup, but realized that the twelve different five-square shapes were too complex for a video game.
Alexey switched to using seven "tetramino" pieces, each made of four squares.
In 1985.6, Alexey Pajitnov programmed the first version of Tetris on an Electronica 60.
Dmitry Pavlovsky, Alexey Pajitnov, and Tetris.
In 1985-1986, Vadim Gerasimov, a 16-year old high-school computer prodigy who worked at the academy, implemented Tetris for the IBM PC running the MS-DOS operating system.
( Vadim Gerasimov later did research at the MIT Media Laboratory, from 1994 through 2003, receiving a Ph.D. after completing many interesting projects:
http://vadim.www.media.mit.edu )
The introduction screen of the 1987-1988 pre-commercial release of Tetris for the PC
The game play screen of the 1987-1988 pre-commercial release of Tetris for the PC
After 1987, Tetris spread around the globe.
The Tetris Company, LLC, owns the Tetris trademark.
4. Projects inspired by Tetris
4.1 0-dimensional Tetris
Not yet developed.
4.2 1-dimensional Tetris
Ziga Hajdukovic has developed 1-dimensional Tetris software that can be played in a Internet browser.
Ziga Hajdukovic has also developed 1-dimensional Tetris software for mobile phones using the Java J2ME platform.
4.3 2-dimensional Tetris
All conventional Tetris variants are in this category.
This section includes interesting variants.
4.3.1 Largest Tetris game ever : Delft University of Technology (1995)
Tetris played on a building; 2000 m^2 surface area; Delft University of Technology (1995)
Tetris played on a building; 2000 m^2 surface area; Delft University of Technology (1995)
4.3.2 Another Tetris game played on a building : Brown University (2000)
Tetris game displayed using lights in the windows of a building at Brown University (2000.4-200.5) http://bastilleweb.techhouse.org
"I think it was just the most incredible one-day thing I could imagine in my life. Like Steve Jobs always said, the journey is the reward."
"It made me think of projects we did back in college. Things that were almost undoable that other people wouldn't think of doing."
Steve Wozniak (2000)
4.3.3 Internet browser game with MIT "Green Building" image
Vadim Gerisimov's Internet browser Tetris
This Internet browser Tetris variant was created by Vadim Gerasimov.
This Internet browser Tetris features the "Green" building at the campus of MIT.
This Tetris variant only has nine columns instead of the standard ten columns.
This Tetris variant presents new pieces with random orientations.
Vadim Gerasimov is the person who wrote the computer code for the PC version of Tetris in 1986.
Vadim Gerasimov did Ph.D. research at the MIT Media Laboratory during 1994-2003, working on many interesting projects.
4.3.4 PIC16F84 12 MHz microcontroller-based NTSC / PAL video Tetris game
PIC16F84 12 MHz microcontroller-based NTSC / PAL video Tetris game
The image above shows the NTSC / PAL video output produced by a PIC16F84 12 MHz microcontroller running software written by Rickard Gunee in 1998.
The video signal is generated by software control of digital outputs.
4.3.5 "Scopetris" Oscilloscope Tetris by Lars Pontoppidan (2007.8)
"Scopetris" Oscilloscope Tetris by Lars Pontoppidan (2007.8)
Lars Pontoppidan wrote code for the AtMega32 microcontroller, and added simple analog circuitry, to create a Tetris version that could be played on an oscilloscope.
Certain registers of the AtMega32 microcontroller control 8-bit output signals, and, when passed through an "R-2R" electrical resistor circuit for digital-to-analog (D/A) conversion, the resulting analog signals can control the (x,y) coordinates of an oscilloscope beam (when the oscilloscope is set to "X-Y mode").
YouTube video:
FLV video:
4.3.6 Obfuscated code Tetris : C / Unix
The following was awarded "1989 IOCCC Best Game".
long h[4];t(){h[3]-=h[3]/3000;setitimer(0,h,0);}c,d,l,v[]={(int)t,0,2},w,s,I,K
=0,i=276,j,k,q[276],Q[276],*n=q,*m,x=17,f[]={7,-13,-12,1,8,-11,-12,-1,9,-1,1,
12,3,-13,-12,-1,12,-1,11,1,15,-1,13,1,18,-1,1,2,0,-12,-1,11,1,-12,1,13,10,-12,
1,12,11,-12,-1,1,2,-12,-1,12,13,-12,12,13,14,-11,-1,1,4,-13,-12,12,16,-11,-12,
12,17,-13,1,-1,5,-12,12,11,6,-12,12,24};u(){for(i=11;++i<264;)if((k=q[i])-Q[i]
){Q[i]=k;if(i-++I¦¦i%12<1)printf("\033[%d;%dH",(I=i)/12,i%12*2+28);printf(
"\033[%dm "+(K-k?0:5),k);K=k;}Q[263]=c=getchar();}G(b){for(i=4;i--;)if(q[i?b+
n[i]:b])return 0;return 1;}g(b){for(i=4;i--;q[i?x+n[i]:x]=b);}main(C,V,a)char*
*V,*a;{h[3]=1000000/(l=C>1?atoi(V[1]):2);for(a=C>2?V[2]:"jkl pq";i;i--)*n++=i<
25¦¦i%12<2?7:0;srand(getpid());system("stty cbreak -echo stop u");sigvec(14,v,
0);t();puts("\033[H\033[J");for(n=f+rand()%7*4;;g(7),u(),g(0)){if(c<0){if(G(x+
12))x+=12;else{g(7);++w;for(j=0;j<252;j=12*(j/12+1))for(;q[++j];)if(j%12==10){
for(;j%12;q[j--]=0);u();for(;--j;q[j+12]=q[j]);u();}n=f+rand()%7*4;G(x=17)¦¦(c
=a[5]);}}if(c==*a)G(--x)¦¦++x;if(c==a[1])n=f+4**(m=n),G(x)¦¦(n=m);if(c==a[2])G
(++x)¦¦--x;if(c==a[3])for(;G(x+12);++w)x+=12;if(c==a[4]¦¦c==a[5]){s=sigblock(
8192);printf("\033[H\033[J\033[0m%d\n",w);if(c==a[5])break;for(j=264;j--;Q[j]=
0);while(getchar()-a[4]);puts("\033[H\033[J\033[7m");sigsetmask(s);}}d=popen(
"stty -cbreak echo stop \023;sort -mnr -o HI - HI;cat HI","w");fprintf(d,
"%4d from level %1d by %s\n",w,l,getlogin());pclose(d);}
4.3.7 Obfuscated code Tetris : Perl code
The following is Tetris for the Perl interpreter: Perltris (version 20050717) by Sean Adams.
#!/usr/bin/perl
$_='A=15; B=30; select(stdin); $¦=1; select(stdout);$¦=1; system
"stty -echo -icanon eol \001"; for C(split(/\s/,"010.010.010.010
77.77 022.020.020 330.030.030 440.044.000 055.550.000 666.060.".
"000")){D=0;for E(split(/\./,C)){F=0;for G(split("",E)){C[P][F++
][D]=G} D++}J[P]=F; I[P++] =D}%L=split(/ /,"m _".chr(72)." c 2".
chr(74)." a _m");sub a{for K(split(/ /,shift)){(K,L)=split(/=/,K
);K=L{K};K=~s/_/L/; printf "%c[K",27}}sub u{a("a=40");for D(0..B
-1){for F(0..A-1){M=G[F][D];if(R[F][D]!=M) {R[F][D]=M;a("m"."=".
(5+D).";".(F*2+5)); a("a=".(40+M).";" .(30+M));print " "x2}}}a(
"m=0;0 a=37;40")}sub r{(N)=@_;while(N--) {Q=W;W=O=H;H=Q;for F( 0
..Q-1){for D(0..O-1) {Q[F][D]=K[F][D]}}for F(0..O-1){for D(0..Q-
1){K[F][D]= Q[Q-D-1][F]}}}}sub l{for F(0..W-1){for D(0..H-1){(K[
F][D]&& ((G[X+F][Y+D])¦¦ (X+F<0)¦¦(X+F>=A)¦¦ (Y+D>=B)))&& return
0}}1}sub p{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[X+F][Y+D]
=K[F][D]) }}1}sub o{for F(0..W-1){for D(0..H-1){(K[F][D]>0)&&(G[
X+F][ Y+D]=0)}}}sub n{C=int(rand(P)) ;W=J[C];H=I[C];X=int(A/2)-1
;Y=0;for F(0..W-1){for D(0..H-1){K[F][D]= C[C][F][D]}}r(int(rand
(4)));l&&p}sub c{d:for(D=B;D>=0;D--){for F(0..A-1){G[F][D]¦¦next
d}for(D2=D;D2>=0; D2--){for F(0..A-1){G[F][D2]= (D2>1)?G[F][D2-1
]:0; }}u;}}a ("m=0;0 a=0;37;40 c");print "\n\n".4x" "." "x(A-4).
"perltris\n".(" "x4)."--"xA."\n".((" "x3)."¦"." "x(A*2)."¦\n")xB
.(" "x4). "--"xA."\n";n;for(;;) {u;R=chr(1); (S,T)=select(R,U,V,
0.01);if(S) {Z=getc;}else {if($e++>20){Z=" ";$e=0;}else{next;} }
if(Z eq "k"){o;r(1);l¦¦r(3);p}; if(Z eq "j"){o;X--;l¦¦X++;p}; if
(Z eq "l"){o;X++;l¦¦X--;p};if(Z eq " "){o;Y++;(E=l)¦¦Y--;p;E¦¦ c
¦c¦c¦c¦c¦n¦¦goto g;};if(Z eq "q"){last;}}g: a("a=0 m=".(B+8).";0
" ); system "stty sane"; '; s/([A-Z])/\$$1/g; s/\%\$/\%/g; eval;
4.3.8 Mozilla SVG Tetris
Scalable Vector Graphics (SVG) is a standard for describing graphical objects using XML.
Mozilla SVG Tetris : Tetris implemented using a Scalable Vector Graphics (SVG) description
4.3.9 Google "widget" Tetris
Google, Yahoo!, and Microsoft, and other companies, have promoted miniature Internet-based software named "widgets" that are usually characterized by some use of dynamic data available on the Internet.
One such widget available through Google is a Tetris game.
The following example is cute, but the shapes rotate in annoying ways:
Google "widget" Tetris
Other Google widgets:
4.3.10 MIT research paper: "Tetris is Hard, Even to Approximate" (2002)
The following research document contains a proof that a certain kind of Tetris variant is "NP-complete".
Erik D. Demaine, Susan Hohenberger, and David Liben-Nowell, "Tetris is Hard, Even to Approximate", Technical Report MIT-LCS-TR-865, Massachusetts Institute of Technology, 2002.10.21.
"NP-complete" is a classification of the time cost and space cost of an algorithm.
Other classifications include "P" and "NP".
A classification of "NP-complete" implies that, for problems larger than some small size, the algorithm is unlikely to find a desired solution in a practical amount of time or space.
4.3.11 Research document: "Applying reinforcement learning to Tetris"
The following paper, published 2005.5.30, by Donald Carr at the Computer Science department at Rhodes University, South Africa, presents the application of "reinforcement learning" to Tetris.
4.3.12 Tetris Skirt (2007.11)
Tetris Skirt (2007.11)
The Tetris skirt was created by "Lucy" ("hissyfitoly" on etsy.com) before 2007.11.
From the creator's description of the skirt (offered for sale on etsy.com):
"Okay, so I was a secret, closet Tetris fanatic from about, oh, 1993 to 1996. It was a bitter-sweet obsession. My life wasn't so great, but I could control the stacking of a few measly blocks, [damn it]! Or could I? Video games have been coming back to haunt my dreams as of late, and I find myself stacking blocks, jumping away from a frighteningly-large Q*Bert, and slipping off of logs next to a pixellated frog. This skirt is the result of those nightmares."
Forum comments regarding this skirt:
"Man that skirt sucks at Tetris"
"Ahahahaha, I thought the same thing."
"There's a complete line down at the bottom...completed lines disappear. DO OVER."
"There should be a spot in the back or front where "long" piece would fit perfectly..."
"That's a really ugly skirt though. My boyfriend couldn't buy me enough chocolate and flowers to convince me to wear that thing."
4.3.13 Tetris stage act (2007.4)
Tetris stage act (2007.4)
"From those that brought you the Triforce in 2006... Comes the next generation of inanimate object skit... Tetris."
Locally-cached video in Flash video (FLV) format (use VLC to play):
4.3.14 Hilarious Tetris variations on a Japanese television show
Tetris variations on Japanese television show
This video segment from a Japanese television show includes hilarious variations of Tetris, including:
pieces that vanish upon landing, a piece that fills an entire row (thus completing a row upon landing), multiple pieces falling simultaneously, irregularly shaped pieces, a long piece that is slightly too wide to fit in a gap (preventing a 4-row completion!), Mario hitting a mushroom and becoming enormous and dying!, small piece debris remaining after rows are destroyed, upward gravity making pieces float to the top, etc.
Locally-cached video in Flash video (FLV) format (use VLC to play):
4.3.15 "The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
"The Original Human TETRIS Performance by Guillaume Reymond" (2007.11)
From the description on YouTube:
"Tetris played by real human-beings sitting in an auditorium:
Tetris is the 4th video performance of the GAME OVER Project, directed by the Swiss artist Guillaume REYMOND (NOTsoNOISY creative agency).
This stop-motion video was shot and played for "LES URBAINES" festival
http://www.urbaines.ch at the Palais de Rumine (Lausanne, Switzerland) on November 24th 2007.
Locally-cached video in Flash video (FLV) format (use VLC to play):
4.3.16 2.5-dimensional Tetris
The term "2.5-dimensional" is used here to mean a non-orthogonal view of a two-dimensional version of Tetris, with some thickness in the third dimension.
(Find the link "tetris3d" in "F7: GAMES".)
4.4 3-dimensional Tetris
Linux / GTK version
Three-dimensional Tetris in the form of a Java applet for Internet browsers:
Three-dimensional Tetris for the Windows operating system:
4.5 4-dimensional Tetris
Greg Kaiser's "HyperTetris" (1996) : a 4-dimensional Tetris
In [1996], [...], Greg Kaiser put together a four-dimensional variant on the classic game.
Using IrisGL (a.k.a. igl) he created a working, if hard to play, game using four sub-screens to depict different three-dimensional aspects of the entire game-space.
[Because] there is not an easily [comprehensible] way to draw four-D objects on a two-D screen, the four sub-views are a practical method to manipulate and visualize the rotation and translation of the pieces through the four dimensions (in the game called x,y,z,w).
Rather than completing lines of blocks as in the original, the goal in this case is to fill a complete cube in the x,y,z subview (usually 4 by 4 by 4).
The other subviews which contain the "w" dimension are arranged in a default 4 by 4 by 10 block arrangement with "w" being the long, "vertical" dimension in all three cases, with different bases of (x,y), (x,z), (y,z).
Gravity acts in the "-w" direction, so pieces fall "down" in the three long subviews that include "w", and do not move unless by player control in the last (x,y,z) subview.
It takes awhile to get used to, to say the least.
If by some miracle of patience or changing the parameters of the game, one does complete a cube, it will disappear as the completed lines do in the original Tetris, though no score is kept in HyperTetris.
Benjamin Bernard (2000)
4.6 N-dimensional Tetris
Polytope Tetris (2003) : an N-dimensional Tetris game variant
Polytope Tetris is n-dimensionally Tetris.
Inspired by the HyperTetris program, Polytope Tetris allows you tons play Tetris in any NUMBER OF dimension.
Play Tetris in 3D, 4D, 5D, or more.
HyperTetris is A much catchier name than Polytope (def) Tetris, but I can't steal the name.
5. "Standard Tetris" specification
5.1 Introduction
The definition of "Standard Tetris" is an idealized model of the most important characteristics and behaviors of the first IBM-PC implementation of the Tetris game (circa 1986-1988).
The idealized model is based upon inferring the apparent intentions of the developers of the first IBM-PC implementation of the Tetris game.
For example, it seems reasonable to infer that the developers of the first IBM-PC implementation of the Tetris game intended to select the shape of each new falling piece "randomly", and that the use of the Borland C implementation of the rand() function was merely a practical approximation of the intention.
The definition of "Standard Tetris" specifies that the shape of each new falling piece is to be selected "randomly".
This ideal behavior cannot be achieved by any implementation, but implementations can approximate the ideal behavior.
Although no implementation can perfectly implement the definition of "Standard Tetris", the ideals of "Standard Tetris" involve objective characteristics, and implementations can be compared according to their relative closeness to the ideals of "Standard Tetris".
This section describes a set of elements, behaviors, and rules, which, collectively, define "Standard Tetris".
5.2 Standard Tetris board
The board is a grid of cells, having 10 columns, and 20 rows, for a total of 10 * 20 = 200 cells.
Standard Tetris board (10 columns, 20 rows)
Each cell can either be unoccupied (empty) or occupied (full).
5.3 Standard Tetris pieces
There are seven (7) standard Tetris pieces, with the following letter names:
{ O, I, S, Z, L, J, T }
The letter names are inspired by the shapes of the pieces.
The seven Standard Tetris pieces and their "orientations"
The dot at (0,0) coincides with board position (6,20) when the piece first appears.
The first column shows the initial "orientations".
In the following, the word "orientation" is used to describe any state of a piece, within a set of allowed states, that can result from a counterclockwise rotation event.
Changing "orientation" from a specified "orientation" of an "I", "S", or "Z" piece, requires the combination of a rotation and a translation.
Therefore, the word "orientation" is used here to mean something more than rotation alone.
However, "orientation" can change only in response to a counterclockwise rotation event, and the cycle of distinct "orientations" for each piece approximates, or matches, the cycle resulting from pure rotations.
The special use of the word "orientation" in this context is nearly equivalent to the meaning of the word "rotation" or "angle", but the word "orientation" is used instead of "rotation" to attempt to bring attention to the fact that some pieces require more than rotation to produce the set of allowed states resulting from counterclockwise "rotation" events.
Pieces can only switch orientations (or undergo a specific horizontal or vertical translation) if the resulting state of the piece would not have any occupied (full) cells beyond the area of the board and would not have any occupied cells which overlap any currently occupied cells of the board.
(In this rule, the occupied (full) cells of the piece are not considered as part of the "currently occupied cells of the board"
In the following comments, any reference to a result of a counterclockwise rotation event is made with the assumption that such a rotation can actually be performed, given the existing conditions of the piece and the board.
The "O" (box) piece only has a single orientation, and does not change the locations of any of its occupied (full) cells in response to any counterclockwise rotation event.
The "I" (line) piece has two possible orientations, initially appearing in a horizontal orientation.
The "I" piece alternates between the two orientations in response to successive counterclockwise rotation events.
The "S" and "Z" pieces each have two possible orientations.
These pieces each alternate between two orientations in response to successive counterclockwise rotation events.
The "L", "J", and "T" pieces each have four possible orientations, and these orientations are the results of simple rotations about center points on the shapes.
When a piece first appears on the board, the piece has its "major axis" in a horizontal orientation, and the piece is at the top of the board.
Therefore, no pieces are initially capable of having their orientations changed. The piece must descend by one row to have the possibility of having its orientation changed.
Once a piece has fallen by one row on the board, all piece orientations can be attained (assuming the piece is not too close to the side walls or to the current pile of pieces).
5.4 Standard Tetris flowchart
The following is an approximate flowchart for a Standard Tetris game.
Approximate flowchart for a Standard Tetris game
Approximate flowchart for a Standard Tetris game
5.5 Standard Tetris piece creation
The following diagram shows the (4 cell * 2 cell) region on the board where all pieces appear when created.
Region where pieces appear when created in Standard Tetris
When a new piece first appears on the board, its origin coincides with the dot on this diagram, and the piece will be completely contained by the shaded area on this diagram.
When a new game is started, a full free-fall delay elapses, and on the first free-fall iteration a piece is spawned at the top of the board.
During normal game play, when a specific free-fall iteration "lands" a piece, a full free-fall delay elapses and on the next free-fall iteration a piece is spawned at the top of the board.
When a piece is spawned, the type of piece is selected using the following algorithm:
pieceIndex = 1 + (randomInteger % 7); // 1..7
Because there is a constant p (= 1/7) chance of selecting a specific kind of piece, and all pieces of the same type are indistinguishable, the probability of having exactly k pieces of a specific type after n trials follows a Binomial distribution:
P(k) = (1-p)^(n-k) * p^k * ( n! / ( (n-k)! k! ) );
p = 0.0 ... 1.0;
k = 0, 1, 2, ..., n;
mean = ( n * p )
variance = ( n * p *(1-p) )
standard deviation = sqrt( variance )
When we choose from among the 7 (seven) pieces at random, the probability of getting a specific piece is p=(1/7).
If we do this n=70 times, for example, the probability of getting exactly k pieces (with k in the range 0 to n) is given by the binomial distribution, as shown in the following image.
Binomial distribution for n=70, p=(1/7)
Thus, one can predict the average total pieces of a single type given a total number of random pieces, and one can also compute the expected variance and standard deviation (square root of variance):
p = (1/7):
total random standard
pieces (n) mean variance deviation
============ ======= ======== =========
70 10 8 3
700 100 85 9
7000 1000 857 29
70000 10000 8571 93
When we convert a random value to a piece index, we interpret it as follows:
value piece
===== =====
1 "O"
2 "I"
3 "S"
4 "Z"
5 "L"
6 "J"
7 "T"
[ The pre-commercial MS-DOS version of Tetris used the random number function offered by the Borland Pascal compiler.
That function used a 32-bit state variable.
Therefore, the sequence of random numbers was limited to 2^32 distinct values.
Therefore, in principle, a player could discover, after dropping perhaps 10 pieces, the exact place in the set of 2^32 numbers corresponding to the current state of the game.
If Tetris simulations are executed with the fixed sequence of 2^32 pieces, then optimal decisions can be found for every place in the sequence.
(There seem to be sufficient opportunities to being the board to a totally empty board state, allowing us to get synchronized with the precomputed optimal solution path.)
The risk of using a simple random number generator in a simulation intended to find an optimal solution to a problem is that the solution will be optimal only for the particular path through the problem space selected by the simple random number generator. ]
5.6 Standard Tetris controls
During game play, the following inputs are available:
left : request to translate left by one column
right : request to translate right by one column
rotate : request to do a counterclockwise rotation
drop : request to instantly drop the piece
All inputs take effect on the rising-edge of the positive input (on button press, as opposed to button release).
When a button press occurs, this counts as a request.
Holding a button down beyond a certain time might result in the "auto-repeat" feature of a keyboard, generating new button presses -- but this feature is external to the game engine.
The inputs specified above conform to the original Tetris game.
Rotate requests can be executed if there is no overlap between the desired orientation and set cells on the current board (excluding the falling piece), and if the desired orientation has no set cells outside the board area.
Translate requests can be executed if there is no overlap between the desired translated configuration and set cells on the current board (excluding the falling piece), and if the desired translated configuration has no set cells outside the board area.
Input requests are processed with a latency that depends on the frame rate of the game (example: 75 Hz), and requests take effect (if valid) instantly.
A piece can be dropped without any line falling steps occurring.
A piece can be translated several times to the left or right, and subsequently dropped, all without experiencing an official line falling step.
Because a newly spawned piece cannot possibly be rotated (because it is stuck against the top edge of the board), the player must accept at least one piece falling step if rotations are desired or required.
The effect on the score is insignificant.
5.7 Standard Tetris piece "landing"
If a piece is simply falling, it falls by a single row during each piece falling iteration.
There will be an iteration that moves it from a place with no contact with horizontal surfaces to a place that has contact with horizontal surfaces. Once this iterations occurs, the pieces are in resting contact.
If an iteration begins with a piece in resting contact with a horizontal surface, the piece "lands", and becomes part of the static pile.
5.8 Standard Tetris "lines completed"
A completed row is a row of the pile in which all cells are occupied. When a completed row is eliminated from the pile, and the rows above the eliminated row are shifted down by one row to eliminate the gap, this counts as a completed "line".
When a piece lands it becomes part of the pile.
Immediately after the piece lands, the pile is checked for completed rows, and all completed rows are eliminated.
Up to four rows can be completed simultaneously.
The following table gives the upper limit on lines completed simultaneously by a single piece:
piece max. simultaneous
rows completed
===== ==================
"O" 2
"I" 4
"S" 2
"Z" 2
"L" 3
"J" 3
"T" 2
5.9 Standard Tetris "levels"
Standard Tetris has 10 difficulty levels, numbered 1 (one) through 10 (ten), with level 1 being the "least difficult".
The level index is the maximum of two values:
actualLevel = max( initialLevel, earnedLevel );
The initialLevel value is the level that the player selects when starting a new game.
The pattern of level as a function of completed lines is easily observed in the pre-commercial MS-DOS version of Tetris:
{ 0, 1, 2, ..., 10 } --> earned level 1
{ 11, 12, ..., 20 } --> earned level 2
{ 21, 22, ..., 30 } --> earned level 3
{ 31, 32, ..., 40 } --> earned level 4
{ 41, 42, ..., 50 } --> earned level 5
{ 51, 52, ..., 60 } --> earned level 6
{ 61, 62, ..., 70 } --> earned level 7
{ 71, 72, ..., 80 } --> earned level 8
{ 81, 82, ..., 90 } --> earned level 9
{ 91, ... } --> earned level 10
Thus, the earnedLevel value is computed according to the following algorithm:
if (linesCompleted <= 0)
{
earnedLevel = 1;
}
else if ((linesCompleted >= 1) && (linesCompleted <= 90))
{
earnedLevel = 1 + ((linesCompleted - 1) / 10);
}
else if (linesCompleted >= 91)
{
earnedLevel = 10;
}
5.10 Standard Tetris falling iteration delay
Standard Tetris has a real-time delay between successive line free-fall iterations that is a function of the current difficulty level.
The following relationship between level index and falling iteration delay is based on repeated stopwatch measurements at all levels of the pre-commercial MS-DOS version of Tetris.
actualLevel iterationDelay [seconds]
(rounded to nearest 0.05)
============ =========================
1 0.50
2 0.45
3 0.40
4 0.35
5 0.30
6 0.25
7 0.20
8 0.15
9 0.10
10 0.05
Thus, we establish the following formula for the iteration delay value as a function of the actual level index:
iterationDelay = ((11 - actualLevel) * 0.05); // [seconds]
If the board is empty, and there is no user input, a spawned piece at actual level 1 lands in approximately 10 seconds, and a spawned piece at actual level 10 lands in approximately 1 second.
5.11 Standard Tetris "score"
Standard Tetris only awards points for the act of landing a piece.
There are no points awarded for the act of completing a single line, or completing two, three, or four lines simultaneously.
[ Note: Some variants of Tetris award points for the act of completing lines, with an exponentially increasing bonus for an increasing number of simultaneously completed lines.
Thus, the strategy for maximizing score in such variants of Tetris involves setting up opportunities to "get a Tetris", slang for using the "I" shape to get four simultaneous lines and getting lots of points. ]
If you have an empty board, and you let a non-"I" piece do a free-fall and land, or you immediately drop a non-"I" piece, you can establish the following point chart using the pre-commercial MS-DOS version of Tetris:
actualLevel free-fall instant-drop
points points
=========== ========= ============
1 6 24
2 9 27
3 12 30
4 15 33
5 18 36
6 21 39
7 24 42
8 27 45
9 30 48
10 33 51
Unrotated, non-"I" pieces fall a total of 18 rows.
This accounts for the point difference between the free-fall and instant-drop cases.
By experimenting with intermediate cases it is easy to infer the following point formula:
pointAward = ( (21 + (3 * actualLevel)) - freeFallIterations );
Note that this formula has nothing to do with the distance a piece falls!
It is strictly a function of the actual level, and a penalty for the number of iterations a piece is allowed to fall freely.
This punishes a user for needing time to think.
Also note that because a piece cannot initially be rotated when it first spawns, a player is punished by at least one free-fall iteration if rotations are required to place a piece in the pile.
This probably never affects human players, unless they somehow: recognize the piece, press translation keys ("left" or "right"), press the "rotate" key one or more times, and press the "drop" key, all within less than 0.5 seconds at level 1, or less than 0.05 seconds at level 10.
6. Standard Tetris strategy
6.1 Introduction
A strategy for playing a game depends on the rules of the game.
A strategy depends on which parameter is to be optimized.
In Standard Tetris, one survives by completing rows, gets points for landing pieces, and scores the most points possible for each piece by executing a drop before one or more free-fall iterations transpire.
An A.I. can optimize the points awarded for each piece simply by deciding on a move quickly and "pressing the keys" to execute the move.
More important to an A.I. is survival, because indefinite survival means an arbitrarily high score can be attained. Because the Tetris pieces fall at a specific rate, the A.I. must make decisions at least this fast -- and the A.I. must make moves that complete rows at a rate that averages at least 1 row per 2.5 pieces. (Each piece has 4 cells, and each row has 10 cells.)
Of course one can postpone completing rows by accumulating pieces and building a large pile, but there are only 200 cells on the entire board, which in principle can only hold 50 pieces, so any player (such as an A.I.) must have completing lines as a fundamental priority.
In Standard Tetris, the game state includes the current board occupation and the current falling piece (type, position, and orientation). The game state may optionally i
