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