El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm

Update: Full source code and implementation now available here!

This algorithm is part of a project I was working on last term as part of my Artificial Intelligence class. This algorithm, which I will be referring to as “El-Tetris”, is an algorithm for playing Tetris by inspecting only one piece at a time (as opposed to two or three pieces in some variations of the game). It is based on Pierre Delacherie’s Tetris algorithm, which is known as one of the best one-piece Tetris playing algorithms.

Before discussing the details of the algorithm, let’s briefly look into how you, a human player, would play tetris.

When you play tetris, you are faced with two decisions every time you are given a tetris piece:

1. Where to position the piece
2. Which orientation of the piece to play

Naturally, you want to eliminate as many rows as possible and maximize your score. To accomplish that, you would (subconsciously) be doing the following:

while the game is not over:
  examine piece given
  find the best move possible (an orientation and a position)
  play piece
repeat

What would be the best possible move then? You would usually try to eyeball certain features to help you determine that. You might, for example, ask yourself these questions:

• If I were to play the move, would that create holes in the game board?
• If I were to play the move, how many rows would I clear?
• If I were to play the move, what would be the height of the highest column?
• … and so on

That’s exactly what El-Tetris does. For every given piece, it evaluates every possible orientation and position against a set of features. The move with the best evaluation is the one that is played.

There are six features in total, formally outlined as follows:

1. Landing Height: The height where the piece is put (= the height of the column + (the height of the piece / 2))
2. Rows eliminated: The number of rows eliminated.
3. Row Transitions: The total number of row transitions. A row transition occurs when an empty cell is adjacent to a filled cell on the same row and vice versa.
4. Column Transitions: The total number of column transitions. A column transition occurs when an empty cell is adjacent to a filled cell on the same column and vice versa.
5. Number of Holes: A hole is an empty cell that has at least one filled cell above it in the same column.
6. Well Sums: A well is a succession of empty cells such that their left cells and right cells are both filled.

The evaluation function is a linear sum of all the above features. The weights of each feature were set and determined using particle swarm optimization.

The following table shows the feature number (as outlined above) and its weight respectively:

El-Tetris’ performance has been compared to Dellacherie’s using a framework written in C called mdptetris. The following are the results after running 35 games on a standard sized board (10 columns x 20 rows).