Let’s imagine you have a friend who’s very good at Tetris. You’ve challenged them to a game with a twist: you get to pick which pieces they have to play. You agree that if your friend can survive 100,000 blocks then you’ll declare them the winner; but if they get game over before this, you win the challenge. So what do you do?
Tetris is a puzzle game of falling blocks that you can rotate and move as they fall. Forming complete horizontal lines clears all the squares in that line, and the aim is to prevent the blocks from stacking all the way to the top of the playfield, which results in game over.
The playfield is 10 cells wide and 20 cells tall and the game is played with seven different blocks, called one-sided tetrominoes, that are each made up of four squares. They are labelled I, J, L, O, S, T and Z because they look a bit like these letters.
There are many different versions of Tetris but, for the challenge against your friend, you will be playing a very simple version where you can pick any block you like, regardless of what has been picked previously, and the speed of the blocks falling stays the same through the whole game.
How to lose
First let’s look at the worst strategy you could go with: choosing the same block 100,000 times.
It’s easy to see that the I, J, L and O blocks fit very neatly together and can always be arranged to completely clear the playfield. The playfield will be cleared after only ten I blocks, ten J blocks, ten L blocks or five O blocks have been placed.

Ten $J$ blocks.

…or ten $L$ blocks fit together nicely then all disappear.

Ten $I$ blocks also fit together nicely
then all disappear.
For the S, T and Z blocks it’s a little less obvious. All three follow the same idea, so let’s look at how it works for the S block:
You can see that after a number of block placements it loops back to a previous step, but never back to the start. But the stack can always be kept between two cells and four cells tall, so S blocks can be played infinitely without resulting in game over, despite never clearing the playfield.
So, regardless of the block you choose, it can always be played as many times as you like without resulting in game over. Since your friend is the best Tetris player you know, this strategy will pretty certainly result in you losing the challenge.
How to win
Let’s instead consider a combination of S and Z blocks. S blocks fit nicely with other S blocks, and Z blocks fit nicely with other Z blocks; but S and Z blocks don’t fit well together.

Two $S$ blocks or two $Z$ blocks fit together nicely…

…but an $S$ block and a $Z$ block don’t.
Because of this, if you choose an alternating sequence of S and Z blocks, the best way for your friend to avoid game over is to construct columns of only S blocks and columns of only Z blocks. The playfield is 10 cells wide and each column will be two cells wide, so there will be five columns, which is odd, resulting in either three S columns and two Z columns, or two S columns and three Z columns.
Since the S and Z blocks are simply the reflection of each other, consider (without loss of generality) the scenario with three S columns and two Z columns. This will result in the Z columns growing faster than the S columns and eventually both Z columns will reach the top of the playfield. At this point, to avoid game over your friend must place a Z block in an S column, creating a one cell wide and two cell high `hole’.

Eventually, your friend is forced to play a $Z$ block in an $S$ column
Filling these holes causes issues later on in the game since there are a finite number of times they can be filled without creating new holes elsewhere. So new holes will continue to form and your friend can only create so many gaps before they reach game over.
But will this happen within 100,000 blocks?
How many blocks?
A more in-depth explanation can be found in Heidi Burgiel’s paper How to lose at Tetris (1997), but the most important parts are the following facts that were proved:
The maximum number of alternating S and Z blocks that can be placed before a hole must appear is 240 blocks.
The maximum number of times an S or Z block can be used to fill existing holes is 120 times, each time removing two holes.
The maximum number of holes the board can contain without resulting in game over is 50 holes, which is 10 holes per column.
By calculating the total number of holes that can possibly appear on the board before game over, including the ones that get filled in, and then multiplying by the number of block placements required for each hole to appear, we get an upper bound for how many blocks will force game over. The number of holes that can appear is $(120\times2)+50=290$, so game over must occur within $290\times240=69600$ alternating S and Z blocks.
Since this is well within 100,000 blocks, you now have your winning strategy. Choose only alternating S and Z blocks and even if your friend is the Tetris world champion you’ll be sure to beat them!
Infinite Tetris?
What would happen if you were to pick blocks at random instead?
In the finite game that you and your friend are playing, the probability of a sequence of 69,600 alternating S and Z blocks occurring at any point within 100,000 blocks is incredibly small, but not zero.
Despite being very unlikely to happen during your challenge, the game-ending sequence of S and Z blocks is guaranteed to occur at some point in a long enough game of Tetris. Because of this, every game of Tetris must eventually end.
Another way to think about this is in terms of the infinite monkey theorem, which states that a monkey randomly hitting keys on a typewriter for an infinite amount of time will eventually end up typing the entire works of Shakespeare. Instead, imagine that the typewriter only has the letters I, J, L, O, S, T and Z, and the monkey hitting the keys chooses the next block in the Tetris game. Given an infinite amount of time, the monkey will eventually end up typing the sequence of 69,600 alternating Ss and Zs, ending the Tetris game it was choosing blocks for.
Back to reality
In regular Tetris games, the speed at which the blocks fall steadily increases. This causes players to make more and more mistakes and, just like the holes in the S and Z columns, these mistakes will stack up until game over is inevitable. Ultimately, small mistakes due to the time constraints will likely be what causes your friend to lose the challenge, so you probably won’t have to wait 69,600 blocks to beat your friend.
But maybe next time pick someone who isn’t as good at Tetris!
The post Cheating at Tetris appeared first on Chalkdust.



