This Emacs Lisp Tetris code is now available at: http://home.pipeline.com/~hbaker1/emacs/tetris.el ----- At 03:06 PM 6/20/03 -0700, Henry Baker wrote:
I have become intrigued by Tetris, not as a game, but as an online packing problem. I'm not interested in the optimum solution, per se, but in the statistics of the problem.
Normally, Tetris has 10 columns and 7 tetraminos -- 2x2 "block", 2 "L"'s (L, L', mirror images), 2 "Z"'s (Z, Z', mirror images), 1 "T", and a 4x1 "line". Each tetramino has an area of 4 units. These tetraminos show up randomly, but with a uniform distribution -- the 7 different types are equally distributed.
I'm curious about the interaction between the packing strategies/heuristics and the probability distribution of the pieces. Everyone who has played the game has noticed how the 4x1 pieces appear critical to achieving a high score -- if they show up too rarely, you quickly run out of space as things stack up.
Tetris appears to be very close to "criticality", in the sense that with the right heuristics and statistics, one might achieve an unbounded score. One way to understand this phenomenon is to embed enough quality-playing heuristics, and then play (automatically) lots of games with slightly varying statistics of the pieces to see how the average score changes.
Clearly, on a Tetris board with 14 columns, one could devote every pair of columns to a single piece type. Since each piece type can efficiently pack with itself in a 2-wide column, and since each type has the same probability and the same area, each of the column pairs will fill at the same rate, on average. So only large variances will cause the game to terminate. When the game is squeezed to only 10 columns, things get much more interesting, as there does not appear to be any similar strict "ghetto" strategy.
I have taken the standard Lisp tetris code distributed with Emacs and made some radical changes to allow the parameters of the game to be modified. For example, you can now change the width (# columns) of the game and choose the probability distribution (I use Walker's algorithm, see Knuth, v.II). I intend to implement backing up (so you can practise better), additional levels of lookahead, automatic placement according to certain heuristics, etc.
If anyone else on this list is interested, I'll be happy to post the code on my web site. I'll go with the usual Gnu GPL, and my changes are public domain if anyone cares. I make no guarantees about quality or reliability of the code, and it will get modified sporadically with no warning.
Henry Baker