Mark Gritter (markgritter) wrote,
Mark Gritter

Inspiration fails on Globs/Floodit

I have previously mentioned trying to find an efficient way to solve Globs/Floodit, a solitaire game.

Last night I thought I had an inspiration. Given a 25-move limit, I thought I could do "forward search" to 13 moves, record all positions in an efficient lookup structure, and then to "backward search" looking for matches. Once an (approximate) midpoint move was found, reconstructing the 13 original moves to get there would be feasible.

I coded up the forward search fairly quickly, and it turned out to be as efficient as hoped. Then I realized there was no feasible way to generate reverse moves--- duh! From the solution state, any arbitrary subset of the spots of one color might have been "unstuck" on the (N-1)th move.

So, anyway, here is what the search space looks like for a randomly-generated instance:

===== Depth 1 ===== Found 2 successor states.
===== Depth 2 ===== Found 5 successor states.
===== Depth 3 ===== Found 14 successor states.
===== Depth 4 ===== Found 45 successor states.
===== Depth 5 ===== Found 162 successor states.
===== Depth 6 ===== Found 571 successor states.
===== Depth 7 ===== Found 1920 successor states.
===== Depth 8 ===== Found 6178 successor states.
===== Depth 9 ===== Found 19074 successor states.
===== Depth 10 ===== Found 57487 successor states.
===== Depth 11 ===== Found 171833 successor states.
===== Depth 12 ===== Found 513755 successor states.
===== Depth 13 ===== Found 1533995 successor states.
===== Depth 14 ===== Found 4528198 successor states.
===== Depth 15 ===== Found 12971218 successor states.

It looks like the effective branching factor is about 3 rather than 5. It should be possible to solve the problem from depth 13 or so using bounded DFS from each of the 1.5M midpoints. My algorithm found duplicates but it didn't find dominated paths, so that could help too--- bound the DFS by anything already in the midpoint set. Reverse search, had it been feasible, would really have cut down the search time, though.
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.
  • 1 comment