Bejeweled Blitz

So, my friends at Popcap have released a clever variant of the evergreen classic Bejeweled™ called Bejeweled Blitz as an application on Facebook. If you want to try it out, follow this link Bejeweled Blitz

I'm far too busy playing Tower Defence like games to invest the time required to master Blitz, but the bragging rights that could be obtained from being near the top of the high score table were too enticing to be ignored. Solution? Why not get the computer to play the game for you?

An underhanded person would simply cheat by hacking the protocol, faking messages, or masquerading as a client ... where's the fun in that? I decided to turn the exercise into a chance to geek out with an over-the-top solution. A few hours later, I had it working. Follow along:

Step 1

Obtain a cheap webcam. Point it at the screen you will be playing the game on.

Step 2

Dust off your favourite development platform. My platform of choice was VB6 (In the words of Chef Gusteau from the Disney Classic Ratatouille "Anyone can cook!" Using VB6, anyone can code ... though the movie does go on to suggest that even though anyone can cook, not everyone should ... but here, errm, the analogy breaks down).

Step 3

Fire up Facebook, and learn the mechanics of the game. If it takes you more than 30 seconds to work out how to play, might I suggest another sport? (I hear watching grass grow is popular at this time of the year).

Step 4

Write a bit of code to capture the image from the camera.

Step 5

You'll probably need to mess about with the camera settings to obtain a decent picture. I found the cheap web cams to not only be very "noisy" but also very poor in the way they differentiate colours. I had quite a hard time tweaking the colour settings on the camera to allow for a reliable differentiation between the red and orange shapes in the game. (Damn you PopCap, next time you develop a game, can you spread the colours of your shapes more evenly around the RGB colour spectrum?)

Step 6

With that out of the way, the next task is to get the computer to parse the image it sees. I did this by allowing the user to draw a clipping rectangle over frame of the image. Everything outside the grid is masked out. Then the grid clipping region is divided equally into 64 equal sized rectangles. Rather than trying to use sophisticated shape detection, I divine the contents of each grid by simply averaging a selection of pixels from the centre of each grid and comparing the RGB values using a least-squares error function to a pre-computed table of known RGB values for the shapes. If you want to repeat my steps, I suggest storing these know values, like I did, in something like an Excel spreadsheet to allow constant tweaks until you get consistent, repeatable and reliable matches. To make the tweaking easier, after the program processed the RGB values, I updated a grid on the form to echo these values so that I could make micro changes to the RGB values.

Step 7

Next we train the computer where the Bejeweled game is on the screen. This is as simple as moving the mouse to the opposing corners of the player grid and reading the coordinates. I click a button which starts a five second countdown timer, giving me enough time to move the mouse to the top left corner of the Bejeweled application. After a beep, another five seconds gives me chance to move to the lower right. From these two coordinates, I interpolate the mid-point coordinates of each cell. When it's time for the PC to make a move, the mouse is programmatically moved to the appropriate cell centroid, the message sent that the mouse button is pressed, then the move, then the mouse released. Pieces can be moved, and not a string in sight! It's fascinating to watch and, for some reason, when it's playing by itself, it just looks a little creepy; like one of those player pianos.

Using a simple checksum of the screen with appropriate "slop" in the calculation allows me to decide when the game has stopped moving. I make a move, then wait for the movement to die down to quiescent levels. Like the other parameters, this took a little tweaking because of the noisy camera, and the flickering graphics in the game. The random planet background image of the game dissuaded me from using a more sophisticated detection system. The game is pretty damage tolerant to bogus clicks; if you click and the board is not ready, or you try to make a move that is not valid, nothing bad happens, and you simply hear the ding, and carry on with the next selected move.

Step 8

That's all the I/O work complete, now onto the AI. Internally, the state of the grid is stored as a small array, so it's trivial to parse. It is in the AI that I now need to concentrate my attention. I've got the beginnings of player and using just a few simple rules can consistently get a score of >100k. So far I've implemented just the basics of basic game play. As I get more time, and/or enthusiasm I'll tweak it more.

First of all, I parse the grid looking for possible five-in-a row matches, if there are one of these, I take it straight away. I start looking horizontally first (from bottom to top), maximising the chances of cascades as new gems fall in from the top, then I try from left to right in vertical columns. If there are no potential five-in-a-row matches, I look for possible four in a row matches, using the same scanning patterns. Finally, I look for potential three matches.

With this simple logic, I can get pretty good scores, but there is VAST room for improvement. Firstly, I'm ignoring any of the power-up gems you get from the superior matches; similarly the score multiplyers; these are simply treated as ordinary cells, and so get matched only if matching, perchance, happens to select them (and to be honest, I've not even generated the RGB lookup values for these, so often they get unnoticed, or worse still, identified as the Wrong shape as when averaging the white pixels from the glows in the center with other pixels around them turns them into an average RGB value that better matches another shape! As a result, in the current implementation, most of the power-ups only get activated by 'mistake'). Even with the computer making really dumb play, the speed at which it can shuffle through moves compensates.

I'm still suffering with the occasional Red/Orange misclassification, and sometimes a White/Yellow mismatch (the random shimmering of the pieces and the crappy picture compounding this). This has the potential to get me into a dead-lock where the computer makes a move, thinking the board will update, but it does not, so it scans again, and finds the same move again, and blissfully repeats the same bogus move over and over again. To stop this, when scanning for three in a row, I don't start from same location each time, but instead use a static variable to increment the starting seed on the grid for each move (Yes, yes, I know a similar issue can exist in the five-in-a-row and four-in-a-row matches).

If I implemented scanning and detection for the special pieces and a little more smarts in selecting of moves, I'm sure it would be possible to create a player that is unbeatable by a human opponent; The pure speed at which the PC can make moves and the ability for it to look a couple of moves deep in the selection of the next piece to move would be too much for even the most dexterous and astute warm body. (I'm not sure that more than two moves ahead would gain much, as the shapes that appear from the top are "random", and after the first move, who knows if the fresh gems you were delivered would change your strategy for the upcoming move).

You can find a complete list of all the articles here. Click here to receive email alerts on new articles.


	Advertisment

My PC plays better Bejeweled than I do