I’m the teaching assistant for MATH116 this semester and the office hours I originally chose didn’t suit most of my students. To remedy this, I set up a doodle poll asking them which times they could do. I downloaded their responses as an Excel table and exported it .csv (comma-separated values).

Becoming a Champion

My girlfriend’s father enjoys a casual game of Bubble Breaker, he even got into the top 100 players on the website he frequents. Trying to impress/troll him lead me to the following challenge: become the Bubble Breaker champion.

Bubble Breaker

Rules: pop a connected set [blob] of bubbles ($> 1$) to make them disappear and be replaced by bubbles above. When a row is emptied, it will be removed.

Goal: remove $n$ rows and $n$ columns

Utility:

• popping a blob of size $k$: $k^2$
• removing $k$ columns in a single move: $50 \cdot k^2$

Termination: the game ends when the goal is reached or when there are no blobs of size $> 1$

Cheating

Well, as I didn’t want to spend a lot of my time playing Bubble Breaker there was an obvious plan: write a program that plays it for me. To make things a lot easier I asked a more experienced programmer, exFalso to help.

Components

Sensor: a scraper that runs the java applet and collects the data necessary for the controller
Controller: a (limited) depth-first search in the graph of game states armed with awesome heuristics
Actuator: play the game (in the applet) according to the „best” sequence of moves found by the actuator

As for heuristics we planned introduce a number of variables regarding the game state and see how they correlated with high scores.

Moar Cheating

While I was working on the controller, exFalso started working on the sensor. He wanted to use Javascript to get the applet’s position but I thought it would be a better idea to trick the applet into running outside of the browser.

This required exFalso to decompile the applet. The result was shocking: the decompiled code had sensible variable names and was well-formatted. After writing a Swing container for the applet exFalso realised something that would change everything: despite the fact that the applet interacted with the server on each move, it was possible to send an arbitrary high score without playing.

A note on premature optimisation

Prior to discovering that we could “print our own money” we spent a lot of time arguing about the controller: I thought it should be written in Haskell (rather unsurprisingly) and he pushed C++. His argument was that depth-first search was inherently stateful (as well as the whole algorithm) and that mutable linked lists are part of the obvious solution. Even after I convinced myself that this was rubbish, I still spent a lot of time thinking about the difference between using immutable arrays or lists of lists for the representation of the grid.

I think this is a rather striking example of premature optimisation: when you optimise code that won’t even be used in the final “product”.

Finally I’d like to thank Alex and Pete for their advice.

Click for code