Overview

The N-puzzle game provides a good framework for illustrating conceptual AI search in an interesting and motivating way. Various uninformed and informed search algorithms are usually applied in this setting and their performance is evaluated.
In the 8-puzzle version of the game, a 3x3 board consists of 8 tiles numbered 1 through 8 and an empty tile (marked as 0). One may move any tile into an orthogonally adjacent empty square, but may not move outside the board or diagonally. The problem is to find a sequence of moves that transforms an initial board configuration into a specified goal configuration. The following are examples of an initial and goal configurations:

Initial configuration        Goal configuration
           1 6 2                          1 2 3
           5 7 3                          4 5 6
           0 4 8                          7 8 0

In this project students are asked to incorporate Explanation-Based Learning (EBL) into the N-puzzle problem. This allows them to better understand the concepts of analytical learning, and to see how learning improves the performance of search algorithms.

The objective of this project is to introduce the student to Analytical (Explanation-Based) Learning using the classical AI framework of search. Hands-on experiments with search algorithms combined with an EBL component give the student a deep, experiential understanding of the basics of EBL and the role it plays in improving the performance of search algorithms in particular and problem solving approaches in general.
The student should have knowledge of data structures and experience with either Lisp or Prolog. Before starting the project the student may want to cover the reading from the AI course textbook related to search and EBL as well as the recommended reading.
The project requires a good understanding of uninformed and informed search algorithms and their implementations either in Lisp or in Prolog. For the principles of search and implementations of search algorithms we recommend reading chapters 3 and 4 of:
Lisp implementations of search algorithms are available form the AIMA site at: http://aima.cs.berkeley.edu/lisp/doc/overview.html. More about Lisp and search algorithms in Lisp can be found in the classical text:
  • Patrick Winston and Berthold Horn, Lisp (3rd edition), Addison-Wesley, 1993.
An excellent book on Prolog and Prolog implementations of AI algorithms (including search) is:
  • Ivan Bratko, PROLOG Programming for Artificial Intelligence (3rd edition), Addison-Wesley, 2000.
An overview of the EBL is provided in Section 19.3. of Russell and Norvig's text. The basics of EBL are covered in Chapter 11 of Mitchell's classical ML text:
  • Tom Mitchell, Machine Learning, McGraw Hill, 1997.
The detailed project description is available in the PDF file NPuzzle.pdf. You will need the free Adobe Acrobat Reader to view this file.
This project is customizable to accommodate different approaches to teaching and different implementations. Additional exercises are also included for students seeking more extended challenges.
A sample syllabus is not available.

Additional readings are included in the Background section above.