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!

Published by

HexarA

Seattleite. Climber. Snowboarder. Traveler. Party rocker. Technologist. Spanish enthusiast. Fun-seeker.

4 thoughts on “Solving Tetris via a Scoring Algorithm”

  1. I totally did write this code a long time ago. But I never blogged about it, and it was easy to write a post about because it’s easy to remember the general solving algorithm I used.Also, I’m surprised you found my blogspot so quickly, I just made it public this week.

    Like

  2. I wrote a Tetris game a while back with a load of features so it could be customised to act more or less like various different existing implementations (and some other weird features like co-operative two-player and “no gravity”). And an AI self-player (or computer opponent) is the only major thing I planned and never got around to. Interesting post.

    Like

  3. Hi Hexar!

    I wrote a Tetris engine some time ago: http://www.youtube.com/watch?v=KaBB9n3Lb7M. I'm “converting” it to Scala now. You can read about the algorithm here (you may need to translate it from Swedish to English!): http://tengstrand.blogspot.com/2011/02/algoritmen.html. You can find the source code for the board evaluator here: http://tetrisai.git.sourceforge.net/git/gitweb.cgi?p=tetrisai/tetrisai;a=blob;f=src/main/scala/net/sf/tetrisai/boardevaluator/TengstrandBoardEvaluator1.scala;h=4657e8636aa6ba2ccd240cea44ac9b9821a1b251;hb=HEAD

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s