AI_Project_1.0

Problem

In this project, we use search to help Jon Snow save Westeros. The field where the white walkers are frozen in place can be thought of as an m × n grid of cells where m, n ≥ 4 . A grid cell contains either:

1. White walker
2. Jon Snow
3. Dragonstone
4. Obstacle

Jon Snowhas to go to the cell where the dragonstone lies to pick up a fixed number of pieces of dragonglass that he can carry. In order to kill a white walker, Jon has to be in an adjacent cell.

Using search you should formulate a plan that Jon can follow to kill all the white walkers. An optimal plan is one where Jon uses the least number of pieces of dragonglass to kill all the white walkers.

Algorithms implemented

1. Breadth-first search.
2. Depth-first search.
3. Iterative deepening search.
4. Uniform-cost search.
5. Greedy search with at least two heuristics.
6. A∗ search with at least two admissible heuristics.