jaypols/pacman-game

In this project, the Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. I implemented general search algorithms such as depth-first, breadth-first, uniform cost, and A* search algorithms which are used to solve navigation problems in the Pacman world.

Pacman Agent

COMP 6721 - Artificial Intelligence

Project Assignment 1 - Concordia University (Winter 2020)

📖 Table of Contents

Table of Contents

1. ➤ About The Project
2. ➤ Overview
3. ➤ Project Files Description
4. ➤ Getting Started
5. ➤ Scenario 1: Depth First Search
6. ➤ Scenario 2: Breadth First Search
7. ➤ Scenario 3: Uniform Cost Search
8. ➤ Scenario 4: A* search algorithm
9. ➤ Scenario 5: Finding All Corners
10. ➤ Scenario 6: Admissible and Consistent Heuristic
11. ➤ Scenario 7: Eating All Dots
12. ➤ Scenario 8: Suboptimal Search
13. ➤ References
14. ➤ Credits

📝 About The Project

For those of you not familiar with Pacman, it's a game where Pacman (the yellow circle with a mouth in the above figure) moves around in a maze and tries to eat as many food pellets (the small white dots) as possible, while avoiding the ghosts (the other two agents with eyes in the above figure). If Pacman eats all the food in a maze, it wins.

☁️ Overview

In this project, the Pacman agent will find paths through his maze world, both to reach a particular location and to collect food efficiently. I implemented general search algorithms such as depth-first, breadth-first, uniform cost, and A* search algorithms which are used to solve navigation problems in the Pacman world.

💾 Project Files Description

• search.py - Where all of the search algorithms reside.
• searchAgents.py - Where all of the search-based agents reside.
• pacman.py - The main file that runs Pacman games. This file also describes a Pacman GameState types.
• game.py - The logic behind how the Pacman world works.
• util.py - Useful data structures for implementing search algorithms.

Some other supporting files

• graphicsDisplay.py - Graphics for Pacman.
• graphicsUtils.py - Support for Pacman graphics.
• textDisplay.py - ASCII graphics for Pacman.
• ghostAgents.py - Agents to control ghosts.
• keyboardAgents.py - Keyboard interfaces to control Pacman.
• layout.py - Code for reading layout files and storing their contents.
• autograder.py - Project autograder.
• testParser.py - Parses autograder test and solution files.
• testClasses.py - General autograding test classes.
• test_cases/ - Directory containing the test cases for each scenario.
• searchTestClasses.py - Project specific autograding test classes.

📖 Getting Started

You are able to start the game by typing the following commands in the command line:

$ python pacman.py

You can see the list of all options and their default values via:

$ python pacman.py -h

Note that all of the commands that appear in this project also appear in commands.txt, for easy copying and pasting.

🔸 Scenario 1: Finding a Fixed Food Dot using Depth First Search

I have implemented the depth-first search (DFS) algorithm in the depthFirstSearch function in search.py.

The Pacman will quickly find a solution via running the following commands:

$ python pacman.py -l tinyMaze -p SearchAgent

$ python pacman.py -l mediumMaze -p SearchAgent

$ python pacman.py -l bigMaze -z .5 -p SearchAgent

🔸 Scenario 2: Finding a Fixed Food Dot using Breadth First Search

I have implemented the breadth-first search (BFS) algorithm in the breadthFirstSearch function in search.py.

I wrote a graph search algorithm that avoids expanding any already visited states.

The Pacman will quickly find a solution via running the following commands:

$ python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

$ python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

🔸 Scenario 3: Finding the best path using Uniform Cost Search

I have implemented the uniform-cost graph search (UCS) algorithm in the uniformCostSearch function in search.py.

While BFS will find a fewest-actions path to the goal, UCS will find paths that are “best” in other senses.

UCS agents differ only in the cost function they use.

The Pacman will quickly find a solution via running the following commands:

$ python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs

$ python pacman.py -l mediumDottedMaze -p StayEastSearchAgent

$ python pacman.py -l mediumScaryMaze -p StayWestSearchAgent

🔸 Scenario 4: Finding the best path using A* search algorithm

I have implemented the A* graph search algorithm in the aStarSearch function in search.py.

I used Manhattan distance as the heuristic function.

A* finds the optimal solution slightly faster than Uniform Cost Search.

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar,heuristic=manhattanHeuristic

🔸 Scenario 5: Finding All the Corners

I have implemented a search algorithm in searchAgents.py that helps Pacman agent to find the shortest path through the maze that touches all four corners.

The Pacman will quickly find a solution via running the following commands:

$ python pacman.py -l tinyCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

$ python pacman.py -l mediumCorners -p SearchAgent -a fn=bfs,prob=CornersProblem

🔸 Scenario 6: Corners Problem - Admissible and Consistent Heuristic

I have implemented a non-trivial non-negative consistent heuristic function that returns 0 at every goal state and never returns a negative value.

This function is both Admissible and Consistent and has been written in searchAgents.py.

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l mediumCorners -p AStarCornersAgent -z 0.5

🔸 Scenario 7: Eating All of The Dots

I have implemented a heuristic function that helps Pacman agent to eat all the food in as few steps as possible.

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l trickySearch -p AStarFoodSearchAgent

🔸 Scenario 8: Suboptimal Search

In this scenario, I have implemented a function that helps Pacman agent to find a path to the closest dot.

This function has been written in searchAgents.py

The Pacman will quickly find a solution via running the following command:

$ python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5

📜 Credits

Mohammad Amin Shamshiri

Acknowledgements: Based on UC Berkeley's Pacman AI project, http://ai.berkeley.edu