priority queue

[Nick Perkins]

Thanks to all who replied!
(I have been away from the computer for a couple of
days--graduation,parents,etc)

I have a first version of the program working now, using the heap.Heap
mentioned by Alex.  The heap works fine for now, but I will keep in mind the
other possibilities.

The game/puzzle that my program solves is Sokoban.  Sokoban is Japanese for
'warehouse-keeper'.  The task is to push a number of square blocks through a
maze-like area, until all blocks are on designated target squares.  I did
this project for AI class last fall.  I became completely absorbed in it for
about three weeks, and came up with some (IMO) clever optimizations,
including a custom compression routine for states, and a custom hash
implementation for states.

The program never actually used up available ram because the nature of the
game is that there are many re-occurences of the same state, which can be
discarded.  Due to another optimization that I came up with, a re-occuring
state may actually be found with a lower g value than the existing state,
and should therefore replace it.

So, yes, I need to detect repreated states (many of them).  For now, I am
using a dictionary, in tandem with the heap.  I need to key on two values:
one is the sokoban position, a tuple(int,int), but the other is a
Numeric.array of Int, containing either 0 or 1. (the positions of the
blocks).  I am not sure if that array is 'the way to go' or not, but it
keeps things simple, for now.  So I need a hashable value out of the
Numeric.array....

I am currently using:
def unique_hash(soko,blocks):
    return (soko,blocks.tostring())

but I could also try:
def unique_hash(soko,blocks):
    return (soko,tuple(map(tuple,tuple(blocks))))

(works like...
>>> a
array([[ 0,  1,  2,  3],
       [ 4,  5,  6,  7],
       [ 8,  9, 10, 11],
       [12, 13, 14, 15]])
>>> tuple(map(tuple,tuple(a)))
((0, 1, 2, 3), (4, 5, 6, 7), (8, 9, 10, 11), (12, 13, 14, 15))

..but with zeros and ones, of course.

(...seems strange, but maybe as good as anything,..?)


So I have a heap for the queue, and also a dict, running in tandem.  Odd,
but it works.  I used a similar method in C, which worked because this
particular A* problem tended to run for a long time without using up memory,
so speed was more important than space.

When I did the C version, I found that my biggest improvement in performance
came from changing the way I generated new states.  Originally, I would
generate a new state for each move of the sokoban.  This lead to much waste,
as the program tried every possible way to walk accross an empty space.  I
decided to skip all those steps, and just figure out how many would be
needed to get to the next block.  Specifically, not generating states in
which the sokoban has merely taken a step, but only those where he pushes a
block, allowed the program to run up to a thousand times faster (or more),
for the problem sizes I was working with.  Since the problem is to find the
shortest number of steps (push or not), to a solution, the number of
intermediate steps needed between states is calculated separately, and that
value is added to the g-value of the new state. (Hence the need to sometimes
replace a state in the queue: a shorter path to that state can be found at a
later time).

Another useful thing was checking for 'deadlock' condiditions: situations
where two blocks are pushed together against a wall, making them impossible
to move further.  This pattern matching can be expanded to find larger
patterns that also cause deadlock, but I have not done that (yet).  Another
thing I have not tried is using dynamic techniques to save solutions to
'mini-problems': parts of the full problem, possibly recognized as patterns.
And of course, any 'static analysis' of the map (maze), is more-or-less
'free' in the long run, (runs once), and so can get as involved as you like,
while not hurting performance.

It's a seemingly simple puzzle, which actually turns out to be quite hard
(NP hard, i think).  It is the type of problem that you can think about ever
 more deeply, until your head hurts. It sure is fun, and will keep me
thinking until I get a job and have to divert my attention.