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.

779 points richer
This move gets me a delicious 729 + 50 = 779 points

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.

The grand design

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