Rushhour: Designing and comparing A* heuristics for a children's puzzle

Overview

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.

Contents

Project writeup for students (LaTeX source, PDF). Includes an overview of the provided code for modeling the Rushhour puzzle.

Files:

• spec.tex/spec.pdf: main document. Uses the graphicx and color packages, which should be part of a standard LaTeX distro.
• *.jpg: images included from the LaTeX source.

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.

Running a solution

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:
len
The number of moves in the solution found by the heuristic for that board.
The number of nodes added to the frontier for that heuristic/board.
exp
The number of nodes removed from frontier and expanded for that heuristic/board. In a column for a student's heuristic, when this number exceeds the result for BFS the entry will be highlighted.
ebf
The effective branching factor for that heuristic/board.

Starting points for exploring the provided code

(From the instructions to students)
1. Package rushhour.model is an implementation of the game mechanics --- the Rushhour board, cars, possible moves, etc.

2. 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.

3. 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.