Laboratory Experiences for Introducing Undergraduates to Artificial
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 2 3
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
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:
Stuart Russell and Peter Norvig. Artificial Intelligence: a modern approach, 2-nd ed.Prentice Hall, Upper Saddle River, NJ, USA, 2003.
Lisp implementations of search algorithms are available form the AIMA site at:
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