« Post Index
Aug 22, 2011

Diamond Dash Bot: 1,000,000 points!

Update: My current high score is about 1.1 million, much more than the 480,000 reported earlier.

My wife is a hardcore casual gamer. Her Bejeweled Blitz scores routinely quadruple my best attempts. For a few short minutes, I had the leading score on Google Games' Diamond Dash, which lasted until my dear wife got a score that obliterated mine by a factor of 5. So, I made the logical decision: to write an automated Diamond Dash playing bot to beat my wife. At Diamond Dash.

DD is pretty similar to Bejeweled Blitz, except that instead of swapping pieces, you just click on a group of 3 or more contiguous pieces to eliminate them all. So, the logic is a little easier. Here's what I came up with.

Get the code

Its best score so far is ~480,000: about four times as well as I've ever done myself (and just a hair better than my wife's top score so far). The basic steps are:

  1. Parse a screenshot to get the current board layout
  2. Select a number of non-interfering moves to make
  3. Translate those moves into pixel coordinates and click those spots.

Of course, only step 2 of those can possibly be really OS-independent. I wrote the code on Linux, but with screenshot-taking and mouse-clicking adapted, you could run it on anything.

Taking a Screenshot

1 2 3 4 5 6 7 8 9 10 11 12 13
def take_screenshot():
"""
Use GTK to get a screengrab of the current screen.
 
Returns an (x, y, 3) full-color pixel array
"""
w = gtk.gdk.get_default_root_window()
sz = w.get_size()
 
pb = gtk.gdk.Pixbuf(gtk.gdk.COLORSPACE_RGB,False,8,sz[0],sz[1])
pb = pb.get_from_drawable(w,w.get_colormap(),0,0,0,0,sz[0],sz[1])
 
return pb.get_pixels_array()

This uses the GTK library to take a screenshot. I think I took this from someone on stack overflow, so thank you to whoever that was.

Parsing the Screenshot

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
class NotDiamondDashException(Exception):
pass
 
def crop_dd_screenshot(pixarray):
"""
If there is no stored index, load the reference .png,
find it in the current screen, and get the coordinates.
 
If the reference is not found, raise a
NotDiamondDashException so we know we're not looking
at a Diamond Dash screen
 
If the index has already been stored, just slice the
array to the right parameters.
"""
global TOP_LEFT_INDEX
 
if not TOP_LEFT_INDEX:
# Load it up
ref_pixarray = read_png_to_pixarray('topleft_ref.png')
 
ind = search_for_subarray(pixarray, ref_pixarray)
 
if not ind:
raise NotDiamondDashException("This isn't diamond dash.")
 
 
ref_row, ref_col, _ = ref_pixarray.shape
 
# Add the size of the reference
row = ind[0] + ref_row
col = ind[1] + ref_col
 
TOP_LEFT_INDEX = (row, col)
else:
row, col = TOP_LEFT_INDEX
 
# Diamond dash board runs 400x360 px.
return pixarray[row:row + 360, col:col + 400], (row, col)
 
def read_png_to_pixarray(filename):
"""
Read a .png image into an (x,y,3) full-color pixarray
"""
with open(filename, 'rb') as f:
r = png.Reader(file=f)
out = r.asDirect()
 
pixarray = numpy.reshape(list(out[2]), (out[1], out[0], 3))
 
return pixarray
 
def search_for_subarray(A, A_sub):
"""
Search for A_sub in A, and return the coordinates to it
 
>>> A = numpy.array([[1,2,3,4],[5,6,7,8]])
>>> search_for_subarray(A, numpy.array([[2,3],[6,7]]))
(0, 1)
"""
 
if len(A.shape) == 3:
sub_rows, sub_cols, _ = A_sub.shape
rows, cols, _ = A.shape
elif len(A.shape) == 2:
sub_rows, sub_cols = A_sub.shape
rows, cols = A.shape
 
for i in range(rows):
for j in range(cols):
if numpy.all(A[i][j] == A_sub[0][0]):
if numpy.all(A[i:i+sub_rows, j:j+sub_cols] == A_sub):
return (i, j)
return None

I took a screenshot of the play area, and cropped off a little rectangle corresponding to the top left of the play area. This function searches, very inefficiently, for that exact set of pixels, to orient itself within the screenshot. It only has to find it once, then it saves that location for speed. So, no moving the window! It returns a cropped pixel array of just the play area.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
# Color of each block at 10, 10
COLORS = (
(158, 221, 255), # Diamond
(247, 183, 0), #Yellow
(1, 185, 1), # Green
(186, 115, 255), # Purple
(242, 0, 16), # Red
(6, 104, 253)) # Blue
 
def downsample_pixarray(pixarray, factor=40.):
"""
Get the nearest color index match from the COLORS tuple
from every square.
 
Diamond dash squares are 40x40.
"""
factor = float(factor)
 
rows, cols, _ = pixarray.shape
 
new_rows = int(math.ceil(rows / factor))
new_cols = int(math.ceil(cols / factor))
 
counts = numpy.zeros((new_rows, new_cols))
out_pixarray = numpy.zeros((new_rows, new_cols, 3))
 
# Downsample instead of averaging
for i in range(new_rows):
for j in range(new_cols):
# Get a point from 10,10 in a 40px square, which should be the right color
i_ind = int(i * factor + factor/4)
j_ind = int(j * factor + factor/4)
 
pixel = pixarray[i_ind][j_ind]
 
c = nearest_index_to_color(pixel)
counts[i][j] = c
 
return counts
 
def nearest_index_to_color(color_tuple):
"Get the index in COLORS closest to color_tuple"
distances = [color_distance(c, color_tuple) for c in COLORS]
return distances.index(min(distances))
 
def normalize_color(color_tuple):
"Get the color closest to color_tuple"
return COLORS[nearest_index_to_color(color_tuple)]
 
def color_distance(c1, c2):
"""Get the sum of squares of the difference between two colors"""
return (c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2 + (c1[2] - c2[2]) ** 2

This bit of code takes that play area and reduces it to a single numeric matrix, where 0 is a diamond, and 1-5 are the various colors. This is what the rest of the program operates on. It does this by sampling every 40 pixels, with a 10x10px offset to get something within the color tile. This was chosen instead of the center because the colors are more consistent in the border between the tile bezel and the symbol.

Selecting where to click

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
def find_largest_contiguous_region(countsarray):
"""
Find the contiguous regions in countsarray using the modified
flood count algorithm described in get_flood_count
"""
 
Q = countsarray.copy()
points_checked = []
rows, cols = Q.shape
 
best_score = 0
best_ind = -1
best_point = (0, 0)
 
for i in range(rows):
for j in range(cols):
 
if Q[i][j] >= 0:
score = get_flood_count(Q, i, j, Q[i][j])
if score > best_score:
best_score = score
best_ind = countsarray[i][j]
best_point = (i, j)
 
 
# Generate a nice little display
print countsarray
print "Best score: {0:d} ({1:d}, {2:d})".format(best_score, best_point[0], best_point[1])
 
if best_score < 3:
raise NoPointFoundException("No point found.")
 
return best_point
 
def get_flood_count(Q, i, j, target, replacement=-1):
"""
A modified flood count algorithm.
Makes some assumptions about the input, namely:
 
1. Input array is small enough not to overflow the stack
2. Input array is numeric, and
3. Input array is wholly positive (or at least, has no -1's)
>>> Q = numpy.array([[1,1,2,4], [1, 3, 5, 7]])
>>> get_flood_count(Q, 0, 0, Q[0][0])
3
"""
s = Q.shape
if i < 0 or j < 0 or i >= s[0] or j >= s[1] or Q[i][j] != target:
return 0
 
# Q[i][j] == target_ind
Q[i][j] = replacement
 
return 1 + (get_flood_count(Q, i+1, j, target, replacement) +
get_flood_count(Q, i, j+1, target, replacement) +
get_flood_count(Q, i-1, j, target, replacement) +
get_flood_count(Q, i, j-1, target, replacement))

This uses a recursive flood fill algorithm and modifies it to count instead. 

A big difference between Diamond Dash and Bejeweled Blitz is that the latter penalizes you heavily for misses. Most issues seem to stem from the lag between when the screenshot is taken and when the action is processed; sometimes the board changes in between. Some possible improvements:

A special message

This is where the affiliate links live, but hear me out! I use these two services every day, and I wouldn't recommend them if I wasn't satisfied.

DigitalOcean - Purveyors of fine (and inexpensive) virtual servers. I use DigitalOcean to host Address Bin and a few others; it's my go-to host. Use this referral link for a $10 credit.

AirBnb - I've been living in AirBnbs for a few months now, and plan to for many more. If you've ever wanted to try them out, you can get a $25 discount from this referral link.