Projects: Bejeweled Blitz Bot

What is it?

I encountered Bejeweled Blitz on Facebook. It’s a game where you swap adjacent jewels in an attempt to makes at least three consecutive jewels. The "Blitz" means that you get one minute and bonuses when you play quickly. There’s only one problem: I’m a terrible player. When playing on Facebook, it showed me the scores of friends who also play Bejeweled Blitz, and it became clear that I’m a bottom-tier player.

After playing for a while, I had to admit that I was likely to remain a bottom-tier player. I wasn’t getting significantly better and some of my friends were getting scores upwards of 200,000 or 300,000 while most of my games were 20,000 or less and I rarely got above 100,000.

Some people might quit playing. Others might redouble their efforts to improve their playing abilities. I don’t enjoy video games enough to get good at them, but something about this game upset me. I wanted to win. Clearly, there was only one solution: I needed to write a program to play for me.

Bejeweled Blitz is a good game for this: the game is very regular (colorful gems on a plain grid). However, it’s not quite as simple as it seems, so it was an excellent learning experience.

My Bejeweled Blitz bot (short for "robot") isn’t perfect, but it plays a pretty good game. A "bad" game is just 200,000 points (way better than me), it regularly scores above 500,000 points, and occasionally above 800,000 points. I made a program that beats the pants off of me! There are people who play better than this, but I suspect they are the rare exception.

The Action-packed movie

The video below shows a sample game where it scored just over 800,000 points. It also shows the bot running: you can see what it thinks is on the board and the moves it’s making.

Near the end, you’ll notice it gets stuck: it does make occasional mistakes, and in this case it couldn’t make progress. I have an out for that: I pause the bot, make one move, and let it resume. I think this is a nice example of human-aided computing. Other than that one move, it played the whole game by itself.

Technical Details

I chose a simple approach. An important goal is speed: the game only lasts one minute and I wanted to maximize my score. The overall technique was:

  1. Take a screen shot of the board.
  2. Convert the image from RGB to HSV (Hue, Saturation, Value).
  3. In the middle of each square where a piece is, analyze the colors to figure out which piece is there. Specifically, make a histogram of the hues in each square. Compute the vector distance between that histogram and a set of pre-calculated histograms for the pieces. The shortest distance is the piece.
  4. Choose the best move: the one that removes the most pieces. (There are details here: it does some lookahead to get better moves, it prefers moves near the bottom of the board, and if it can get a multiplier piece, it does it even if it doesn’t remove many pieces, etc.)

When you look at a basic board, this seems like a pretty good approach because the colors for each piece are nicely distinct. Here is a sample board:

In reality, it’s messier than that, so the implementation is more complex than I described above In a good game, the board is in constant motion, and there are lots of graphics to make the game "fun". For example, here are two pieces being swapped. (I’ve grayed out the irrelevant pieces):

There is often extra text overlaying the pieces. Also, when pieces are removed, there is an animation that leaves small bits in the image. (Again, I'’ve grayed out the irrelevant pieces):

Here’s another image with an explosion in it:

All of these mess with the basic algorithm. The final algorithm has various heuristics to tweak it, such as extra checks to be sure it’s an orange piece and to distinguish flaming bombs.

The program was written in C on a Mac.