Rush Hour Puzzle 475730

Rush-Hour puzzles solved with multiple search algorithms. Brynjar Reynisson and Ívar Björn Hilmarsson Reykjavik University T-622-ARTI February 19, 2008 Abstract To solve the Rush-Hour puzzle, we implemented the Uniform-Cost, PureHeuristic, A*, IDA*, Enhanced-IDA* and RTA* search algorithms. DepthFirst-Iterative-Deepening was also used for comparison. All of the algorithms can handle easy to medium difficult puzzles, but DFID and IDA* can’t solve tougher ones in a timely manner, and RTA* runs out of memory with the implementation used.

This report describes the usage of several search algorithms, that were used to solve multiple Rush-Hour puzzles. The algorithms covered are Depth-First-IterativeDeepening (DFID), Uniform-Cost (UC), Pure-Heuristic, A*, IDA*, Enhanced-IDA* (EIDA*) and RTA*. We describe the data structures used to implement these algorithms, the method used for measuring efficiency and discuss the results found.

1

Method

The task at hand was to implement various search algorithms in Java, having their implementation conform to a predefined interface. Also supplied was a main method, through which specified rush hour puzzles could be run and the performance of the search method measured. A*, Pure-Heuristic and UC search all use the same datastructures and search method, with the only difference being how their cost function is evaluated and what values are put in the open list. The classes added for implementing these algorithms are SearchAStar, SearchUniformCost, SearchPureHeuristic, StateCostMap and StateCostWrapper (source code is found in the src directory). StateCostWrapper encapsulates a state id, its parent state id, the cost of getting to this state and the heuristic estimate for the cost of reaching the goal from the state. StateCostMap extends TreeMap which is a sorted map, and stores integer values representing cost as keys, and arrays of StateCostWrapper instances as the values. This makes it easy 1

1 METHOD

to find the state that is estimated to be the cheapest way to the goal (implemented in the getCheapestState method). A* requires lookup of specific states in the open list. To find these more quickly than running through all the value arrays, StateCostMap internally maintains a map with state ids as keys and integer values. Each such integer represents the estimated cost of the state and is therefore of course also a key in the main map. The StateCostWrapper holding the stateid will thus be in the array that matches the integer value. The purpose of StateCostMap is to be an implementation of the open list, and this is what is used by SearchAStar. SearchAStar implements a standard version of A*, from pseudocode found at http: //wiki.gamegardens.com/Path_Finding_Tutorial. Besides using StateCostMap as its open list, SearchAStar maintains its closed list with a hashmap of state id keys and StateCostWrapper values. SearchUniformCost and SearchPureHeuristic extend SearchAStar, and only override the costFunction and addToOpenList methods from the base class. The SearchIDAStar (IDA*) and SearchEIDAStar (EIDA*) classes use a similar methodology as supplied in SearchDFID. The main difference is that DFID uses depth-bound recursion while IDA* and EIDA* use cost-bound recursion. Both the IDA* and EIDA* implementations use a class named DFS_CRetval, which stores whether a solution is found and the minimum limit for each state of the recursion. Additionally, EIDA* uses a transposition table of state ids and instances of TTEntry, which stores cost, limit and heuristic. SearchRTAStar (RTA*) uses completely shallow search and stores its findings in a hashmap of state ids and state costs, which get updated each round according to standard RTA* implementations. All of the heuristic based algorithms use a heuristic implemented in RushHourHeuristic3. It returns the sum of three variables: the exact cost of moving one’s car (A) to the exit, the exact cost of moving everything out of A’s way (B) and a cost of 2 for each car that’s in the way of those cars specified as B. Measurements were done using the method supplied in the RushHour2 class. The data collected specifies whether a problem is solved, number of steps needed, solution cost, nodes expanded, time taken, as well as the actual solution. All tests were run using JRE 1.6.0_03 on an IBM Thinkpad with 2GB of RAM, using 512MB for the JVM and a 1.8Mhz U. An extra hard puzzle was added to test the algorithm’s efficiency. Here is that puzzle: ######## # CBB# # DDCL # #AAGKL = #EEGKMM# #FHHH J# #F II J# ######## 2

2 RESULTS N 0 0 0 0 0 0 0 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3

Algorithm DFID Uniform-Cost Pure-Heuristic A* IDA* EIDA* RTA* DFID Uniform-Cost Pure-Heuristic A* IDA* EIDA* RTA* DFID Uniform-Cost Pure-Heuristic A* IDA* EIDA* RTA* DFID Uniform-Cost Pure-Heuristic A* IDA* EIDA* RTA*

Solved 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0

Length 1 1 1 1 1 1 1 3 3 3 3 3 3 2 8 8 15 8 8 8 86

Cost 6 6 6 6 6 6 6 11 11 13 11 11 11 8 25 25 39 25 25 25 180

49 116 49

134 303 134

51

136

Expanded 1 5 1 1 6 6 1 16 28 3 4 14 13 3 3178805 1076 77 814 4500808 3525 87 ∞ 2645 606 2074 ∞ 55676 37203891

Time (ms) 14 11 11 11 1690 3 2 0 3 0 0 6100 2 0 10562 53 15 54 49774 67 12 ∞ 60 26 60 ∞ 527 206925

Table 1: Algorithm performance on rush hour puzzles.

2

Results

Table 1 shows the results of the test runs for puzzles 0-3. All algorithms were able to solve all the supplied rush hour puzzles (0-2). The added puzzle (3) turned out to be much more difficult for DFID, IDA* and RTA*. Tests for the first two were terminated after a long time ing without results. RTA* ran out of memory as the path it had traveled was all kept in memory. It’s also obvious from the results that RTA* is not showing correct cost, but the error behind that wasn’t found. Pure-Heuristic search solves all puzzles very fast and with very few nodes expanded, but does not guarantee an optimal solution, especially not for more difficult puzzles.

3

3 CONCLUSIONS

3

Conclusions

The results confirm established literature on the performance of the studied algorithms. A* memory constraints weren’t tested as the search space wasn’t large enough for that. There was no need to implement an eviction policy for EIDA* for the same reasons as for A* not having any problems. RTA* ran out of memory on the most difficult puzzle, because the implementation requires that the whole solution be stored in memory before returning. If it had been allowed to return single steps, RTA* would eventually have found the solution. That would not necessarily have happened much faster than for DFID and IDA* that would also have accomplished this, if not for the impatience of the authors. The usage of the heuristic makes it difficult to accurately estimate time and space complexity beforehand. It is known that DFID and IDA* use very little memory, while they need much more time to solve problems. This is confirmed in our test results. Uniform-Cost and A* use similar time and memory for difficult puzzles, while A* needs less memory for easy puzzles. Pure-Heuristic uses the least amount of time and expands the fewest nodes, though the solutions are not always optimal. EIDA* shows a different behaviour - for easy puzzles it uses similar memory and time as A* and Uniform-Cost, but starts using both more time and expanding more nodes as the puzzles become harder. No transposition table eviction policy was needed for the puzzles tested, but that would have been needed for a very large search space. EIDA* would probably also have been the only algorithm able to solve puzzles whose size would make the other algorithms cry, crash and burn.

4