Solving Tetris via a Scoring Algorithm

When I was in college, I wrote a simple Windows Tetris game I called WinTetris, because the name wasn’t taken and I wasn’t feeling very creative that day. This project was at first just an exercise in Win32 programming and game logic, and the first version featured very ugly GDI graphics with DrawRect.

Over time, I polished it quite a bit, and added a lot of new features. I replaced the ugly graphics with DirectDraw, added support for mouse/keyboard controls, added sound and music, A/B game types, and LAN multiplayer. But quite possibly my favorite new feature was the “demo mode”, which starts when you launch the program.

Demo mode was a simple way for me to use the tetris engine I had already developed to do something cool; write an algorithm that could play tetris extremely well. The bonus was that I could show off both my AI programming and my game at the same time, thanks to my demo mode.

So how does it work? At the top-most level, it does the following:

  1. Considers every possible piece placement for the current piece, including both lateral movement and rotation.
  2. Assigns each piece placement a score, according to some kind of scoring mechanism.
  3. Chooses the placement with the highest score.
  4. Moves and rotates the piece into place.

This arrangement is pretty logical, but everything hinges on the scoring algorithm. How would you write such a function? Personally, I thought a bit about things that are good, and things that are bad when it comes to playing tetris, in general:

  • Completing a line is a good thing. Completing more than one line at once, all the way up to a tetris, is even better.
  • Reducing the maximum stack height is a good thing. Conversely, making the maximum stack height higher is bad.
  • Placing a piece lower in the playing field is generally better than placing it higher.
  • Creating empty holes beneath a piece is bad.

So now that you know what to look for, you write methods that will tell you the effects of your piece placement, assign each measure a weight, and total up the plusses and minuses. But what weight values to pick?

Personally, what I did was to pick weights that seemed reasonable, watch how the game played, and then made adjustments if I thought it was playing in a way that was either too reckless or too safe. And although I didn’t mention it before, my goal was an algorithm that would take a long time to lose, not one that loves to set up tetrises or rack up a high score.

In the end, I made the following weight table:

Hole Count: -500
Lines Completed: +500
Block Height: -150
Chasm Height: -400

If I was to tweak these weights again, I would want to take a more scientific approach. I could use even more AI programming to run thousands of tetris simulations, and see which weight values yielded the lowest average stack height, and use those values. Perhaps that could be a future project of mine.

The last trick I added was a modification of the process, not the scoring algorithm. In the process I gave above, the code only evaluates the current piece. But players get to see the next piece! So instead of choosing the piece placement with the highest score, I modified my algorithm to calculate the best combined score (A + B) for the current piece as well as the next piece, and use that information to place only the current piece. So the current piece is placed with the highest potential score. The weird thing about this is that the algorithm is not committed to that second placement. It can choose to do something completely different if the next piece changes the optimal two-piece score.

So now that you know how to write a Tetris AI, break out your favorite compiler and improve on my methods. I implemented WinTetris such that you can create your own AI DLLs if you want to play around with it. The installer and source code for WinTetris is available at http://www.hexar.net/wintetris.php. Enjoy!