Deadly piece sequence

You might have heard of the result that you can play forever with bag randomizer, Hold and 3 previews (a similar setup even works with 0 previews). However, the opposite is true, if you play with a randomizer that can generate all piece sequences (e.g. memoryless randomizer). In this article we will present a piece sequence that will top you out - no matter what you do. Even Hold, kicks and knowing the sequence in advance can't save you. Deadly piece sequences even exist for a 100 columns wide and 40 rows high matrix.

Alternating sequence of S and Z pieces

The following sentence is a result of Heidi Burgiel's paper "How to Lose at Tetris". We assume the matrix is 10 columns wide, 20 rows high and there is no Hold feature. A game ends, if the current piece can't be placed entirely in the visible part of the matrix.

A Tetris game consisting of an alternating sequence of S and Z pieces (SZSZSZSZ...) will always end before 70,000 Tetrominoes have been played.

The following sections will cover a complete proof. But first, let's illustrate the major idea behind the proof by having a look at all possible S and Z placements near the left wall.

2 blocks in 1st column
2 blocks in 2nd column

0 blocks in 1st column
2 blocks in 2nd column

1 block in 1st column
2 blocks in 2nd column

0 blocks in 1st column
1 block in 2nd column

What have all those placements in common? There's no placement where more blocks (filled cells, Minos) are added to the first column than to the second column. As a result, at each point in time there will be never more blocks in the first column than in the second column (starting with an empty field). This also means that certain ("special") placements can only be made a finite number of times - or the height difference between the first and the second column becomes too big.

Step 1 of the proof

Not more than 120 special S and Z placements can be made.

Here a placement is called special, if the piece is placed with its leftmost blocks in an even-numbered column. Columns are numerated from 1 to 10 (from left to right).

Let B_i be the total number of blocks (Minos, filled cells) located in the i^th column.
Let H_i be the number of dropped S & Z pieces that contributed blocks to the (i-1)^st, i^th and (i+1)^st columns.
Let V_i be the number of dropped S & Z pieces that contributed blocks to the i^th and (i+1)^st columns.

Then it holds for every i in 1 ... 10

B_i = 2·V_i-1 + 2·V_i + H_i-1 + 2·H_i + H_i+1 - # cleared lines

wheras V₀ = 0, V₁₀ = 0, H₀ = 0, H₁ = 0, H₁₀ = 0, H₁₁ = 0.

Now let's compare the number of blocks in two neighboured columns . For each i in 1 ... 9 we have

B_i+1 - B_i = ( 2·V_i+1 + H_i+1 + H_i+2 ) - ( 2·V_i-1 + H_i-1 + H_i )

This can be rearranged to

2·V_i+1 + H_i+1 + H_i+2 = ( B_i+1 - B_i ) + ( 2·V_i-1 + H_i-1 + H_i ) (☆)
2·V_i-1 + H_i-1 + H_i = ( B_i - B_i+1 ) + ( 2·V_i+1 + H_i+1 + H_i+2 ) (☆☆)

What have we won? Since our matrix is 20 rows high, we know that B_i+1 - B_i ≤ 20 and B_i - B_i+1 ≤ 20.
This can lead to a recursive estimate of the terms on the left side.

By using (☆) and beginning on the left side we conclude

i=1: 2·V₂ + H₂ + H₃ = ( B₂ - B₁ ) + ( 2·V₀ + H₀ + H₁ ) ≤ 20 + 00 = 20 (1)
i=3: 2·V₄ + H₄ + H₅ = ( B₄ - B₃ ) + ( 2·V₂ + H₂ + H₃ ) ≤ 20 + 20 = 40 (2)

By using (☆☆) and beginning on the right side we conclude

i=9: 2·V₈ + H₈ + H₉ = ( B₉ - B₁₀ ) + ( 2·V₁₀ + H₁₀ + H₁₁ ) ≤ 20 + 0 = 20 (3)
i=7: 2·V₆ + H₆ + H₇ = ( B₇ - B₈ ) + ( 2·V₈ + H₈ + H₉ ) ≤ 20 + 20 = 40 (4)

Now let's sum up the formulas (1), (2), (3), (4). We obtain

2·( V₂ + V₄ + V₆ + V₈ ) + ( H₂ + H₃ + H₄ + H₅ + H₆ + H₇ + H₈ + H₉ ) ≤ 20 + 40 + 20 + 40 = 120

Thus

V₂ + V₄ + V₆ + V₈ + H₂ + H₃ + H₄ + H₅ + H₆ + H₇ + H₈ + H₉ ≤ 120

which corresponds to the statement that not more than 120 special S and Z placements can be made.

Step 2 of the proof

Not more than 240 pieces can be played before either a special placement is made or a hole is created.

A hole denotes an enclosed empty cell. The condition above means that all pieces must be placed vertically in 5 lanes, each lane 2 columns wide with odd-numbered left-most column.

Let's say the initial surface is shaped in the way, that there are 3 lanes for S pieces and 2 lane for Z pieces. Let's consider a sequence of 12 pieces. If we don't want to violate the condition, we have to place the 6 S pieces on the S lanes and the 6 Z pieces on the Z lanes. In average, that's 2 pieces per S lane and 3 pieces per Z lane. This means the height difference (average height of Z lanes minus average height of S lanes) increases by 2 every 12 pieces. The height difference will always be between -20 and +20, since we play on a 20 rows high matrix. If we start at -20, we will reach +20 after 240 pieces. At this point the next Z piece must be placed on an S lane. The limit of 120 pieces is also true for every other combination of lanes.

We start with a relatively flat field. 3 lanes for S pieces, 2 lanes for Z pieces.

We try to distribute the next 12 pieces evenly.

However, the Z lanes grew by 2 rows.

After a while, the Z lanes are at the top. We are forced to drop a Z piece on an S lane.

This creates 2 holes. The holes can only be cleared by special placements.

Step 3 of the proof

Not more than 290·240 pieces can be played before the game ends.

In Step 1 we've seen that the number of special placements is limited (by 120). In Step 2 we've seen that we are forced to make special placement (since we cannot make an infinite numer of holes). Combining these results we conclude the finiteness of the game. We still have to proof the upper bound of 70,000 pieces.

In the following, let's assume we create exactly 2 holes each time we have to make a hole with a non-special placement. We'll refer to it as a directional change (dropping an S piece on a Z lane or vice versa). In Step 2 of the proof, every hole made after 40 dropped pieces will be either by a directional change or a special placement. So the same limit can be proven without this assumption. It's just that the wording becomes too complicated.

First, let's note that we cannot fill more than 2 ex-hole cells per special placement, respectively 2·120 = 240 holes in total. The final board cannot contain more than 100 holes created by directional changes. So the number of directional changes is limited to 170. This also limits the total number of directional changes and special placements to 170 + 120 = 290. Every 240 pieces we must make one of those two. This concludes the upper bound of 290·240 = 69,600 pieces.

A horizontal special placement can uncover holes in 2 different columns. On the other hand, you cannot dig deep enough to clear 2 holes on top of each other without another special placement.

A vertical special placement can uncover holes or clear 2 holes, but not both at the same time.

Lower Bound

The 70,000 pieces limit is just an upper bound and mustn't be even close to the real maximum. In Step 1 of the proof, 120 special placements can only be reached in the case that all special placements are horizontal and that B₁ = 0, B₂ = 20, B₃ = 0, B₄ = 20, B₇ = 20, B₈ = 0, B₉ = 20, B₁₀ = 0. If you have holes in your stack, then you won't be able to drop 240 pieces, before you are forced to create a hole or make a special placement. For those reasons a maximum of 5000 pieces is more realistic.

In the external link section you'll find a video of my game that lasts 2387 pieces respectively 942 lines. Apart from the ending, all S and Z pieces are dropped vertically. The used technique manages to restore the initial position, whereas 2 rows are wasted per iteration. The first iteration takes 512 pieces. An iteration involves 6 special vertical placements, 4 of them are used to uncover and clear holes.

In the Fumen, a 5 lettered code (e.g. LLR*RR) is used to describe the surface of the stack. Each letter stands for one lane. S pieces can be dropped on L lanes without creating holes (resp. Z pieces on R lanes). An asterisk behind the letter notes that the corresponding lane is 1 row higher/lower than most other lanes; more precisely the height of the lane + cleared lines is uneven.

Note, that randomizers based on pseudorandom number generators won't create fixed sequences containing such a long chain of S and Z pieces. Also note that players can be topped out much faster when not knowing the sequence in advance. Nobody seems to have cleared more than 30 lines on Hatetris. That's a Tetris game without any previews, that reacts to the player's current stack and deals the worst imaginable piece.

O pieces

O pieces behave exactly the same way as vertical S and Z pieces in the manner that they add 2 blocks to each of 2 neighbored columns. Thus identical statements regarding O pieces can be made in Step 1 of the proof. On the other hand, O pieces can be dropped on S or Z pieces without creating holes (Skimming). So the argument in step 2 cannot be applied for an alternating sequence of S and O pieces (SOSOSOSOS...). More precisely, such a game could be played forever.

On the other hand, a game that reacts to the player's current stack can top out a player by majorly handing out O pieces. For more details see John Brzustowski - "Can you Win at Tetris?".

Other matrix sizes

Odd number of columns

Here any sequence consisting of nothing but S, Z and O pieces will force a top out eventually. More precisely, the game will end before 10·n·(n+1) pieces are played in a 2·n + 1 columns wide and 20 rows high matrix.

We will prove the upper bound of 120 pieces for a 7 wide matrix. The proof pattern can be applied to other numbers of columns and rows.

Let's use the notation of Step 1 of the proof, whereas V_i includes O pieces that contributed blocks to the i^th and (i+1)^st columns.

By using (☆) and beginning on the left side we conclude

   i=1: 2·V₂ + H₂ + H₃ = ( B₂ - B₁ ) + ( 2·V₀ + H₀ + H₁ ) ≤ 20 + 00 = 20    (1)
   i=3: 2·V₄ + H₄ + H₅ = ( B₄ - B₃ ) + ( 2·V₂ + H₂ + H₃ ) ≤ 20 + 20 = 40    (2)
   i=5: 2·V₆ + H₆ + H₇ = ( B₆ - B₅ ) + ( 2·V₄ + H₄ + H₅ ) ≤ 20 + 40 = 60    (3)

By using (☆☆) and beginning on the right side we conclude

   i=6: 2·V₅ + H₅ + H₆ = ( B₆ - B₇ ) + ( 2·V₇ + H₇ + H₈ ) ≤ 20 + 00 = 20    (4)
   i=4: 2·V₃ + H₃ + H₄ = ( B₄ - B₅ ) + ( 2·V₅ + H₅ + H₆ ) ≤ 20 + 20 = 40    (5)
   i=2: 2·V₁ + H₂ + H₁ = ( B₂ - B₃ ) + ( 2·V₃ + H₃ + H₄ ) ≤ 20 + 40 = 60    (6)

Now let's sum up the formulas (1), (2), (3), (4), (5) and (6). We obtain

2·( V₁ + V₂ + V₃ + V₄ + V₅ + V₆ + H₂ + H₃ + H₄ + H₅ + H₆ ) ≤ 2·( 20 + 40 + 60 ) = 2·120

which corresponds to the statement that not more than 120 placements can be made in a 7x20 matrix.

Of course for an odd number of columns, an endless sequence of O pieces will force a topout with zero line clears.

Even number of columns

We must make a case differentiation:

Number of columns is not divisible by 4: Here an alternating sequence of S and Z pieces will force a top out. This can be proven analog to a 10 columns wide and 20 rows high matrix.

Number of columns is divisible by 4: An alternating sequence of S and Z pieces can be survived forever by using half of the lanes for S pieces and the other half for Z pieces. However, there are still enough ways to destabilize the lanes in Step 2 of the proof, for example by dealing an extra S piece every (2·n + 1) pieces, whereas n is the number of columns devided by 2. In this case there are 2·n lanes but the sequence repeats itself every (2·n + 1) pieces.