Our Program - Rolling Stone

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 Rolling Stone to solve more than the trivial problems. The following is a list of enhancements that allow me to solve more of the standard 90 problems. The column "problems solved" shows how many problems can be solved with all the enhancements in this row and above. So just imagine we add all those features when going down the list to a version of the program that becomes better and better.

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: