When faced with a problem in which there is no perfect algorithm and the number  of permutations wouldn't permit doing a full tree search for the best answer, you  may want to consider using a genetic algorithm.  You may be shocked at how  much more intelligent the solution is than what a human could come up with.

Melanie Mitchell wrote a book called Complexity: A Guided Tour which was  released in April 2009.  It contains a chapter on genetic algorithms in which she  describes a simple problem and how a GA is used to solve it.  I implemented a  t-sql solution to the problem in about three hours.  It took 20 minutes to run  about one million simulations.  It came up with solutions that are counter-intuitive  and exceed human ability by leaps and bounds.

Here is a definition of the problem:  There is a 10 x 10 grid surrounded by a wall.   Half of the grid squares contain an empty soda can.  A robot starts in the upper  left square and executes 200 actions.  An action can be to move North, South,  East, West, or to try to pick up a can, or to pick a random direction in which to  move.  The robot can only see five squares, the current square it is on plus the  four adjacent squares. 

The robot scores 10 points for each can it picks up.  It scores -5 points for trying  to move into walls. It scores -1 point for trying to pick up a can from an empty  square.  If the robot executes a perfect run, 50 cans will be picked up without  penalties for a total of 500 points.  It is important to remember that the robot has  no memory of previous moves nor access to problem solving routines.  The  intelligence will be due to an evolutionary process only.

Here is how to implement a genetic algorithm solution:  Generate an initial  population of children.  Test them in a simulator.  Kill off all but the best two  children.  Cross breed those as parents for a new generation of children by taking  a top portion of DNA from one parent and combining it with a bottom portion of  DNA from another parent.  Generally a few random mutations are then introduced  into each child.  Test these children and repeat the process of selection and  replication until a good enough answer occurs.

In our simulation, a square can be empty or a wall or a can.  Since the robot can  see five squares, the number of permutations is 3x3x3x3x3 which equals 243.   Each permutation is a situation in which a gene will determine the action to take.   Our robot just happens to have 243 genes to handle each of the possible  permutations.

Each of the 243 genes is one of six action values to move in one of four  directions, pick up, or move random.  If we take 6 to the 243rd power, we see  that we can have 1.23x10^189 unique children, way too many to ever test in a  brute force manner.  The included script checks only one million evolved children  out of nearly an infinite possible number of children and comes up with an almost  ideal answer.

Run the ScoreRobotFitness.sql script (in the Resources section below) to create the ScoreRobotFitness stored procedure.  It will  be called for each child that is created to score its performance.

Run the EvolveRobots.sql script (in the Resources section below) to create and evolve robots.  Start with 100  NumGenerations and 100 NumOffspring to see results in seconds.  Start with  1000 of each if you want the ideal robot after 20 minutes of calculations.  Copy  the results to Excel for a quick graph on its learning curve.

Run the DecipherDNA.sql script (in the Resources section below) after replacing @s with your ideal robot's DNA to  decipher the rules it came up with.  Most likely it came up with heuristics that a  human wouldn't.  For example, it may have avoided picking up a can in the  current location, preferring instead to move to the left of a string of cans and start  picking them up from the beginning.  Picking up cans from the middle of a string  would make it more difficult to backtrack to the stranded cans at the left.

Most humans would score about 350 after hand-coding the genes and optimizing  for a few days.  I'm not sure a human would ever be able to score as well as this  GA did in only 20 minutes of evolution.  Try implementing a randomly populated  grid, tweaking the generations and offspring counts, allowing diagonal  movements, or varying the mutations and let us know what interesting heuristics  emerge, especially if you can speed up the evolution process.