The state for a given problem can be described by the position of the player and the position of each of the movable blocks. The walls and empty spaces cannot change, so they are the same for every state of the problem.

To make a zobrist hash key using the player's position and the position of each block, you would xor together the values for the player at his current position and the values for blocks at each of their positions. For each position, you'd have two random values, one for when it is occupied by a player and one for when it is occupied by a block. When the player moves, you can generate the hash code for the new state by just a few xors (for the player's movement and possibly for a block's movement). To compare states for equality, check that the player's position and the positions occupied by movable blocks are the same. The odds of a hash collision are very low, so you won't need to do many equality checks, and when you do find that you've already visited a state you can immediately terminate that branch since you've already found a path at least as short as the current path that leads to that state (assuming the heuristic is admissible).

With iterative deepening A*, you wouldn't have to store lots of states at all. It's just a depth first search, down to the depth of the solution length. With an admissible heuristic, you stop descending whenever you encounter a state where the path length plus hueristic value is greater then the solution length. This can be easy to implement and has an extremely small memory footprint, while still finding optimal solutions and using a hueristic to reduce the size of the search space. In fact, the only advantage of A* over IDA* for this problem would be A*'s ability to recognize states for which it already has a shorter path.

Thanks for the clarification on zobrist hashing 8) I'm going to try implementing it today.

I use the manhattan distance heuristic, which I believe is admissible in this case. I also think I use some form of iterative deepening A*. As you describe, I don't expand nodes where f > maxMoves. Unfortunately, this doesn't work quite as well as you'd think. Most levels have a very large maxMoves. Like around 150~200. One level even has 616 :X All large boards are 21x21 which means the largest manhattan distance you can get is 42. In other words, you need to move a whole bunch of times before f > maxMoves and you can start cutting down those branches. The worst part is that the algorithm has likely made a mistake in the first 1-10 moves, it takes forever for the branches to exhaust and find the correct path :X

I think hashing states will be a huge improvement though, I imagine many many redudant states are produced by pushing blocks back and forth. Or at least I hope :P

The only other thing I can think of is using a better heuristic. Do you know of any other admissible heuristics? I might try making one up. Something that basically increments the manhattan distance when it decides there are walls between you and the goal.

One heuristic that comes to mind is the shortest distance from each space to the goal, ignoring movable blocks. The boards are fairly small so each of these distances can be computed in advance.

Some techniques developed for sokoban might also be useful, since sokoban has the same mechanics as this game, just a different goal.

The solution length of the puzzle with a number of the blocks removed is also an admissible heuristic, since removing blocks can only make the path shorter. Maybe solve the puzzle with some of the blocks removed at random. Or solve a puzzle where all the blocks greater than or less than a certain distance from the player are removed. I think that the path lengths for solving for the number of moves required to get a certain distance from your current position and then adding that to a solution where all the blocks that are within that distance are removed minus the chosen distance would even be admissible.

Vorpy's comments have triggered another idea from me that might speed up your solver. Throw away your progressive search (i.e., search from the start node) and perform a regressive search (i.e., searching backwards from the goal state.

You can use a Distance Transform (regressive flood fill) for your search rather than A*, since you know that the heuristic cost for A* is going to be a gross underestimate on most boards and hence not useful in directing search. For the small boards the DT is very quick since the goal is known and fixed in time and thus the additional cost for solving boards that have an open path between the start and goal nodes (over A*) is minimal.

If your DT doesn't find an open path, then you need to consider permutations of the board generated by block movements, as you are doing now. For each permutation, recompute the DT starting at the lowest cost square adjacent to the pre-moved block (or adjacent to the post-moved block if this square is blocked now).

You can trim your search space by stopping your DT at any square that has a cost equal to the permissible plan length, as you are doing now.

You could just do a regressive A* search, or perhaps even a bi-directional and concentrate on regions of the state space that show the most promise for a short path.

Keep us posted as to how your solver goes please.

Cheers,

Timkin

To save memory, instead of storing entire maps, store the movement of a block and a pointer to the previous map (which is just the movement of a block, and a pointer to the previous map, etc).

Then write a function that makes that difference transparent to the end-user code. While this will increase time costs, it will reduce space-costs. And while you can always wait longer, you can't always allocate more memory. ;)

Thanks everyone for the posts.

Heres a bit of an update:
1. Memory isn't a problem for now. I've been using something similar to what NotAYakk suggested for a while now, and it seems to be working. (One board with rearraranged references in each additional state)

2. I implemented the heuristic suggested by vorpy:

"One heuristic that comes to mind is the shortest distance from each space to the goal, ignoring movable blocks. The boards are fairly small so each of these distances can be computed in advance."

This was an excellent idea. The only drawback was a small constant delay added to the algorithm's execution speed, but on average the code is almost 600% more efficient. One level that used to take 10 minutes to solve was done in 60 seconds :O This was a real spirit booster :)

3. I tried to incorporate state hashing into my code, but there is big problem with using this in my implementation. I don't follow a depth first approach, and therefore have a very difficult time "undoing/removing" entries from the hash table if a path has proven to be incorrect. As a result, my naive implementation often blocks the path to the correct solution. I'm still working on this though, I have a couple ideas left

EDIT: I got this working... but the additional overhead causes slower execution on average and it didn't result in solving any of the levels that were previous unsolved.

4. Between levels 1-35, there are only a few the algorithm doesn't solve (just runs forever) If I could get all 35 that would be half way :P

For anyone whos interested, you can take a look at the levels that currently don't solve:

BLUE = start
PINK = movable block
GRAY = floor tile
WHITE = goal
BLACK = wall

Level26 Level27 Level34 Level35

This is the one that used to take 10 minutes:

Level25

---
I haven't gotten around to the more complex ideas suggested by Vorpy yet:

"The solution length of the puzzle with a number of the blocks removed is also an admissible heuristic, since removing blocks can only make the path shorter. Maybe solve the puzzle with some of the blocks removed at random. Or solve a puzzle where all the blocks greater than or less than a certain distance from the player are removed. I think that the path lengths for solving for the number of moves required to get a certain distance from your current position and then adding that to a solution where all the blocks that are within that distance are removed minus the chosen distance would even be admissible."

These heuristics sounds like they are worth trying as well, after that first simple one showed such a great improvement. I will try them eventually :)

Timkin, I have also thought about a regressive search, but I never really pursued the idea. I'm not familar with distance transform, i'll google around to see what I can find.

At this point it seems like I have a lot on my plate 8) Thanks again everyone.

There was one other vague idea I had, but I'm not sure if its worth pursuing. What about partioning each board into sections defined by the walls, not blocks. Then solved each section and turned the problem into navigating a graph (with possible cycles in the solution :X) with much much fewer nodes.

[Edited by - neemo_t on June 10, 2007 5:25:37 PM]