CubeCrasher

I haven’t posted anything in a couple weeks so I thought I’d throw something up. What have I been up to? Midterms, work, and a side programming project which is an automation program for a little Facebook puzzle came called Cube Crash. I call it the CubeCrasher.

The game Cube Crash itself is fairly simple. You’re given a set of colored blocks on a nice grid. Blocks in a group of 3 or more with the same color can be clicked on and eliminated. The goal is to eliminate enough blocks to move onto the next level, and also get a high score, which is done by eliminating large groups of blocks rather than small.

Scoring is based on the formula: n^2 + (n+1)^2 + (n+2)^2 + (n+3)^2 + (n+4)^2 with n-2 being the number of blocks you eliminate with a click. Not sure why they chose this sequence, but it basically to get a high score you need to create large groups of blocks to click.

CubeCrasher Algorithm

The first thing CubeCrasher does is take an input for the number of “blocks left”, which it can then compute total blocks – blocks left to figure out the max number of blocks that can remain and still level up. It then takes a screenshot of the game and checks the pixel color in the center of each block, storing the results into a character array which gives me an internal logical representation of the game to manipulate. This is done using the Java.Robot library (quite handy for automation).

The state of the game is then put into a GameStateNode object, which consists of the game state (the character array), a LinkedList of groups of blocks that can be clicked on, a scoreSoFar variable, and a LinkedList of children. This becomes the root of a tree of all the possible solutions of the game. Each child represents clicking a different set of blocks.

My original idea was to brute force an optimal solution to each of these little levels of blocks. I quickly found that it seems fairly impossible given the size of the solution space though. In some cases you can do as many as 20-30 clicks to eliminate all the blocks. A very rough estimate is to say that everytime you click a group of blocks, there is one less group you can click, which would give between 20! and 30! game states. 30! has far more 0’s in it than I know how to pronounce, and would take around 1.3*10^18 years to compute using a single processor and my current program. This is of course a very rough estimate, but long story short, a pure brute force solution to a full grid of blocks is fairly impossible. Once you eliminate maybe 1/3 or 1/2 of the blocks, then you can actually find an optimal solution to your current state within a reasonable amount of time.

My original program was a nice recursive tree algorithm that, if left long enough, would go off and compute every single possible state and return the game with the highest score. Unfortunately due to the size of the solution space, what would end up happening is that it would go 20-25 moves deep and then sit there spending all of it’s computation time figuring out an optimal solution to the last 10 or so moves. I also wasted a lot of time computing all the possible children of every state even though I didn’t use any of them, and I simply checked for groups of blocks starting at the top left corner and moving down. This meant that it never actually got to game states where the bottom blocks were clicked first.

Version 2 of the algorithm consisted of adding a lot of randomness. The algorithm itself was a lot simpler to code though. First it creates a root GameStateNode by taking a screenshot as before, but instead of finding all the groups from the top down to the bottom, I make a list of 0 to 13 for the x values and 0 to 12 for the y values and shuffle them before iterating through and finding groups. This makes it so when finding groups, it goes in a random order. I set a counter variable so after checking some number of states it would stop the current path through the tree. I then repeatedly called this function in order to traverse random paths down the tree, but actually compute all possible states of the last couple moves (just because I set the counter value to 100 or 1000). This algorithm is a bit slower than before, but the results score wise are much better. This was also trivial to make multithreaded and get a good 40-50% speed boost by using both cores of my Intel Core 2 Duo, since I’m not actually checking if I’ve traversed a certain path down the tree before. It’s assumed that the solution space is so large, the tiny fraction of it I’m randomly exploring won’t contain too many repeats, and that recomputing those repeated paths down the tree would actually be faster than checking every single path if I’ve done it before.

What’s the result? A score of 144,835 after a couple games. This was high enough to put me on 2nd place for the week, but not on the all time score list which is my goal. It seems around level 13-15 the game gets to the point that there’s simply no way to continue. I let the algorithm run overnight once, computing over 8 billion possible game states, and didn’t find a single one that would eliminate all of the blocks and let me move on. This leads me to believe that I either have to focus on getting higher scores on the beginning levels, or fully automate the program so it will just play many games in a row and hopefully get lucky on one and get a high enough score to make it into the 200k+ all time high score list. There are also some optimizations I can do on the algorithm to speed it up a little, and perhaps when I have some time I’ll work on a version 3 of it that actually takes into account some sort of strategy for the first moves (like favoring deleting one color at a time, or the color with the most/least blocks).

Source code to be posted later.

n^2 + (n+1)^2 + (n+2)^2 + (n+3)^2 + (n+4)^2.