Our program uses IDA* as the basic search algorithm. Since IDA* itself is not very smart, a lot of enhancements are necessary to allow our program

You can download the source now: http://www.cs.ualberta.ca/~games/Sokoban/Src

Name of Enhancement | Description | Effect on Tree | # Problems Solved | Paper Reference |

IDA* | Iterative Deepening A* can be pictured as a depth-limited, depth-first
search algorithm that uses the means of a lower bound estimator (heuristic)
to prune parts of the tree that cannot contain a solution with the current
depth limit. The depth limit is increased, if no solution was found for the
previous limit - hence iterative deepening. |
0 | IJCAI-97 | |

Minmatching | MinMatching is a sophisticated lower bound for how many stone pushes are
needed to solve an arbitrary maze configuration. It uses an algorithm that
solves the minimum cost perfect matching in bipartite graphs. To
update such a matching when a move is made, we need to find negative cost
cycles in that bipartite graph. |
Compared to any other (worse) heuristic, IDA* can cut branches in the search tree earlier, resulting in smaller search trees. | 0 | IJCAI-97 |

Hash Tables | Hash tables (or Transposition Tables) are a means to avoid revisiting positions that can be reached via different paths. Hash tables also eliminate loops in the search paths. | Large reduction in size by removing identical subtrees. | 5 | IJCAI-97 |

Move Ordering | Move Ordering sorts moves before searching them. Since IDA* searches all but the last iteration's trees exhaustively, savings are only to be expected in the last iteration. Since the last iteration is potentially the largest, the savings can be substantial. | Savings in the last iteration. Possibly one path to a goal explored only - essentially eliminating the last iteration. | 4 | IJCAI-97 |

Deadlock Tables | Deadlock Tables are a special instance of pattern databases. It contains the status (deadlock or not) of all patterns of stones, walls and empty squares in a 5x4 region. | Some parts of the tree with no solution because of deadlock are removed. | 5 | IJCAI-97 |

Tunnel Macros | Tunnel Macros essentially treat long tunnels as one square. Tunnels consisting of articulation points can be handled more aggressively. | Tree depth is cut. | 6 | IJCAI-97 |

Goal Macros | Goal Macros are invoked by the search when a stone enters the goal
area. Goal macros push stones directly to the correct goal square. This
method can potentially cut solutions. |
The tree depth is further reduced. | 17 | IJCAI-97 |

Goal Cuts | When a stone can be pushed to a goal square using a goal macro, the program assumes that to be a save move and makes only this one move, ignoring alternatives. | The branching factor of the search tree is reduced. | 24 | IJCAI-97 |

Pattern Searches | At nodes that are deemed dangerous (by a heuristic) the IDA* algorithm invokes a speculative search that tries to identify conflicts among limited subsets of stones that results in inefficiencies of the lower bound. These subsets of stones are stored as patterns and reused throughout the rest of the search to improve the lower bound. | Improved lower bound leading to vast reductions is search tree size. | 49 | AAAI-98 |

Relevance Cuts | Instead of searching all the possible moves at interior nodes, some
nodes that are not relevant to previous moves are cut. |
Further decrease in effective branching factor of the search tree. | 51 | CG-98 TCS-99 |

Overestimation | Instead of using a lower bound as a heuristic estimate of the distance to the goal, a realistic estimate that sometimes overestimates the distance to a goal is used. | Further cuts in the tree, since IDA* still treads heuristic values as lower bounds to cut the search tree. | 54 | IJCAI-99 |

Rapid Random Restart | Be impatient: When you think you are stuck in a search, restart and scramble the move ordering. Scramble progressively for a maximum of 8 attempts per IDA* iteration. Then, assume there is no solution for this threshold, increment threshold. | Avoid getting stuck in hopeless situations. If the search wastes lots of effort in a search tree, we are on the wrong track (move ordering is off), try it in a different part of the tree. | 57 | unpublished |

University of Alberta |
Computing Science |
Games Homepage |
Sokoban Homepage |

Please mail feedback to games@cs.ualberta.ca Last modified: