Posted: May 8th, 2015

Concepts and Technologies of Artificial Intelligence

CIS006-2 Concepts and Technologies of Artificial Intelligence

Assignment 2 “8 Puzzle Problem”

The 8 Puzzle Problem is an AI classical example of how heuristic search can be used for finding solutions of real-world problems. A puzzle is represented by a 3 by 3 grid and 8 tiles numbered from 1 to 8. One cell of the grid is a blank (0). A start puzzle is a random sequence of the 8 tiles. The goal state is the sequence in which tile 1 is in the top left position, while the other tiles go clockwise around the blank state in the middle. There are a number of heuristics (Manhattan, Nielsen Sequence Score, etc) which allow the solution to be found with minimal expenses. The goal of this assignment is to compare different heuristics (at least two) on a given set of 10 puzzles. The performance of heuristics is evaluated in terms of 1) numbers of nodes tested during search and 2) numbers of moves that are required to achieve the goal state.

Experiments

The experiments is the main part of the assignment. Each student will be given an individual set of 10 puzzles for the experiments. The puzzle set is extracted from the puzzle combinations file by a number given by the tutor between 1 and 100. Student can use the MATLAB Illustration Code available on BREO to run the experiments on the given puzzles set. Experiments with the 2 core Manhattan and NSS heuristics will typically give a grade D-(5). Students are encouraged to extend the comparative experiments with new heuristics — using the larger number of heuristics will normally lead to a higher grade.

Report Contents

1.Heuristics used for search

2.Experiments run for collecting heuristics performance on a given puzzle set

3.Conclusions made on heuristics performance

4.References including all materials used

Assignment Viva

Six weeks after the assignment is given out, each student has to submit progress report allowing for receiving early feedback. Students who do not demonstrate satisfactory assignment progress are reported to the department Action Board.

Report Writing

Reports must be presented in the text form and submitted as a Word file in order to allow BREO Turnitin to check similarity. Experimental results must be placed in Word format tables. Presenting text or tables in an image format is therefore not allowed and is considered as attempt for Academic Offense.

Plagiarism

Submissions including text or tables in formats that the Turnitin cannot check as well as submissions with similarity level 20% and higher will be reported to the AO Panel.

Page 1 of 2