OddThinking

Introducing the Puzzle

Virus 2 is a flash game with a disturbing name, but quite simple game-play.

On a grid of randomly-coloured hexagons, you control a contiguous area of like-coloured cells. You can change the colours of every cell under your control, and where you match the colours of neighbouring cells, you absorbed them.

The aim is to absorb all the cells on the 20×16 playing board in as few moves as possible. (As the game cycles, the target count drops until you fail to meet it.)

Go ahead and play it for a while. When you get back, it will be time to try to truly solve it.

Rules of Engagement

So how do you go about solving it? The obvious solution is a brute-force search. But I am a bit over that right now – there’s no finesse.

So, I decided to aspire to some rather arbitrary rules of engagement. I wanted to maintain the algorithmic interest.

The Rules

• The solver algorithm should be based on examination of the current board state. It should not do any exhaustive searching. (I didn’t want to be too limiting, so I permitted myself one or two moves worth of look-ahead if I needed it.)
• Each move on a given grid should be assigned a metric value, and the highest value should be chosen as the next move.
• The metric algorithm should consist of the weighted averages of a number of sub-metrics. This was an design choice based on elegance rather than appropriateness, and I reserved the right to revisit it, as the solution became more clear.
• Sub-metrics that I came up with included: number of neighbour cells of that colour, the least recently used colour, some function of the percentage of cells of that colour that are neighbours, the number of neighbours to the cells of that colour that are neighbours to the virus (effectively, looking ahead 1 move.) As I discovered which sub-metrics worked, I expected to come up with more.
• While I wasn’t allowed to search during the puzzle-solving phase, I was allowed to search during the software-development phase. My interesting idea was to search through the space of weightings of the sub-metrics, finding the best overall metric that combined the advice of the sub-metrics. I wanted Simulated Annealing and everything! Once the best weightings were found (which could take a lot of processing time,) I would have the parameters to plug into the algorithm (which would then execute quickly). That algorithm might not find the optimal solution to a particular puzzle, but it would, on average, quickly find good (perhaps great?) solutions.

Again, these are rather arbitrary restrictions designed to make the software solution fun to produce, rather than strictly finding the optimal solution to a given problem.

Chatting to Andrew D., who introduced me to the puzzle, I learnt that he solves the puzzle (by hand) in a number of phases. For example, in the early phases, he aims to grow the virus towards the center. In the middle phases, he concentrates on growing the virus as quickly as possible. My arbitrary restrictions largely preclude me from such a solution.

Setting a Goal

What’s my goal?

Well, my goal isn’t to find the optimal solution for any puzzle. If I wanted to do that, I would do a search.

My goal isn’t to find the best ever solution to any puzzle – e.g. “Look, I solved this is 20 moves!” There’s too much dependency on the random configuration of the puzzle for this to have meaning. A puzzle could be solved in zero moves if you are lucky enough to have every cell the same colour.

So, I guess my goal is to play better than a human player. It seems an expert human player solves the puzzle generally in mid-to-high-twenties. If I can average, say, 25 moves, I shall declare it a success.

Implementation of the Basic Game Rules

I created some familiar data-structures. Grid objects represents the grid; it is a container of HexCells. A HexCell object represents on cell in the grid. It knows its colour, co-ordinates and neighbours. Given a GameWindow object, a HexCell can render itself graphically.

This was largely based on my experience with Kakuro, Nonograms, etc.

After a lot of high-school geometry, here’s the result – it is an 8×8 test sample.

Pretty, isn’t it!

You will notice the “virus” in the bottom left. Unlike the original, I always colour the virus black. It’s real colour is irrelevant to the puzzle, and I thought making it distinct would help.

From Hex Cells to Clusters

The next step was to abstract away from individual hex cells. A cluster is any group of adjacent cells of the same colour. They work together. So rather than dealing with cells, the final algorithm manipulates the clusters.

One key advantage here is that the number of nodes that the algorithm must deal with is reduced from (16×20=) 320 to an average of 200. Another is that it is easier to work out the true value of matching a particular colour.

Initially, each cell creates its own cluster with a unique id and a colour. The cluster is now delegated the responsibility for storing the colour on behalf of the cell.

Then the cell informs the clusters of its neighbours, and the clusters start to merge. If a cluster finds its neighbour is the same colour as it, they merge together, giving control to the lower numbered cluster.

Each cluster still exists after a merge, but when asked for its data (e.g. by its corresponding cell), it refers to its associated cluster recursively. (A cluster keeps a cache of its best associated cluster so it doesn’t have to recurse through the entire merge history each time it is accessed.)

The picture isn’t quite so pretty now. The numbers represent the co-ordinates of the lowest numbered cluster associated with that cell. You can see neighbouring cells with the same colour all share the same cluster.

The virus cluster is represented by “****”.

Also on this diagram, there are thin white circles around the cells in “susceptible” clusters. Susceptible clusters are the clusters that are direct neighbours of the virus cluster. They are the ones that may be absorbed in the next move.

First Sub-Metric: Random

Before I could write the bit metric that combined all the sub-metrics, I needed some sub-metrics to base it on.

The first one was a “control” sub-metric – random choice. I wrote a function that, given a grid, randomly chose one of the colours of a susceptible cluster.

Not only was this a quick test sub-metric, but I hoped to find, during the parameter searching phase, that the random metric was weighted very low by my searching algorithm. That would provide some evidence that the searching algorithm was working.

Using the Random sub-metric alone, I ran a sample of 500 runs. It showed a mean solution time of 41.0 moves (ranging from 29 to 59 moves).

End Of The Line for the Graphics

About this point, all the work I did on the graphics was discarded. It was useful, because it helped me debug the clustering, but now it no longer had much point, and just slowed down the execution.

Before I go on the ignore it, here is one more image – a full-sized puzzle mid-solution.

Second Sub-Metric: Least Recent

Next, I implemented an algorithm that I thought would be useful. From the choice of susceptible cluster, it selected the least recently chosen colour. It makes intuitive sense that the least recently chosen colour is likely to have accumulated the most nearby neighbours. It was also rather simple to implement.

Using the Least Recent sub-metric alone, I ran a sample of 500 runs. It showed a mean solution time of 37.6 moves (ranging from 25 to 49 moves)

That’s a good improvement already over the Random sub-metric baseline.

Third Sub-Metric: Most Neighbours

The next algorithm was the most obvious one: chose the colour that has the most matching clusters nearby.

I hoped it would supersede the Least Recent used algorithm by using facts rather than heuristics to find the colour with the biggest immediate growth.

Using the Most Neighbours sub-metric alone, I ran a sample of 500 runs. It showed a mean solution time of 33.2 moves (ranging from 25 to 41 moves).

That’s another good improvement, and it is reflected not only in a smaller average, but a smaller range. It is a more consistent result, which is reassuring.

Fourth Sub-Metric: Most Neighbours’ Neighbours

I had given myself permission to use some limited look-ahead. It was time to exercise that permission to implement a single move look-ahead.

The algorithm chose the colour of the neighbouring clusters that themselves had the most neighbouring clusters. That is, what is the best move this turn to maximise the best move next turn?

This sub-metric was still a bit naive. It didn’t work out “If I go Blue this time, I will have 5 Green neighbours, so that’s the best move.” It worked out “If I go Blue this time, I will have 25 neighbours, so there is probably at least one move that is good from there.” The look-ahead heuristic was simplistic.

Using the Most Neighbours’ Neighbours sub-metric alone, I ran a sample of 500 runs. It showed a mean solution time of 27.8 moves (ranging from 21 to 34 moves).

That was a good improvement again. A very good improvement. I wasn’t still expecting big jumps like that at this point – basically, it is already a better player than me (I’ve only player about 10 or 15 games, manually.)

In a way, this was a disappointingly high improvement. Boring, old look-ahead was proving to be very successful. I guess that tells me what the next algorithm should be.

Fifth Sub-Metric: Most Neighbours’ Neighbours’ Neighbours

I went ahead and implemented two levels of lookahead. What colour’s neighbours have the most neighbour’s neighbours?

Again, this sub-metric was naive. It wasn’t working out “If I go Blue then Green I will have 5 neighbours.” It was working out “If I go blue, and then add up all the neighbours of those neighbours, I get a total of 15 neighbours.”

Nonetheless, this sub-metric had me feeling a little bit dirty. Look-ahead is like searching, but wearing a leash so you don’t go too far. Two levels of look-ahead (in a puzzle that only requires 20-30 moves) is just starting to smell a little bit exhaustive.

Using the Most Neighbours’ Neighbours’ Neighbours sub-metric alone, I ran a sample of 500 runs. It showed a mean solution time of 24.9 moves (ranging from 20 to 31 moves).

Note: 24.9 < 25 moves, which was my original target.

Conclusion

What a let-down! I already reached my goal and I didn’t need to implement any parameter searching, simulated-annealing, parameterised sub-metrics or nothing.

I just had to stray towards the dullness of lookahead (which is just a cut-down version of an exhaustive search). If I wanted to improve it any further, I knew what I needed to do. Make the look-ahead less naive and let out the leash to another level of look-ahead.

Boring.

I stopped instead.

I declare this a fizzer. I reached my stated goal, but without enough fun.

One more pretty picture before I go – a histogram showing the results in more detail.