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.

I made a breadth first solver for this Gridlock game and it took about 0.1 seconds (or less) to solve a puzzle with 700 MHz CPU. So A* isn't really necessary unless you're planning on writing the solver for a mobile phone or something..

Genetic Algorthimn might be faster than a brute search.

I disagree - genetic algorithms are utterly dependent on the quality of the heuristic that evaluates the fitness of a given solution. More critically, this isn't the sort of problem that is easy to encode - how would you represent solutions for this problem as a fixed-length string?

A* isn't completely stupid, even with a crude heuristic - even in it's worst case, it at least avoids checking duplicate states twice, and it will be easy to encode states for the A* algorithm. A GA will need a very clever encoding and fitness heuristic - why suffer by trying to be clever when dependable old A* is far more appropriate?

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.