Foundations of Artificial Intelligence

CSC 480 - Fall 2022

Assignment 1

Due Date: Thursday, September 29

Search Algorithms for 8-Puzzle

In this assignment you will develop a problem solving agent for a modified version of the 8-puzzle problem that implements a variety of uninformed as well as heuristic search strategies.

8-puzzle is a sliding puzzle that consists of a 3 x 3 frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes. If the size is 4×4 tiles, the puzzle is called the 15-puzzle. The object of the puzzle (starting from some initial state) is to place the tiles in order (see diagram) by making sliding moves that use the empty space (the blank tile), such as moving left, right, up, or down.

For more details on the 8-Puzzle problem and implementation details for the problem solving agents please review the PowerPoint Slides for Assignment 1.

Description

Move Costs: In this modified version of the original 8-puzzle problem, you will assume that the cost of a move is value of the tile being moved. So, in the left figure above, the cost of moving the blank tile down is 8. (Note that the cost of the moves are only relevant in search strategies that take path costs into account such as the Uniform Cost Search and the A* Search. For Breadth-First and Depth-First search strategies we ignore different costs associated with the moves).

Tasks:

  • Implement the basic problem solving agent that uses a queuing function (as described in the lecture notes and the textbook) to implement different search strategies.
  • Implement the following uninformed search strategies
    1. Breadth-First Search
    2. Depth-First Search
    3. [Extra Credit] Iterative Deepening
    4. Uniform Cost Search (where path costs are based on values of the tiles being moved)
  • Implement the following heuristic search strategies
    1. Best-First Search (using the heuristic function h1(n) = No. of misplaced tiles relative to the goal)
    2. A* Search with h1(n) as above
    3. A* Search with h2(n) = Sum of Manhattan distances of tiles from the correct positions
    4. [Extra Credit] A* Search with h3(n), where h3 is a heuristic better than h1 and h2.
  • Run your program using the following configurations ("0" = blank tile):
    • Goal State: 1 2 3 8 0 4 7 6 5
    • Start States:
      • Easy: 1 3 4 8 6 2 7 0 5
      • Medium: 2 8 1 0 4 3 7 6 5
      • Hard: 5 6 7 4 0 8 3 2 1

What to Submit:

  • Code [60 points]
  • 5 Minute Video [20 points]
  • Write up [20 points]

For more details on specific deliverables and additional implementation notes, please carefully review the PowerPoint Slides for Assignment 1.