Most people living in Auckland would likely agree that it would be a bad thing if their city was destroyed by gigantic ancient sea creature whose mind is both terrifying and incomprehensible to us mere mortals. Imagine a scenario where portals suddenly appear around the city spawning all manner of hell beasts. What could we do to protect mankind from the unwitting use of dangerous knowledge which could cause such events? Luckily, this year’s ICFP Programming Contest 2015was set up to find algorithmic ways of preventing these imminent disasters.

A few developers from Movio got together to take part and save the world! Myself, Jonathan Chow and Nicolas Maquet formed our team for the 18th ICFP Programming Contest which ran from 7 - 10 August with people participating from all around the world.

The opportunity
The challenge consisted of finding command sequences for a Tetris-like game that would simultaneously score points by clearing lines and contain specific sequences of "power words". The game had three main concepts:

• The board, consisting of a hexagonal grid where each cell could become occupied as units are locked into position
• The units, consisting of various shapes with a pivot point around which the shapes can be rotated
• The source, which determines the order in which the units appear on the board

Example board was taken from icfpcontest.org

The command sequence we generated would indicate how the units would be moved on the board and locked into position. An example command would be "palb" which would move a unit west, south west, south east, east. To add to the challenge, if the command sequence spelt out specific secret ‘power words’ then bonus points were awarded. Finding what sequences were considered ‘power words’ was also part of the contest. For instance "ia! ia!" was a power word hidden in one of the problem boards in its initial layout.

Since nothing beyond the problem specification and problems was provided we initially set out to create a simulator.  We found this reference created by Red Blob Ganes on hexagonal grids to be extremely helpful in explaining how to do the math involved. Creating the simulator let us visually verify command sequences and discard commands that broke the rules of the game. It became the central piece we used to find good commands.

Searching for magic

Once we had a working and reliable simulator we needed to find command sequences that gave us the highest scores. We divided this into four parts:

• Find possible locations to place units at
• Rank the locations in order to pick the best one
• Find a path from the spawn position for a unit to the target location
• Replace this path with one that is isomorphic and uses as many "power words" as possible

Finding possible positions involved putting a unit in all positions (and rotations!) on the board and checking if it was still inside the board, then filtering so only positions from which the unit could be locked on the board were returned.

To get a sense of the number of checks needed, a tiny 2x2 board and a simple two-piece unit has 19 position checks but only 3 valid ones (ignoring symmetrical positions). These numbers grow fast when the state space expands.

To rank each location, we developed fitness functions to evaluate the resulting board configuration. Finding good heuristics is essential, and thankfully codemyroad had already found a few good ones for regular Tetris, so we reused those and added a couple more to complement them. We ended up with evaluators for a board's depth, bumpiness, hole count, line fullness, snugness and lines that would be completed. Having holes in the board sometimes makes it impossible to clear lines. Bumpiness can make it harder to find good spots for subsequent pieces. Ensuring lines get more and more full is good since it brings us closer to the goal of clearing lines.

Pathfinding is a fun problem since it can be solved in lots of ways, such as depth- or breadth-first search, iterative depth-first search, or Dijkstra's algorithm. In the end, we chose to use A* since it guarantees to find the best path from A to B according to the criteria you define for what a good path is by varying the cost for different moves and having a custom heuristic to estimate the cost of reaching the goal.

How important is a ‘hole’?

The above gave decent results, but the results varied between the supplied problems. Some boards started out with lots of holes below some initial locked blocks, and because of that our algorithm tended to try to fill out that space before attempting to clear out the initial blocks. We realized that we needed specialised evaluators for each of the different problems. Turns out nature has supplied us with a great example of a way to create specialisation: evolution!

Darwin to the rescue!

We initially tried evolving whole command sequences, but found that it took a very long time to find good ones. To deal with this, we chose to assign weights to each evaluator and optimise those instead. This meant there were far fewer variables involved in the problem. We used JGAP and specified the score for a command sequence generated by a run of the simulator with the supplied weights as the fitness function. The good thing with this was that evaluating each individual weight combination in the evolutionary algorithm is highly parallelizable. The downside is that for some boards finding a good position for a unit could take up to 10 seconds! That meant that a single run of those problems could take over 4 hours. On other problems, we quickly found some decent evaluator weights that enabled us to score in the top 40. In the end, we hand picked weights for the difficult problems and generated command sequences with those.

Power words

Sadly we didn't know our H.P. Lovecraft well enough to figure out many of the power words. For those we did find, we generated isomorphic command sequences (sequences of commands that put the block in the same position but by an alternate route) and tried to insert them in the command sequences we generated. Instead of going as quickly as possible from the spawn position to its goal, this caused the blocks to dance and wiggle before settling in the desired place.

What it looked like and lessons learnt

As a final note, we did spend a lot of time watching the simulator run. So here's a sample run of one of the problems (note the wiggling):

I found it extremely exciting how fast our team could move with a clean slate (and not having to worry about maintenance). Techwise - if you are thinking about using evolutionary algorithms, do make sure that the fitness function is as fast as possible.

All in all the ICFP contest was a lot of fun, however, it did come with an unadvertised sleep-depriving effect! After a tiring but inspiring weekend team Movio was placed 68th out of 315 teams and we’re already excited for next year.