kleemans.ch

Some time ago (it’s been over four years!) I posted my bejeweled-bot, a simple bot for cheating in the Facebook game Bejeweled Blitz. By simulating mouse moves, it gets a pretty high score by some very basic strategy.

I was asked later on for a detailed writeup so I’d like to point a few things out about how to write a bot which plays a game. I actually was surprised that it still worked after all this time :-)

I tweaked it a bit (it’s now optimized to run on OS X) and was able to push my highscore up to 4.5 million (with use of “Chronostone”, a rare gem):

Outline

As a really basic strategy for any bot, it loops over the following steps, which is similar to how a game works, like the famous game loop :

Analyze board: How is the actual situation? Which gems are there, how are they aligned?
Calculate moves: Based on the board situation, which are the best moves?
Execute moves on board: Execute as moves (ideally ordered by expected outcome) as fast as possible.

Recognizing the game window

But before we can get into the game loop, we have to do some preparations, like recognizing where the game window is. We relate on the pixel coordinate system of the screen, which starts in the upper left corner.

Because screen sizes vary, I decided to write a very simple, pixel-color based recognition, which starts at 1/3 of the width and 1/2 of the height of the screen, so putting the window anywhere where it touches one of those lines will just be fine. Window recognition works as follows:

If a certain colour is found (for the horizontal line we use RGB 199, 199, 199 and for the vertical line RGB 215, 215, 215), we save the coordinates. We do this for both the x- and y axis:

# detect anchors
screen = ap.screen.get_size()
x = y = 0
for i in range(screen[0]):
  if x == 0 and get_pixel(i, screen[1]/2) == (199, 199, 199):
    x = i
  if y == 0 and get_pixel(screen[0]/3, i) == (215, 215, 215):
    y = i
  if x != 0 and y != 0:
    anchor = (x, y)
    break
print "Detected anchor:", anchor

Recognizing gems

So we have the game window and know where everything will be, where the buttons are to click and where the gems will appear. Next up is recognizing which gems are on the playing field, which appears to be non-trivial to get 100% right. As the board will be constantly changing with every move we don’t need a perfect match and also a 90% will do, so I just went with simple color recoginition for distinguishing between gems.

I took a fixed point at every gem and collected RGB samples from there, for later to match them with the color identified:

Here’s a simple output map of colors and their category:

def match_color(pix):
    colors = {
    (250,  10, 250): 'p', (185,  16, 184): 'p', 
    (217,  19, 216): 'p', (255,  73, 255): 'p', 
    ( 98, 254, 156): 'g', (  0,  94,   6): 'g', 
    (  0, 168,  10): 'g', (206, 255, 255): 'g', 
    (254, 254,  38): 'y', (254, 247,  67): 'y',
    (255, 255, 102): 'y', ( 20, 112, 232): 'b',
    ( 44, 156, 252): 'b', ( 21,  74, 120): 'b', 
    (254,  29,  59): 'r', (215,  17,  30): 'r',
    (254, 254, 254): 'w', (211, 211, 211): 'w', 
    (254, 254, 137): 'o', (252, 126,  44): 'o', 
    (114, 186, 112): 'X'}

    for color in colors:
        if sum([abs(color[i]-pix[i]) for i in range(3)]) < 60:
            return colors[color]

    return '.'

Notice how in the loop below, there’s a check if the color provided is anywhere near one of the known colors (up to 60 points near to it over all three values). Even with this threshold not every color is recognized, for example during ongoing visual special effects:

Here the colors are much darker than in normal mode, so for a few seconds, the algorithm is “blind” and no gems are recognized. Several other difficulties include moving/falling gems, special gems (from combining 4 and 5 gems), burning gems, score points in front of the board, explosions, fire and special effects, like on the following board:

Simulating input

After analyzing the board and how the gems are arranged, the hardest part is already done. Now we just need to build some simple rules for moving the gems into position:

# gem in the middle is missing, horizontal
if same_gem(x, y, x-2, y):
  if same_gem(x, y, x-1, y-1):
    move_fields(x-1, y, x-1, y-1)
  if same_gem(x, y, x-1, y+1):
    move_fields(x-1, y, x-1, y+1)
# two gems next to each other, horizontal
if same_gem(x, y, x-1, y):
  if same_gem(x, y, x+1, y-1):
    move_fields(x+1, y, x+1, y-1) # right
...

A simple move where the middle gem is missing

Autopy is a great help simulating input, and the methods in the script for moving the mouse or clicking are just wrappers for the autopy methods, including some pause so all inputs will be accepted.

def left_down():
    ap.mouse.toggle(True, ap.mouse.LEFT_BUTTON)
    time.sleep(SLEEPING_TIME)

Also, timing is crucial when it comes to optimizing the game loop. When the board is analyzed, several moves are detected, but maybe it’s not helpful to execute them all, because each move can change the whole board and the move would no longer be helpful or even valid. A common value I found out that works is 5 moves, but you can try other values at the beginning of the script:

MAX_MOVES = 5

Another bottleneck was the screen capture time. Autopy was fine on Ubuntu and a relatively small screen, but on Windows with a Full HD 1920×1080 taking a screenshot would take about 0.3 seconds, which is to long to run the script continuously. I updated the screenshot part according to this StackOverflow answer so it is now optimized for Mac OS X. For Ubuntu, I think Autopy is still the best choice, and I did some timing with pyscreenshot for Windows, but unfortunately it seems to be too slow.

Ending the game

At last, it’s important to give back the control to the user as soon as possible. There’s a maximum runtime (defaulting to 70 seconds) after which the script will stop running, but you may want to extend that to 150 seconds or more when using special gems, because they will slow down the gameplay, allowing to play longer than the original 60 seconds.

Not only time, but also some predefined value (taken from the game) will make the script stop, or if the board is suddenly empty (or no gems have been recognized), as it is the case when the browser window changes or the game is finished and some popup appears.

while (time.time() - t) < MAX_TIME:
    if get_field(2, 4) == (60, 109, 118) or not board_valid(board):
        break # "time up" board corrupted

def board_valid(board):
    whites = 0
    for line in board:
        for field in line:
            if field == 'w':
                whites += 1
    if whites >= 20:
        return False
    else:
        return True

It’s still not 100% safe (if some message from your operating system partly overlaps the game, it might not be recognized), but in most of the cases it will stop. If not, you’ll have to sit through 70 seconds watching the script trying to click frantically without being able to do anything :-)

The code

The code, as always, is available on my Github page: https://github.com/akleemans/bejeweled-bot

Summary

With under 200 lines of Python, one can write a fairly good bot which achieves scores of over two million points (with some special gem).

In general, it’s quite easy to write a Bot for a game, especially when certain conditions are met:

The game situation should be easy to recognize/read by the program
The input to be able to “win” the game should be fairly simple, such as key presses or simple mouse drag and drop

More complex games like Angry Birds require much more sophisticated algorithms for both recognizing the situation and even more for performing a complex action and I don’t think someone has tried to write a bot for it, although it would be surely possible.

Happy hacking ;-)