CMPT 417 (Intelligent Systems) Group Project

• In this project, we will be studying different search algorithms for solving a puzzle.

• In particular, we will be focusing on A*, iterative deepening A*, breadth-first search(BFS), depth-first search(DFS) and iterative deepening depth-first search(IDDFS).

• We will be testing the algorithms on a 8-puzzle. We will be comparing the algorithms by their completeness, optimality, time taken and the number of nodes expanded.

• We will be focusing on the time/space efficiency of the algorithms on different instances of the puzzles.

• Click here to jump to Usage.

Methodology

1. A* algorithm (Admissible heuristic)
2. Iterative Deepening A* algorithm
3. Breadth-First Search (BFS) algorithm
4. Depth-First Search (DFS) algorithm
5. Iterative Deepening Depth-first Search (IDDFS) algorithm

Setup

You will need Git, Python 3.5+ installed on your machine.

Cross-platform Install with Anaconda (Windows, macOS, Linux) - Recommended

• Select Python 3.5+ Installer
• Download Git here

Install Python Only

• Download Python here

Debian/Ubuntu based Linux with APT

Open up a Terminal and type:

sudo apt update
sudo apt install python3 python3-dev python3-pip python3-pygame git

macOS with Homebrew Package Manager

Open up a Terminal and type:

brew update
brew install python3 git

Install Python Packages with pip3 - REQUIRED (Windows, macOS)

Open up a Terminal and type:

pip3 install pygame
# or, if pip3 does not work:
pip install pygame

Cloning this repository onto your local machine

Open up a Terminal, cd to your preferred directory and type:

git clone [email protected]:j-shim/CMPT417GroupProject.git

Note: If git clone fails, confirm that your SSH Key is set up and registered properly.

Usage

Open up a Terminal, cd to your working directory and type:

python src/main.py

Authors

• Xiaolu (Christina) Zhu - [email protected] / GitHub
• Yusong (Ethan) Cai - [email protected] / GitHub
• Joo-Young (June) Shim - [email protected] / GitHub

Acknowledgments

• README template adapted from https://gist.github.com/PurpleBooth/109311bb0361f32d87a2
• src/util.py adapted from http://ai.berkeley.edu/search.html (Specifically, from this zip archive)
• A* algorithm pseudocode
• IDA* algorithm pseudocode
• BFS algorithm pseudocode
• DFS algorithm pseudocode
• IDDFS algorithm pseudocode