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:

Feature # Weight
1 -4.500158825082766
2 3.4181268101392694
3 -3.2178882868487753
4 -9.348695305445199
5 -7.899265427351652
6 -3.3855972247263626

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).

 

 

El-Tetris Dellacherie
Mean (Rows Cleared) 16,047,595 5,024,731
Standard Deviation (Rows Cleared) 12,428,449 4,557,225

As can be seen from the results above, El-Tetris clears 16 million rows per game on average, compared to 5 million rows by Dellacherie’s algorithm. With these results, and from the research I’ve done, this makes El-Tetris the best performing publicly available one-piece Tetris AI out there at the time of this writing. Woot!


27 thoughts on “El-Tetris – An Improvement on Pierre Dellacherie’s Algorithm”

  1. Thanks for your algorithm.
    Just one typo in “4. Column Transitions”, I think that should be “same column” instead of same row, right? =)

  2. Hi, the algorithm is great! I’ve finished an implement myself according to the six features you mentioned above and it works perfectly.

    My algorithm takes two steps into consideration, i.e current piece and the next one. For me, the most interesting part of your article is the determination of the coefficients of six features.

    I’ve browsed several websites and read some scholar articles about PSO method. But I still cannot figure out how to determine the coefficients. Could you please give me some hints on it? Thanks again.

    What’s more about my understanding:

    Let val be the best value of evaluation function, vector x’ = (height, rowEliminated, rowTrans, colTrans, numHoles, numWells)’ in the feasible region, and vecotr coef = (c1, c2, c3, c4, c5, c6). Hence, val = coef * x.

    Compare with PSO, should we regard the velocity as coef and position as x? I can not go any further now.

  3. Hi Bill. You’re very close! The coefficients/weights of a solution correspond to the *position* of that solution in the solution-space (as opposed to the velocity). The reason for this is because, if you were to imagine all the possible solutions as a plot, a possible solution is a point in that plot. That solution’s position can be described using its coefficients.

    The velocity of a particle, on the other hand, should be a vector that’s initialized with random values. This vector is then updated based on the position of the best solution found at that point in time.

    When I was initially working on this algorithm, I used a prebuilt Java library called JSwarm for running the optimization (http://jswarm-pso.sourceforge.net/). It might be worth looking into that.

    You might also want to look at a simple implementation of PSO written by a friend of mine here:
    http://code.google.com/p/kivj-project/source/browse/branches/junru/ParticleSwarm.java
    http://code.google.com/p/kivj-project/source/browse/branches/junru/Particle.java

    Hope this helps and let me know if you have any other questions 🙂

  4. The references really help! Now I think I get the point of how to apply PSO on this specific problem:

    1. Treat the weights as *positions* in PSO.

    2. Randomize the velocities and positions at beginning of the algorithm.

    3. Use current weights to evaluate Tetris board.

    4. Continue playing the game until AI looses or reaches the maximum round.

    5. Count total number of eliminated rows.

    6. The global best position is updated if current weights lead to more rows eliminated. And current weights will also be updated as a “better position”.

    7. Apply PSO iteration to generate the next velocities and repeat the step 3 ~ 7 until the maximum iteration time reaches.

    8. Every particle will play the game and get its own pBest in an iterative.

    9. Finally the swarm reaches the approximate global optimal position. This position is the optimal weights so far.

    AND, because the evaluation function is designed based on the thought: “the more rows are eliminated, the better weights are”. This can be used to explain why the coefficient of feature “rows eliminated” is positive while others are negative.

    There’s another interesting point:
    Why the feature *row transitions* is less important than the *column transitions* according to their different value? They are supposed to describe the same state but in fact they have different value. Can we say “feature *column transitions* is about THREE times worse than the row ones”?

    My guess is:

    The feature *column transitions* associates more tight to the row elimination, while the *row transitions* does not. A high column transition means not only the player has some trouble eliminating the rows but also the game is about over!

    The guess to the ratio between *row transitions* and *column transitions* may not have an explicit value due to different PSO implementations and different range of velocities. But there should be an inequality between these features such as:
    rows eliminated > 0; column transitions > row transitions etc.

    BTW, I just think it’s fun to learn how the algorithm is applied into specific problem. So… I typed all above to make me understood.

    Thank you again! Now I have learned so many things.

  5. Hi! Your table lists “number of rows eliminated” as the factor number two.
    In Pierre’s algorithm, there is no such factor. There is, however, a “number of piece cells eroded” factor: number of cells from the just-dropped piece that were immediately done away with by the clearing of line(s). For example, if you clear 4 lines with a Tetris piece, this factor is 4. It is also 4, if you clear 2 lines with a square piece. If you clear 2 lines with a S or Z piece, the factor is 3 (because it will have one nub still remaining on the field).

    Is this an error in the article, a fundamental change in the algorithm itself, or some other kind of omission?

    1. Hi Bisqwit,

      You are correct. The “eroded piece cells” feature is in Pierre’s original algorithm. This is intentional though and I decided to replace it with the “number of rows eliminated” since it seemed to perform better. Replacing the “eroded piece cells” feature, as well as re-optimizing the weights, are the two key distinctions between El-Tetris and Pierre’s original algorithm.

  6. Allright, thanks. I am surprised to hear that such a simple metric (as a part of the whole formula) works better than the more complex one. I also have tried similar factor optimization using a genetic algorithm, but I could not conclusively get better results.
    I should try this one.

  7. I implemented your algorithm in http://bisqwit.iki.fi/jsgames/worstpiecegame/ , and initial experience seems to validate the merit of the algorithm, but there’s no simple way to compare it to Pierre’s algorithm (which I had there previously) in this kind of context. This game uses AI to evaluate different pieces, and then chooses the worst one to give to the player, within the limits of fair average distribution.

    1. The way I compared El-Tetris to Pierre Delacherie’s in my experiments was by running a few games with the same seed for the random number generator. That way, both algorithms are given the same pieces to play with. Maybe you could try something similar?

  8. Could you give me some example about row and column transition, please?
    I follow your step but only reach approximately 100 pieces 🙁

    1. Hi Luis,

      Let’s look at row transitions examples. In the examples below, “X” is a filled cell and “_” is an empty cell.

      • XXX___XXX (If you read this row from left to right, we crossed from X to _ and then _ to X. Therefore, there are 2 row transitions)
      • X_X_X_X_X (If you read this row from left to right, we keep crossing from X to _ and then from _ to X. Therefore, there are 8 row transitions)
      • XXXXXXXXX (If you read this row from left to right, we never cross from X to _ nor from _ to X. Therefore, there are 0 row transitions)

      The exact same logic applies for column transitions as well.

      I also open-sourced an implementation of this algorithm. Might be worth having a look here.

  9. Hi there,
    I just implement your agorithm. This is the perfect one, thanks a lot.
    But I found a minnor misunderstanding here
    “Landing Height: The height where the piece is put (= the height of the column + (the height of the piece / 2))”

    Why the height of the piece must divide by 2?

    1. Hi MuoiTran,

      Glad things are working out! The main motivation for dividing by two is to put more emphasis on the height of the column rather than the height of the piece. By dividing by two, we are implying that the height of the column is twice as important as the height of the piece we are adding. Having said that, the decision to divide by two is somewhat arbitrary, meaning that the algorithm may still have worked well without dividing by two.

  10. regarding the wells:

    11011
    10011
    10000

    if i understand your source code correctly the “board” above should have a well-sum of 3?
    you only look to the left & to the right of an empty cell and then move down and count the empty cells beneath, no matter if the cells below have taken or empty cells

    and this should return 5?

    11011
    11011
    11011

    because once you have an empty cell that has a non-empty cell to its left and right respectively you move down and count the empty cells, but you do that every line

  11. Hi!

    Nice work! My Tetris AI (Tetris Analyzer) makes about 1,000,000 rows/game in average (1-piece mode), >100,000,000 in 2-piece mode. Have you checked out Misakamm’s site? (it needs to be translated from chinese: http://misakamm.com/blog/504). His AI makes 10,000,000 rows/game! I’m working on an improved version right now, trying to beat 10m rows!

  12. Hi El-Ashi,
    Thank you for sharing your algorithm. I tried to implement it but somehow it didn’t work for me. So I used the described here features + 1 more to implement them in an AI bot. I had to adjust all the weights to make the algorithm to work. If used with 1 piece preview the algorithm uses 8 features. I included the use of the hold functionality as well. So if you want to take a look at the bot performance in my Java Duel Tetris, you can download it from here: http://dueltetris.webs.com/
    You can also try to play against it. Choose the right hand side for yourself for better performance. The bot with enabled Hold is really hard to beat if you choose a starting level that plays at your speed. The level will stay the same if you choose a time mode like 2 min. game.

  13. Hello Sir. I’ve downloaded your Tetris program and it looks neat, although I want to ask. How do you change the colors for different pieces?

    And I would like to ask for the program where you obtained the weights. This is because I’m working on a Tetris-based thesis that also concerns about the weights of each feature function.

    Thank you.

    1. Hi Gregg,

      Glad to hear you’re finding it useful 🙂 If I remember correctly, I used a Java package called JSwarm (http://jswarm-pso.sourceforge.net/) for the particle swarm optimization. Back then, though, the implementation I had for El-Tetris was in Java, so using JSwarm made sense.

      As for changing the colors of the different pieces, that’s unfortunately difficult to do. Right now, each row in the board is saved as an integer. Depending on the value of the integer it knows which cell is filled and which isn’t. Information about which piece the cell belongs to isn’t stored. You’ll need to change the way the board is stored internally for you to be able to record (and render) color information.

  14. Hi!

    I looked at your tetris program and was wondering how the number of holes work. Does the following means 1 hole or 3 holes? I am not so sure if each empty space is a hole only if the cell above is filled or it can be any cells above as long as one is filled.

    xxx
    x x
    x x
    x x

    1. Hi Cinder, thanks for asking. In your example, this would be 3 holes. A cell is considered a hole if there exists a cell above it in the same column that is filled.

Leave a Reply

Your email address will not be published. Required fields are marked *