Algorithm and data structure for solving the game "Globs"/flood fill/"FloodIt"

Question

Suggest an algorithm and data structure for solving the game Globs (http://www.deadwhale.com/play.php?game=131). It's pretty fun in a geeky kind of way.

State the time-space complexity (big-O) of your approach in terms of N, the size of the grid (N>=14). Good-enough efficient algorithms with low complexity are preferred.

(MatrixFrog correctly points out this game is also known as FloodIt, and Smashery gave a solution 3 months ago in the link he cites below. All you dudes suggesting pruning/greedy with only 1 lookahead, that gives suboptimal solutions.)

The game generates a random square grid of nxn nodes, where each node is colored one of six colors (Grn=1, Ylw=2, Red=3, Blu=4, Pur=5, Orn=6). Level 1 has 9x9 grid, then n increases each level, up to 14. Each level you can take up to 25 turns or else you lose. On each turn you choose which color to change the top left node to e.g. Grn->Red, such that any connected adjacent (horiz/vert) nodes of the new color get assimilated into a shape, and 1 pt per node assimilated is ADDED to your score. The scoring objective is to complete each grid in as few turns as possible, e.g. if you do it in 16 turns, then your 9 unused moves => 2*9 MULTIPLIER times your total accumulated score.

Obviously there are a ton of ways to decompose this, and the default choice of recursive backtracking with a 14x14 grid is a viable contender; What other types of data structures does this lend itself to? A* ? Don't get hung up on optimality, I'm wondering if there is a "good-enough" algorithm.

(I thought it might be a fun project to code up a robot and get silly-high scores. Although I scored 3.5E+12 all by my fleshware self.)

Answer 1

This game really grabbed my interest, so I spent a couple of days working on it.

The first thing I noticed, is that it is easy to show that after the first board (maybe 2 in some cases), the fastest way to raise the score is by using the multiplier. Because of this, I built a system with the goal of solving each board in the fewest number of steps. I started out wanting to use A* because it is generally built for just these types of search problems... however, this problem still turned out to be a doozie.

When talking about A*, the effectiveness of it really boils down your choice of heuristic estimation. The closer you get to guessing the actual distance, the fewer nodes that will have to be expanded in order to reach the goal. For this problem, I went through a number of ideas for estimation, but most of them broke the A* rule, which is that you can NOT over estimate the actual distance, or else you break the optimality of A*.

There are a few that work however. Others in this thread have posted about just taking the number of remaining colors as the estimation, which is admissible because it cannot over estimate (you have to change colors at least once for each remaining color not part of the main "flood" area. The problem with this heuristic is that it very poorly estimates the actual distance. Take for instance the first move, which generally has an estimation of the number of colors, 6. It often expands into 2 moves, each of which generally has an estimation of 7, and so on and so on. Take this 5 levels deep and for a board size of 10x10, most leafs have an estimation of 11. This heuristic is basically an implementation of a breadth first search until you reach within 4 or 5 moves from your goal. This is not very efficient and in my own tests, the exponents run a much around board size 9, which often requires about 14 moves in the solution. It should be noted my solution was very high level however and not much care was taken to speed things up.

The problem is that A* is really only good when each step makes a significant refinement to the actual distance of the overall solution. Looking at the problem directly, you probably wont find a good heuristic that can do much better than this without over estimating the cost. However, if you transform the problem into another problem, better heuristics jump out at you. The heuristic "number of colors remaining" is answering the question, what is the smallest number of possible moves remaining. To the answer that question, I asked myself "which spot on the board requires the maximum number of steps to get to"? I ended up settling on the answer to "how many steps is it to the bottom right corner" for my heuristic. This is fairly easy to implement by running another A* search that works more like finding map directions and then counting the number of steps in the solution. I realize this is an arbitrary point on the board to select, however it worked quite well in testing and running A* on every remaining point took a fair amount of time on my single processor test machine.

This heuristic alone had a tendency to collapse after the bottom right corner became part of the flooded area however, so the final result was MAX(bottom right corner min steps, number of colors remaining not part of main flood). This was finally able to achieve some very large board sizes in under a second with my high level implementation.

I'll leave the record setting to you.