Arms Race, Part 4

In Part 3, I went all the way down the pixel level to describe how my automatic Bejeweled player detects the color and type of the gems on the screen.  Today, we'll use that information to get ridiculously high scores in Bejeweled Blitz.

Detecting all the colors was pretty tough, and detecting the type of gem in each cell was even tougher; but now we need the software to make a decision and act on it.  Specifically, of all the possible trigger/target combinations available on the board at the moment, which one is the best one to do next?  I chose to go a pretty simplistic route on this, since I was, after all, writing this for the heck of it.

I do not have the software attempt to predict combos or other more advanced plays to maximize points.  This is something that humans playing the game do to some extent without even thinking about it, but it becomes more challenging for software.  Consider the picture below.  I have highlighted the 4 possible moves by drawing a red blobby line between the trigger and target gems.  Which move will generate the most points?  If you said "the bottom-right one", you would be correct, because both the green and red gems would be removed, not to mention the bonus you get from doing a combo move like that.  By the way, the software would call that move "6,5-7,5".  The best move that the software sees from this board is "4,6-3,6" - swapping the white and yellow gems in the bottom-middle of the board.  I'll explain why this is chosen shortly.

Which move is best?

So skipping the combos and any other move in which you choose things based on secondary effects, I can define some scoring rules by decreasing order of weight:

1. Always use paths with multipliers in them first - this is a no-brainer, because that has long-term positive effects on the entire game.
2. If a path has a crosshair in it, it will destroy more gems than any other move on the board - except maybe a hypercube, but the software doesn't detect those, so that's moot.
3. If a path has a flaming gem in it, its explosion will take out a 3x3 square of gems as well as the path gems themselves, yielding 9-10 gems destroyed on a 3-gem path.
4. Longer paths are better than shorter ones, because they destroy more gems.  Plus, they generate crosshairs, hypercubes, and flaming gems, so that's goodness too.
5. Paths lower on the board have more opportunities to create combos than paths near the top.  All else being equal, pick the lowest path on the board.

Going back to our picture and following these rules, we can see that there are no multipliers, no crosshairs or flames, and no 4-gem or greater paths.  That gets us all the way to rule #5, where we pick "4,6-3,6" because its highest gem (all of them) is lower than the highest gem of any other path on the board.

OK, great, we have rules of how to pick a path, but we've gotten a little ahead of ourselves.  How do we find the damn things?  In the software, I have a Grid object with 8x8 GridItem objects (aka Gems) in it.  During the detection phase, I set the color and type of each of those gem objects.  When I'm done, I have a software representation of the board as of the last screen capture.  Then I look at each gem and check to see if it is the leading edge gem of one of the following patterns:

The four path patterns in their basic form

In the first pattern, the gray squares are optional.  Readers familiar with Bejeweled will notice that adding one or both optional squares on will cause the path to generate a flaming gem or a hypercube, respectively.  The first case also has a special sub-case where the mirror-image is also possible, with the trigger below the target rather than above, but only the first of the two optional gems is present.  In this special sub-case, we move the trigger to the optional gem position to form a "T" when the path is completed; this generates a crosshair, so it is obviously more desirable.  If both optional gems are present, however, we leave the trigger where it is because hypercubes are awesome - even if the software doesn't know how to use them right now.

Anyway, in examining each gem to see if it is the leading edge of one of the patterns above, I actually examine it 4 times for each of the 4 patterns above - once with each possible 90-degree rotation of the pattern.  Mirror-images are included as well, but they are done within each rotation, so it's only 16 (4x4) checks on each gem instead of 32 (4x4x2).

Once all the processing above is done, we have a full list of every path available for activating.  For each path, we generate a score based on the 5 rules discussed above, and then sort them by score in descending order.  Then we pick the best possible path and execute it by moving the mouse to the trigger, clicking, moving the mouse to the target, and clicking again.  I do the mouse movement and clicking using the XLib API again: XSetInputFocus, XSync, XWarpPointer, XQueryPointer, and XSendEvent in various combinations that I worked out primarily through internet searching and a lot of trial and error.

As I was coding all of this, I went with the most expedient code possible, rather than the highest-performing.  Again, it was a project being done for the heck of it, so spending a lot of time designing around performance was too much like work.  Nevertheless, as I reached code completion, I started being concerned that the image processing and path detection would take so long that the software wouldn't even outscore me.  After all, I can hit 350k pretty reliably every week, and my highest human score was 652k.  Besides speed, I also have the human judgment that lets me pick the combo path automatically as we saw at the start of the post.

I needn't have worried: the screenshot, the origin detection, the color and state detection, the Grid-building, the path detection, and the scoring and decision process all takes 9 milliseconds to finish.  In fact, this thing is so fast that it finds matches as gems fall that don't really exist.  This causes it to have a high mistake rate, so I actually have it sleep (do nothing) for 50 milliseconds between passes to give Bejeweled a little time to catch up.  Even so, it's still mighty fast.

Below are two videos, neither one using boosts.  The first was captured while I was manually playing, and while it's not exactly a stellar run, it's a fairly representative game, finishing with a score of 166k.  The second is a run using my software.  It gets confused a couple of times, pausing for a full second while it reacquires the origin; and notice how it just ignores the hypercubes and makes a lot of stupid plays.  And yet the score speaks for itself.

Playing by hand, for 166k

Playing by program, for 698k

Yeah, that'll do.