CS 312: Artificial Intelligence Laboratory
Assignment 1
Task 1: Uninformed Search
Teach Pacman how to intelligently find his food! The objective of this task is to simulate
breadth-first search, depth-first search, and DFID in the state space. The state-space consists of
an m x n grid. The start state is (0,0). The goal state is the position of (*) in the grid. The
Pacman is allowed to move UP, DOWN, LEFT and RIGHT (except for boundary).
Compare the above search methods on two accounts:
1. Length of the path (from the initial state to the goal state) that each algorithm finds
2. Number of states explored (visited) during the search.
(The length of the path and the number of visited states are two different things). Also, analyzing
whether or not the result depends on the order in which the neighbors of each node are added
into the list should be done.
The format of the report can be as follows:
1. Pseudo Code for MoveGen() and GoalTest()
2. Results (include table, plots if applicable)
3. Dependence of results on the order of neighbors added
Input format:
<ALGORITHM CODE> // 0 for bfs, 1 for dfs, 2 for dfid
<MAZE of m x n size>
Output format:
<Number of states explored>
<Length of path found>
<Maze with path formed with 0s>
Evaluation Criteria:
Correctness: 30
Report: 15
Code Quality: 5
Note
Penalty of 10% will be issued per day if the deadline is not met. If found copied, 0% score will
be awarded.
Sample Input 1:
0
+--+--+--+--+
|||
+ + + + +
|||
+--+--+ +--+
|||
+ + +--+ +
|| *
+--+--+--+--+
Sample Output 1:
42
24
0--+--+--+--+
00 |0000| |
+0 +0 +0 + +
|0000 |0 |
+--+--+0 +--+
| |0000 |
+ + +--+0 +
| | 000
+--+--+--+--+
To test your solutions, you can generate more mazes from here. (Put the type of maze as text.)
Deadline: 11:59 PM, 26 Dec 2021
