Mark Gritter (markgritter) wrote,
Mark Gritter

Problem structure in Globs/Floodit

So, I have an almost-working solver for Globs/Floodit. I left it run last night and it only took about 30 minutes (on my poor little 2GHz Athlon 64.)

This problem instance:


Can be solved in 18 moves, with move 13 looking like this:


The discovery I made while playing around with various possible pruning strategies is that breadth-first search turns up a lot of duplicate states across depths. So quite a few of the positions after N moves are reachable in N-1 moves, and thus can be pruned from the tree.

For example, in addition to the 368,030 states my solver examined at depth 12, an additional 114,772 were rejected because they had already been explored at depth 11. It doesn't seem feasible to keep a complete history, but I could easily check whether new states already existed in the previous generation.

My search strategy so far:

1. Generate all possible states (identified by coverage of the board) at depth 1, 2, 3, ..., M (for midpoint.)
1b. While doing so, prune from depth K each state which was already visited at depth K-1.

Implementation: each generation's set of states are stored in a hashtable of 25-byte entries. 25 = ceiling( 14 * 14 / 8 ).

2. For each of the states in depth M, perform a second breadth-first search, taking each single state as a starting point.
2a. Bound the search depth by the best solution found so far.
2b. Prune using the predecessor set of states as in part 1.
2c. Prune any state which appears at depth M, or at depth M+1 in any subtree visited so far. (Perform this pruning check only up to depth M+3)

Eyeballing the early results suggests M=13 is a good balance between the number of subtrees and the depth each subtree has to be searched. The M+3 bound on (2c) was experimental as well--- the check gets about a 10% hit rate if done up to M+2 but about 5% if done one level further, which seemed like a win giving a branching factor of about 3 on average (5 worst case.) The (2b) pruning does better when the tree is larger, ranging from 5-20%, but doesn't help much at all in the early depths of the second search.

There are better ways to make use of the problem structure, though, so I'm going to try these ideas next:

2d. Visit the nodes at depth M in descending order of their "weight" (number of nodes covered.) The sooner we find a good solution, the more leaves we can prune.
2e. Track, for each state, the number of squares left of each color (6 bytes additional cost.) Prune any state which has C distinct colors left but is fewer than C steps from the best known bound. (Also, as a small optimization, any state with just one color left is guaranteed to succeed in one move.)

There may also be some advantage to starting the second stage with more than one starting pattern at a time--- but then we would have to go back and figure out *which* of the starting states led to the improvement.

Finally, to really get a solution:

3. Perform depth-first search in the space of moves to find how to reach the state S in depth M that was identified with the best solution. Prune any path that occupies a square not in S.
4. Perform depth-first search from S to the solution, bounding at the maximum depth.

Unfortunately I was not able to come up with anything "clever". There doesn't seem to be a dual problem to solve, or some other representation of the problem that permits a known solver in an elegant way. Perhaps with a solver that operates in a feasible amount of time one can look for heuristics that could guide search more efficiently, but my earlier attempts didn't really pan out when I was just guessing.
Tags: floodit, games, programming
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.