Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

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:

14315140312121
54004452332221
11500053141433
35212250541223
22413323254315
03032322321002
20352100201440
05342453523042
12213545433135
35313453054552
43253500454305
21231554221214
24045233513445
54550121513122


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

XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
XXXXXXXXXXXXXX
X.XXXXXXXXXXXX
.XXXXXXXXXXXXX
XXXXXXX.XXXXXX
XXXXXX...XXXXX
...XX...XX.XXX
..XXXXXX.X..X.
.XX.XXX.XXX...
..X..X...X....
....XX...X....


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
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 20 comments