Rushhour is a children's puzzle based on sliding blocks back-and-forth on a grid. One of the blocks represents the family car, which is stuck in traffic: one or more blocks sit in between the family car and an exit at the end of the family car's row of the grid. Initial grid configurations of the cars are given on a deck of cards, each card ranked by difficulty. Solving a puzzle configuration requires moving cars within each car's row or column so that the family car can move to the exit.
This assignment uses Rushhour to explore the design of heuristics for A* search, asking students to construct different heuristics for this single problem. The exercise asks students to calculate the effective branching factor and other metrics for each of their heuristics, as well as for naive BFS. The programming burden in this assignment can be relatively low; the provided Java code here includes the A* implementation and model of the game, focusing the assignment specifically on the construction and comparison of the heuristics.
| Summary | Students explore the behavior of different heuristics for A* search in the children's puzzle Rushhour. They practice applying the definitions of admissible heuristics, consistent heuristics, and effective branching factor to explain the differences between their heuristics. |
| Topics | A* search, heuristic design, admissible/consistent heuristics, effective branching factor |
| Audience | First-semester class in AI algorithms (upper-level undergraduate or graduate) introducing A* search. |
| Difficulty | Low to moderate. There is potentially relatively little programming required apart from the heuristic functions themselves, and the level of understanding of the various terms expected is straightforward to adjust. |
| Strengths | This assignments focuses very specifically on heristic design techniques, and comparison of heuristics. The relatively low scope of effort for programming keeps the student time for the exercise fairly low. |
| Weaknesses | The example boards drawn from the children's game are relatively small (of course, since they are suitable for six-year olds!). The provided code allows for larger board sizes, but we do not have code at this time which generates larger puzzles. |
| Dependencies | The provided code is in Java, and requires proficiency of data structures in Java, including lambda notation. |
| Variants | The number and types of heuristics and the sort of write-ups expected would be easy to vary. This puzzle could also be addressed by other techniques such as local searches, with comparisons of the techniques made. This assignment could also serve as a larger project for implementation of A* by simply not giving students the search implementation included here. |
Project writeup for students (LaTeX source, PDF). Includes an overview of the provided code for modeling the Rushhour puzzle.
Files:
Source tree. Standard Java source tree for provided code. Why Java? Our program uses Java as its main teaching language through data structures, and our students are very comfortable with it. Python or Lisp are certainly more common now for AI, but I am not able to assume that our students will have seen those languages at the point of our AI elective.
The directory src/samplesoln gives an example of how the students should package their solutions. It attempts to solve all of its sample boards with BFS, and with A* using each of the student's heuristics. It writes a table to standard output summarizing its results. If the student has two heuristics, then the first few lines of the table could look something like this:
| BFS | [1] | [2] |
Board config | len added exp ebf | len added exp ebf | len added exp ebf |
Deck 2, Card 01 | 16 647 643 1.38 | 16 648 644 1.38 | 16 645 637 1.38 |
Deck 2, Card 02 | 14 3141 2719 1.65 | 14 3392 2862 1.65 | 14 2338 1948 1.60 |
Deck 2, Card 04 | 22 435 423 1.22 | 22 430 419 1.22 | 22 410 386 1.21 |
There is one group of columns for each heuristic (plus one for
BFS), and one row for each initial board configuration, and a
key to the heuristics below the table. The four columns for
each heuristic are as follows:
Package rushhour.model is an implementation of the game mechanics --- the Rushhour board, cars, possible moves, etc.
Class rushhour.model.Boards has several sample initial board configurations.
Package search is a generic implementation of several of the graph search algorithms we have discussed.
The heart of this implementation is class GraphSearcher, which implements the Graph-Search algorithm of Russell and Norvig in its general form. The specific behaviors of the frontier, the explored set, checking for goal nodes, etc. are provided through the generic type arguments, and through the behaviors passed as constructor arguments.
You will make particular (if indirect) use of class AStarSearcher, which specializes GraphSearcher with the priority queue details of A* search.
Package rushhour links the generic search implementations with the Rushhour model.
Class rushhour.BreadthFirstFinder solves Rushhour puzzles using breadth-first search. This class is your frenemy: On the one hand, this class gives you a working example of how we specialize the general search algorithms to a particular problem. But on the other hand this class is your rival, since the entire point of designing good heuristics with A* is to beat blind search algorithms like BFS.
For each heuristic function you implement, you will write one class extending MovesFinder.
Note the series of MovesFinder's superclasses: they include the A* implementation of AStarSearcher, so extensions of MovesFinder all use A* search.
Note also that the constructor for MovesFinder takes only one argument --- the heuristic function. So MovesFinder applies the heuristic given in its constructor to A*. Your subclasses should provide that constructor argument, and nothing more: do not otherwise override any methods inherited from MovesFinder in your final submission.
(Overriding the various debugging functions as you develop and debug is fine, but silence this output for your actual submission.)
For example, see the ZeroHeuristic class in the sample solution.
Finally, you will extend class AbstractSolution to wrap up all of your work in one bundle. The run method of this class is suitable for calling from the main method of your concrete rushhour.Solution class, such as with
new Solution().run();The given version will apply all of your solvers, plus BFS, to all of the sample boards, and print the results as a table. Of course you are free to override or edit this method locally to print additional calculations useful for your analysis of the effective branching factor.