Tetris and matrices over semirings

Here's a position in Tetris:

  X    X
XXXX XXX X

We can describe this as a list of heights (1,1,2,1,0,1,1,2,0,1).
Here's a Tetris piece:

   Y
 YYY
 Y

and here's what you get when you drop one on the other

   Y
 YYY
 YX    X
XXXX XXX X

We get a new list of heights (1,3,3,3,0,1,1,2,0,1). This has failed to capture the 'overhang' in the 4th column but lets just think about Tetris pieces dropped from the top so overhangs make no difference. What is the relationship between the old and new list of heights?

It turns out that you can get one from the other from a single matrix 'multiplication' - the catch is that we have to work over the semiring (R union infinity,min,+) instead of the more usual semiring (well, actually field) (R,+,*).

Let hn be the initial height in the nth column and hn' be the height after dropping the new piece. Think about how low the new piece made of Ys can fall. If the left most column of the Ys is in contact with the X's then it's lowest point ends up at height h2+1. If he middle column is in contact then the lowest point ends up at h3. And if the right column is in contact the lowest point ends up at height h4. So the lowest point ends up at height min(h2+1,h3,h4). So we can now write down expressions for the new height: h2' = min(h2+1,h3,h4)+1, h3' = min(h2+1,h3,h4)+1, h4' = min(h2+1,h3,h4)+2. We can rewrite this as:

h2' = min(h2+2,h3+1,h4+1)

h3' = min(h2+2,h3+1,h4+1)

h4' = min(h2+3,h3+2,h4+2)

Now let's switch to the semiring (R union infinity,min,+) (with 'additive' identity OO = infinity). Use the notation (+) = min and (*) = +. Then we can write:

h2' = 2(*)h2 (+) 1(*)h3 (+) (1)*(h4)

h3' = 2(*)h2 (+) 1(*)h3 (+) (1)*(h4)

h4' = 3(*)h2 (+) 2(*)h3 (+) (2)*(h4)

We can now write this in matrix form h' = Mh where h is

(  0 OO OO OO ...)
( OO  2  1  1 ...)
( OO  2  1  1 ...)
( OO  3  2  2 ...)
( ...  ...    ...)
( ...          0 )

So corresponding to each Tetris piece in a particular column we have a matrix. To find the effect of dropping multiple pieces we just multiply the matrices in the semiring in turn.

Turns out this has all types of applications - for example resource allocation in a queing system. I'll leave you to figure out how falling testris pieces might represent jobs submitted to a queing system and how the columns might represent types of resource.

Here's an easy exercise: If M is the matrix of a piece, what piece is the transpose M^T the matrix of?

I learnt this from this paper by Gaubert and Max Plus. (I think Max Plus is a relative of Bourbaki.)

Many algorithms are 'linear' in this semiring. Another example that seems quite different is the dynamic programming algorithm for approximate DNA string matching. I tried to work out what the transpose matrix did (ie. what the adjoint algorithm was) and then use the code reversal method I mentioned earlier to see what new algorithm I obtained was. It was another approximate string matcher but this time it worked through the strings in the opposite direction. (Note how each operation in this description is essentially of the form a = max(some terms added to constants).)