Solving the Gridlock Game

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.

I think the best idea posted is to use brute force, but recognize previously encountered board positions.

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 :)

Maybe look at this as trying to recursively solve subproblems.

First try to move the blue block one space closer to the goal. If it is blocked, try to move the block in its path out of the way. There may be two different ways it can be moved, so treat each direction as a subproblem, and apply this algorithm recursively (to the task of moving the block the number of spaces needed to clear the way for the blue block). Then move the blue block. Keep repeating this until the blue block has reached the goal.

Now the tricky thing is what to do if you need to move the blue block (or whatever block we're currently trying to move) backwards in order to clear its path forward, since then we might end up freeing the square that was ahead of it, but then when we're done it might be further back and blocked by something else...

Maybe just allow the block to be moved backwards and blocked in this fashion, but whenever trying to move a block by one space, remember the state of the board (and also which block we were trying to move) so if that exact situation comes up again the recursion terminates to avoid cycles. At that point, the algorithm backtracks to one of the earlier decisions (to either move a block up or down, or left or right) and chooses the other direction.

I wonder if there are boards for which this algorithm wouldn't work...

Also I've found that the more standard name of this game in literature is "Rush Hour", since that is the name it was first sold under. wikipedia entry on Rush Hour (board game)

A* is never less viable than Dijkstra's algorithm; if you can't think of a good heuristic, just use h(X)=0. In this case, the heuristic could simply be the distance of the target block from the goal. Obviously this is nowhere near an exact heuristic. Nevertheless, it's still admissible (and consistent, for that matter), so it can't hurt, and might well help. Never underestimate the advantage a bad heuristic has over no heuristic.

Vorpy, thanks for the link. It looks like there is a solver that implements a brute force breadth first search.

Sneftel, can you think of a good Heuristic for this game?

for the heuristic to be admissible, it should be the least cost possible to get to the solution, so I would suggest as a starting point:

h =
distance from car to exit
+
for each perpendicular car/truck blocking the exit, the distance it would have to move to get out of the way

what he said. [grin] Usually the best heuristics are (a) ridiculously oversimplified, and (b) cheap and obvious to evaluate. Don't fall into the trap of making your heuristic too detailed and smart: It can make proving admissibility more difficult, and spend time giving A* information it doesn't need.

Genetic Algorthimn might be faster than a brute search.

Quote:

Original post by bugboy Genetic Algorthimn might be faster than a brute search.

I hope that was a joke.

I have to say I think most of the answers to this are incorrect, so far. With the exception of the 'subproblem' idea, I don't think that anyone has described a viable "human approach" other than brute force, and that's why I don't see anything more than the human approach coming out.... Then there's the A* method. TBPH, I'm not sure what that is. If it's the hash method, then I think it's the same as the brute force method, right?

Anyway, whatever.... Here are two good ways to solve these puzzles that could probably be adapted to AI.

First off, you will need to be programming some 'brute force', but before you do that, you're going to have to give the computer something more to work with than the pieces, the board, and where the blue peg belongs....

STEP 1
Either:
A) Have the computer calculate viable end states for the board, itself.

or

B) Have the computer calculate which pieces need to be moved such that the goal can be reached, and then have the computer eliminate the closest possible end-of-the-line scenarios.

Considering A:
A heavily populated board has only 12 pieces on it. Just knowing the pathing and understanding that pieces are not allowed to overlap, a computer can descover an end-desired result. There are usually only 2-4 good end states. Most of the time 2-3 of those are reachable states.

Considering B:
It helps a lot to know the closest possible fail states, in my opinion. If you can figure those out, then you can see the core problems with the board. Example: if two 3-tall pieces need to touch the bottom of the board for you to reach your goal, but there is a 3-wide piece, then you know the blue piece must be moved past the first 3-tall piece before the second 3-tall piece is put into place. Knowing this quickly eliminates hundreds of moves from any game where there are two 3-talls and a 3-wide.

Step 2
Following A:
Now, you need to have the computer solve it. The issue I see with the proposed method, which is just 'brute force', and very similar to my method, is that it is a ground-up method. You need a sky-down approach. Discover which moves are necessary to bring you to your end state instead of which moves are not. When I look at a board, I always think to myself, "I need to make the blue piece move. To do that, I need to move this piece out of the way, and to move this piece out of the way, I need to move this piece up and these two pieces over." Rather than, "I can move these three pieces. Which one is best." I can't know which move is best until I know what belongs where.

Following B:
Basically, the same principles apply. If you're trying to find the closest fail states, though, you need to look at the white space more than the pieces themselves. Notice the possible positions pieces can live in. Sometimes a 2-tall piece can be either above or below a 3-wide. You need to decide on whether not victory is achievable while the 2-tall piece is above that 3-wide and whether or not victory is possible while the 2-tall piece is below. You'll sniff out the end states that do not work, and you'll discover when it is impossible to move that piece out of a fail end state. Often, a piece needs to be moved into a successful half early in the game; however, there are times when a piece must be kept in fail space until you are about half way through, and then it needs to be transferred. So, you need to account for time, not only asking which pieces belong where, but also asking "... at what point in the game".


Here's the path I recommend:
1) Find the possible end states. The final 3-tall is out of the way, and the blue piece is clear.
2) Find the possible board configurations where pieces do not obstruct the main path. 2-tall pieces need to be all the way up or at 0-3y (where the bottom of the board is 0y). 3-tall pieces need to be all the way down.
3) Discover the states in which all points on the path can be simultaneously open, if there are any. If not, discover which parts of the path cannot be simultaneously open and mark these as important moves.
4) Discover how to move the blue piece to the left wall. That should be your start state in every game.
5) Work backwards from a clear-path state to discover where pieces need to be such that the path can be cleared. Make a note of all possible states that clear a path for the blue piece to move forward.
6) Work backwards from the second main-path clear state to each of the first main-path clear states. Exclude any impossible first main-path clear states from the solution.
7) Repeat steps 5 and 6 for the 3rd clear state. Repeat them for the 4th clear state.

Not having read the entire thread, this seems awfully similar to the 15 puzzle (sliding number puzzle). That can be solved with a search algorithm with the heuristic being the manhattan distance that each block needs to move to its appropriate spot. In this case, if I understand correctly, we only have one block that we are concerned with getting to a goal state. Therefore, the heuristic is how many moves it would take to get to the goal if there were no other obstacles.

Coincidentally just read about this problem recently in the book "Evolved to Win" http://www.moshesipper.com/etw/.
Apparently its quite a hard puzzle to solve. The book gives the most recent best efforts based on genetic programming.
Chapter 10 is pertinant