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. <\/p>\n
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.)<\/p>\n
Go ahead and play it for a while.<\/a> When you get back, it will be time to try to truly solve it<\/a>.<\/p>\n So how do you go about solving it? The obvious solution is a brute-force search. But I am a bit over that<\/a> right now – there’s no finesse.<\/p>\n So, I decided to aspire to some rather arbitrary rules of engagement. I wanted to maintain the algorithmic interest.<\/p>\n 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.<\/p>\n 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.<\/p>\n What’s my goal? <\/p>\n Well, my goal isn’t to find the optimal solution for any puzzle. If I wanted to do that, I would do a search.<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n This was largely based on my experience with Kakuro<\/a>, Nonograms<\/a>, etc.<\/p>\n After a lot of high-school geometry, here’s the result – it is an 8×8 test sample.<\/p>\n Pretty, isn’t it!<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.)<\/p>\n 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.<\/p>\n The virus cluster is represented by “****”.<\/p>\n 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.<\/p>\n Before I could write the bit metric that combined all the sub-metrics, I needed some sub-metrics to base it on.<\/p>\n 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.<\/p>\n 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.<\/p>\n 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).<\/p>\n 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.<\/p>\n Before I go on the ignore it, here is one more image – a full-sized puzzle mid-solution.<\/p>\n 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.<\/p>\n 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)<\/p>\n That’s a good improvement already over the Random sub-metric baseline.<\/p>\n The next algorithm was the most obvious one: chose the colour that has the most matching clusters nearby.<\/p>\n 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.<\/p>\n 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). <\/p>\n 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.<\/p>\n 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. <\/p>\n 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?<\/p>\n 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.<\/p>\n 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). <\/p>\n 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.)<\/p>\n 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.<\/p>\n I went ahead and implemented two levels of lookahead. What colour’s neighbours have the most neighbour’s neighbours?<\/p>\n 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.”<\/p>\n 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.<\/p>\n 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). <\/p>\n Note: 24.9 < 25 moves, which was my original target.<\/p>\n 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.<\/p>\n 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.<\/p>\n Boring.<\/p>\n I stopped instead.<\/p>\n I declare this a fizzer. I reached my stated goal, but without enough fun.<\/p>\n One more pretty picture before I go – a histogram showing the results in more detail.<\/p>\nRules of Engagement<\/h3>\n
The Rules<\/h4>\n
\n
Setting a Goal<\/h3>\n
Implementation of the Basic Game Rules<\/h3>\n
<\/a><\/p>\nFrom Hex Cells to Clusters<\/h3>\n
<\/a><\/p>\nFirst Sub-Metric: Random<\/h3>\n
End Of The Line for the Graphics<\/h3>\n
<\/a><\/p>\nSecond Sub-Metric: Least Recent<\/h3>\n
Third Sub-Metric: Most Neighbours<\/h3>\n
Fourth Sub-Metric: Most Neighbours’ Neighbours<\/h3>\n
Fifth Sub-Metric: Most Neighbours’ Neighbours’ Neighbours<\/h3>\n
Conclusion<\/h3>\n
<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"