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

Contributed by John Maraist

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:

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

  3. Package rushhour links the generic search implementations with the Rushhour model.