I recently stumbled upon a small flash game called Gridlock that is a fun puzzle game. Now I'm trying to write a program to solve it. How the game is played The game consists of a 6x6 board with horizontal and vertical blocks of length 2 or 3 and width 1. The objective is to move the horizontal blue block out through the hole on the right side of the board. To do so, you will need to move other blocks out the way. The horizontal blocks can be moved left and right and the vertical blocks can be moved up and down. Writing a program to solve any puzzle My initial attempt to solve this puzzle was with brute force. I started by looking at the initial board and figuring out all possible moves that could be made (There are generally ~4-10 moves that can be made given a board state). Then I create new boards with these states and check if any of them are in the winning state (the blue block is out to the right). If there are no winners, I repeat the process of analyzing all possible moves and creating new boards. The problem with this attempt is that the space we are searching grows too fast. Generally it takes me ~15-50 moves to solve the puzzle. So a conservative estimate of the number of boards checked with brute force (breadth first search) would be 4^15 (could be 10^50 or worse). The next step What I plan to do next is play the game some more and try to figure out the strategy I am using the solve it. And by "figure out" I mean I want to be able to write down in words or explain to someone else steps they can take to solve the game. Once I figure this out, I think it will be much easier to implement an efficient algorithm. Has anyone played the game and come up with such a strategy? Another idea that I have is creating a heuristic to evaluate how "good" a board is. Meaning a board that is only a few steps away from being solved will get a higher score than a board that is not close to being solved. If this was possible then the N best boards could be evaluated (beam search) at each depth in the search tree. The problem with this is rating what a good board is. Usually a better board is one where there are fewer blocks in between the blue block and the exit. This is similar to saying the blue block is closer to the exit on the right side (but not quite - there are slight differences). I think this might run into problems though in cases where you need to make your position worse before you can make it better. Any suggestions on this idea or any other ideas?

From my experience with the game, I don't think rating boards as "good" or "bad" will be too productive. It's pretty difficult to look at a board and judge how close you are to finishing (unless you can actually see the solution). In fact, most of the tricky puzzles are deliberately set up so that there are states which look really good, but are in fact dead ends.

I think in this case, it wouldn't be too hard to just keep track of every possible state of the game. There's (relatively) not that many. If you have, say.. 10 cars, and each of them can be moved to 5 possible positions, that's ~9 million states. Not too hard to handle.

So, step 1: encode every possible state in memory. Then start from the initial state and figure out which states you can reach from that state by making a single move. Mark those states as "reachable". Also, for each reachable state, keep track of the shortest path that was used to reach it.

Then take all the states that were newly marked as "reachable", and figure out which states are reachable from those. Repeat. Stop when your goal state gets marked "reachable", and your solution is the path to that state.

If you want to be more efficient, you could start searching from both the start and the end simultaneously.

It's kind of like your brute force search, except brute force will end up searching the same exact board state multiple times. This method makes sure that each possible board state only gets checked out once.

I believe this kind of programming technique is called "dynamic programming"

I think it could be done with a brute force AI using traditional pathfinding techniques. The fact that each block on the board can only move in two directions greatly limits the number of possible states for each board. The biggest problem with that approach would be having the algorithm recognize when a loop has been reached in the pattern.

Another way to try it would be to consider the shapes of all the pieces given, and to create a set of solutions with those blocks, then to have the algorithm attempt to reach those solutions from the starting point.

You can use A* algorithm. It is originally used for pathfinding. But, you can use it for single player puzzel solving.

For A* you need a good heuristic. The trick is, it's not just brute force. While brute forcing you move in the best possible direction.

Regards.
Varuna.

http://www.geocities.com/jheyesjones/astar.html

Try this one! :-)

As pinacolada said, using A* probably isn't viable because we can't think of a way to evaluate what a "good" board is. If you can think if a good evaluation function I'd be glad to hear it.

For recognizing previously encountered positions, you can use a hash table. For a good and fast hash function, look up zobrist hashing. It's a technique to generate hash codes for game boards that makes it very fast to generate a hash code for a new board that is reached by moving one peice on an old board. For each posible position of each peice you generate a random 32 bit number. The hash code for a board is just the number for each peice on the board XORed together. When moving a peice, you just remove it from the hash code by XORing its current value with the old hash code, then XOR in the value of its new location.

For everyone suggesting brute force:

Do you think this is the way humans solve the puzzle? Commit 9 million states to memory at the beginning, or go through tens of thousands of possibilities each game?

I would think certainly not. So there is guaranteed to be a better algorithm. Above people have said that A* wouldn't work as there is no way to judge the worth of a board, but there must be some rough measure, otherwise we couldn't do it. Sure, they can lead you into easy-looking dead-end solutions, but even with those tricks, the game is still solvable by humans without doing a brute-force ten-thousand possibility search.

Anyone got any thoughts?

Asbestos, I definitely agree with you that there must be a better method than brute force search as we humans can usually solve the puzzle in 20-100 moves. (Although I think it's important to point out that we probably analyze more than a 100 moves in our head and automatically erase the bad ones. I think we are also able to do a good job of remembering moves we already did so we don't end up repeating them or returning to a previous state. This is effectively pruning branches of the search tree that we don't think it would be a good idea to take.)

However, I don't think the human method is necessarily done by rating how "good" a board is. When I try to solve the puzzle, I usually start by looking at the first block between the blue block and the exit. I then try to figure out what pieces I need to move to be able to move that first block, and repeat.

As an example, consider the following game board where the periods are empty space, the B's are the blue block, and the numbers are regular blocks.

. . . 3 3 .. . . 2 . .B B 1 2 . .. . 1 4 4 .. . 1 . . .. . 5 5 . . 

To solve this, I would see I need to move block 1, and to do this, I would need to move block 5. Next I would see that I need to move block 2, and to do this, I would need to move blocks 3 and 4 (and possibly 1 and 5). I also try to make sure that in the process of clearing block 2, I don't move other blocks in the path of the blue block.

Steps: 1. Move block 1   a. Move block 52. Move block 2   a. Move block 3   b. Move block 4   c. Possibly move blocks 1 and 5 - but make sure I'm not moving them back to previous positions where they are blocking B

I think this algorithm could possibly work. This would involve performing a search on the first block in the way, then performing a search on the second block in the way while trying not move other blocks in the way of the blue block. The algorithm would also need to avoid making moves that "reset" previous moves or series of moves.

This approach would probably fail for the more complex cases where you need to make things "worse" before you can make them "better". However, I think its a good first step and once it works well for simple cases, it could be tweaked for the complex cases.

I look forward to trying to implement this, as well as an efficient brute force method after my finals this week. I'll be sure to post my results :)